As you might already know , Ada the Ladybug is growing plants. She used to have a very long furrow, yet it costs a fortune to fence it. To reduce it, she has decided to build a square field. It is so big, that most of water falling from rains drops just onto a rectangular part of the field. Ada doesn't want the plants to wither, so she records all rains to know, how much water every particular plant got. Sadly, there are so many rains that she couldn't handle this alone!

At first, you will be given N queries with [x,y],[X,Y] rectangles telling you, where all of the N rains has fallen (lower left / upper right corners of it). Afterward M queries follow, with number i - the i-th plant for which you want to know, the number of rains, which has fallen onto it.

Input

The first line will contain 0< N,M ≤ 3*10⁵,0< L ≤ 5000, number of rains, number of questions and size of square field.

Then N lines follow, each containing four integers x, y, X, Y( 1 ≤ x ≤ X ≤ L, 1 ≤ y ≤ Y ≤ L ), bottom-left and upper-right corner of rectangle where i^th rain has fallen.

Afterward M lines follow, each containing two numbers 1 ≤ x, y ≤ L, asking for number of rains which has fallen onto plant on coordinates [x,y]

Output

Print M lines (for each query of second type), with integer indicating number of rains, which has fallen onto the plant in query.

Example Input

6 16 4
1 1 3 4
1 1 3 3
2 2 2 2
4 2 4 3
3 3 4 4
1 2 2 4
1 1
1 2
1 3
1 4
2 1 
2 2
2 3
2 4
3 1
3 2
3 3
3 4
4 1
4 2
4 3
4 4

Example Output

2
3
3
2
2
4
3
2
2
2
3
2
0
1
2
1