S. Farming Negative Karma
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

After passing away from a chronic illness induced by data structure problems, Hiraku is isekaied into another world with a peaceful life as a farmer.

Hiraku's field can be represented as an $$$N$$$ by $$$M$$$ grid where each cell is a unit of farmland. The cell in the lower left is $$$(1, 1)$$$ and the cell in the upper right is $$$(N, M)$$$.

For each of the $$$A$$$ days of the plowing season, Hiraku will use his Almighty Farming Tool (AFT) to till a subrectange of his field.

Then for each of the $$$B$$$ planting days, Hiraku will try to plant a new type of seed on a certain subrectangle of his field. The seed can only be planted on cells that have been tilled at least $$$k$$$ times. He wants you to answer his query of how many cells in the rectangle could have that seed planted on it.

Considering this problem will not induce a chronic illness in you by data structure problems, help him answer his surveys!

Input

The first line of input contains four integers $$$N$$$ $$$M$$$ $$$A$$$ $$$B$$$ $$$(1 \leq N, M, A, B \leq 10^5)$$$.

The following $$$A$$$ lines of input will contain four integers $$$x_1$$$ $$$y_1$$$ $$$x_2$$$ $$$y_2$$$ $$$(1 \leq x_1 \leq x_2 \leq N, 1 \leq y_1 \leq y_2 \leq M)$$$ denoting that he will till all cells $$$(x, y)$$$ such that $$$x_1 \leq x \leq x_2, y_1 \leq y \leq y_2$$$.

The following $$$B$$$ lines of input wil contain five integers $$$x_1$$$ $$$y_1$$$ $$$x_2$$$ $$$y_2$$$ $$$k$$$ $$$(1 \leq x_1 \leq x_2 \leq N, 1 \leq y_1 \leq y_2 \leq M, 1 \leq k \leq 5)$$$ denoting that he will consider all cells $$$(x, y)$$$ such that $$$x_1 \leq x \leq x_2, y_1 \leq y \leq y_2$$$ for that seed and the $$$k$$$ that seed requires.

 —

Testcases in subtasks are numbered $$$1 \dots 20$$$ with samples skipped. Each testcase is worth the same amount of points.

For tests $$$1 - 2$$$, all inputted numbers will be $$$\leq 500$$$.

For tests $$$3 - 4$$$, there will be exactly one query of $$$1$$$ $$$1$$$ $$$N$$$ $$$M$$$ $$$5$$$.

For tests $$$5 - 7$$$, all queries will have $$$x_1 = x_2$$$.

For tests $$$8 - 9$$$, the rectangle tilled will always have $$$y_1 = y_2$$$.

For test $$$10$$$, the rectangle tilled will always be $$$1$$$ $$$1$$$ $$$N$$$ $$$M$$$.

For tests $$$11-18$$$, the $$$i$$$'th test will have $$$k$$$ be at most $$$\lceil \frac{i - 10}{2} \rceil$$$.

There are no additional constraints on the remaining tests.

Output

Output $$$B$$$ lines, the $$$i$$$'th containing a single integer denoting the number of cells the $$$i$$$'th type of plant can be planted on.

Example
Input
7 6 5 6
1 1 3 3
2 3 4 3
1 2 1 3
2 1 7 6
2 2 6 6
1 1 7 6 5
1 1 7 6 4
2 1 7 1 3
3 3 5 6 2
1 2 3 4 1
4 3 6 5 3
Output
0
2
0
12
8
1
Note

After all $$$A$$$ days of tilling, the amount of times each cell has been tilled is as follows.

1 2 2 0 0 0

2 3 4 2 2 2

2 3 4 2 2 2

1 2 3 2 2 2

1 2 2 2 2 2

1 2 2 2 2 2

1 1 1 1 1 1

For the first query, no cells have been tilled $$$5$$$ times, so the answer is $$$0$$$.

For the second query, cells $$$(2, 3)$$$ and $$$(3, 3)$$$ have been tilled twice, so the answer is $$$2$$$.

For the last query, cell $$$(4, 3)$$$ is the only valid cell, so the answer is $$$1$$$.

 —

Problem Idea: oursaco

Problem Preparation: oursaco, 3366

Occurrences: Advanced 13