ADARAINB - Ada and Rain II


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*105,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 ith 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

hide comments
morass: 2017-05-01 00:17:00

@hodobox: Yes - thank you! ^_^

hodobox: 2017-04-19 23:28:17

You might want to change your link to spoj.com/problems/ADARAIN

morass: 2017-02-11 10:00:33

@Vipul Srivastava: Good day to you. Well you can't definitely brute-force each query. You shall find a way how to process it much faster (HINT: You shall consider when you need to answer!).

Good luck & Have nice day!

Vipul Srivastava: 2017-02-11 07:38:37

@ morass can you tell me where I need to optimise my solution?


Added by:Morass
Date:2017-02-10
Time limit:3.5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64