Migrated from Lutece 1058 秋实大哥与家

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

秋实大哥是一个顾家的男人，他认为人生就是旅途，不管我们漂到哪，最终还是会回到温暖的地方——家。

所以他买了很多家具。

秋实大哥的家可以看成一个$W\times H$的矩阵，每一件家具可以看成一个矩形，他们放置在秋实大哥的家里，相互之间没有重叠。

现在秋实大哥购置了一个新的大小为$1\times M$的家具，秋实大哥想知道他有多少种方式来安放这个家具。

Input

第一行包含四个整数$W，H，n，M$，表示秋实大哥家的大小为$W\times H$，现在已有$n$个家具，新购置的家具大小为$1\times M$。

接下来$n$行，每行包含$4$个整数$x1，y1，x2，y2$，分别表示这个家具左下角的坐标和右上角的坐标。

$1\leq n，H，W，M\leq 100000$，$1\leq x1\leq x2\leq W$，$1\leq y1\leq y2\leq H。$

Output

输出一行包含一个整数，表示有多少种方案可以来放置秋实大哥的新家具，要求不能跟原有的家具重叠，也不能超出家的范围。

Samples

3 3 1 2
2 2 2 2

8

Resources

2015 UESTC Training for Data Structures