Description

从前有一道水题，给你一个矩形，求另一个矩形和它的面积交。

现在又有一道水题，给你\(n\)个矩形，求另一个矩形和它们的面积交。

具体地，在\(W \times L\)的平面上有\(n\)个互不相交的矩形，每个矩形的左下角点是\((x1_i,y1_i)\)，右上角点是 \((x2_i,y2_i)\)。你\(m\)组询问，对于每组询问，给出一个矩形，请输出这个矩形和给定的平面上\(n\)个矩形的面积交的和。

Format

Input

第一行包含两个整数\(n\),\(m\)，表示矩形数和询问数。
第二行两个整数\(W\)和\(L\)，表示平面的长和宽。
接下来\(n\)行，每行四个整数\(x1_i\),\(y1_i\),\(x2_i\),\(y2_i\)，表示第\(i\)个矩形。
接下来\(m\)行，每行四个整数\(x1_i\),\(y1_i\),\(x2_i\),\(y2_i\)，表示询问的矩形。

Output

\(m\)行，每行一个整数表示第\(i\)次询问的结果。

Sample 1

Input

2 2 6 6
1 1 3 3
4 2 5 4 
2 2 6 3
1 1 6 6

Output

2
6

Limitation

10s, 512MiB for each test case.

Hint

数据范围

对于20%的数据，\(n,m \leq 5000\)
对于30%的数据，\(W \times L \leq 1e7\)
对于60%的数据，\(n,m \leq 5e4\)
对于100%的数据，\(n,m \leq 5e5\)，\(0 \leq W,L \leq 5e5\)，\( 0 \leq x1 < x2 \leq W \) ，\( 0 \leq y1 < y2 \leq L \)
读入数据较大，建议使用读入优化。

Source

csp2019模拟题二