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 ith 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^{5},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 ), bottomleft and upperright 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
hide comments
morass:
20170501 00:17:00
@hodobox: Yes  thank you! ^_^ 

hodobox:
20170419 23:28:17
You might want to change your link to spoj.com/problems/ADARAIN 

morass:
20170211 10:00:33
@Vipul Srivastava: Good day to you. Well you can't definitely bruteforce each query. You shall find a way how to process it much faster (HINT: You shall consider when you need to answer!).


Vipul Srivastava:
20170211 07:38:37
@ morass can you tell me where I need to optimise my solution? 
Added by:  Morass 
Date:  20170210 
Time limit:  3.5s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 