Rico's Entertainment
Limits: 2 sec., 256 MiB
There’s no day that Rico doesn’t want to explode something.
Today Rico and Skipper decided to make a dynamite. They have N packages of explosives (N is an even number). The і-th package contains two boxes: one has \(a_i\) grams of explosives the other – \(b_i\) grams. Skipper and Rico alternatively take any package and add one of the boxes to a giant dynamite. Another box is discarded. Skipper starts this process. Rico believes an explosion is beautiful if the giant dynamite contains exactly x grams of explosives. But he hasn’t decided on the value of x yet.
Help him and determine for each of Q values \(x_i\) whether Rico can make a dynamite with exactly \(x_i\) grams of explosives regardless of the Skipper’s moves.
Input
The first line contains 2 space-separated integers N and Q. It’s guaranteed that N is an even number. Each of the following N lines contain two space-separated integers \(a_i\) and \(b_i\). Each of the following Q lines contain one integer \(x_i\).
Output
For each number \(x_i\) output "YES" (without quotes) if Rico can make a dynamite which contains exactly \(x_i\) grams of explosives regardless of the Skipper’s moves and "NO" otherwise.
Constraints
\(1 \le N, Q \le 10^5\)
\(0 \le a_i , b_i \le 10^9\)
\(0 \le x \le 10^{15}\)
Samples
Input (stdin) | Output (stdout) |
---|---|
2 4 4 7 5 2 4 9 12 0 | NO YES NO NO |
Notes
Rico cannot make a dynamite with 4 grams of explosives, but he can make one with 9 grams. One of the possible scenarios: Skipper chooses the 2nd package and the box with 5 grams of explosives then Rico takes 1st package and the box with 4 grams of explosives.
Submit a solution
Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
---|
Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
---|