Problem D
Paint Buckets
Gladys runs a paint shop with a huge stock of paint buckets of various volumes and hues. One of the special features of her shop is that she takes orders of any of the $10^9$ colors there are. On the surface of things, this cannot be possible – of course, there is not space enough for at lesat $10^9$ paint buckets!
To solve this problem, Gladys invented a special device capable of changing the hue of a particular color by $1\, 000$ color units. This means that if she gets an order for a particular color $x$, she may instead deliver any of the $2\, 001$ colors $[x - 1\, 000, x + 1\, 000]$.
A slight problem remains though – Gladys old inventory system does not support this particular way of fulfilling orders. Your task is to write her a new system, that determines for a given order of $v$ litres of a particular hue $h$, if the volume of all paint buckets she can transform to hue $h$ is at least $v$ litres.
Input
The first line of input contains the two integers $1 \le N \le 200\, 000$ and $1 \le Q \le 200\, 000$, the number of paint buckets and the number of orders the system will get. This is followed by $N$ lines describing the paint buckets. The $i$’th of these lines contains the positive integers $h_ i$ ($1 \le h_1 \le 10^9$) and $v_ i$ ($1 \le v_ i \le 10^4$), the hue and volume of the $i$’th bucket.
Finally, $Q$ lines follow containing the paint orders. The $i$’th of these lines contains the positive integers $h_ i$ ($1 \le h_1 \le 10^9$) and $v_ i$ ($1 \le v_ i \le 10^4$), the hue and volume of the $i$’th order.
Output
For each order $h$, $v$, output yes if Gladys can fullfill the order, and no otherwise.
| Sample Input 1 | Sample Output 1 |
|---|---|
9 6 5000000 100 5001000 100 5002000 100 6000000 100 6001000 100 6002001 100 7000000 100 7001001 100 7002001 100 5001000 301 5001000 300 6001000 201 6001000 200 7001001 201 7001001 200 |
no yes no yes no yes |
