Woburn Challenge 2015-16 Round 3 - Junior Division

Being a masterful tactician, Batman wants to take advantage of his opponent's every weakness in battle. Too bad there just aren't many weaknesses of Superman. Though Superman's most famous weakness is Kryptonite, Batman's Kryptonite-laced weapons may still not be enough to help him win. A lesser known weakness of Super is the red sun. The red sun on Krypton is much less radiant than the yellow sun on Earth, which is why native Kryptonians aren't naturally as strong as Superman. It is only because Superman grew up on Earth that his powers are acquainted to and magnified by our powerful yellow sun's radiation.

Without a yellow sun, Superman's powers will be temporarily weakened. Even for Batman, it is quite near impossible to block out yellow sun radiation altogether. However, Batman believes that if he is able to temporarily convert the yellow sun radiation to red sun radiation, then he will be able to weaken Superman to the same effects. With the help of Lucius Fox, WayneTech was able to secretly develop a device to perform this exact conversion. This sophisticated technology, known as the Red Sun Simulator (RSS) will be installed onto the batplane which will idle in the sky during their fight. When the time is right, the device will continuously diffuse electromagnetic waves that will create an interference pattern with the electromagnetic radiation of the sun. The radiation generated by the RSS should be at precise frequencies so that the resulting wave exactly matches the frequency of the red sun of Krypton. Unfortunately for Batman, the frequency of solar radiation is going to be constantly changing due to small factors such as atmospheric conditions and their altitude. Due to these constraints, the ability of the RSS to produce waves at a certain frequency will also be limited.

The masterful tactician he is, Batman has planned out how every moment of the battle is going to go down. In particular, he predicts that there will be $N$ $(1\le N\le 50000)$ minutes in the entire battle. During the $i$-th minute, the frequency of the solar radiation is forecasted to be $F_i$ $(1\le F_i\le {10}^9)$ megahertz. In order for Superman to be weakened by red sun radiation during minute $i$, the frequency produced by the RSS must be a multiple of the solar frequency during that minute. In minute $i$, the RSS will randomly produce a frequency from a set of $M_i$ $(1\le M_i\le 5)$ intervals. The $j$-th of these intervals will consist of the integers from $A_{i,j}$ to $B_{i,j}$ $(1\le A_{i,j}\le B_{i,j}\le {10}^9)$ inclusive, meaning that during minute $i$, the RSS is capable of emitting radiation at any one frequency from $A_{i,j}$ megahertz to $B_{i,j}$ megahertz for any $j$ from $1$ to $M_i$. For each minute $i$, the $M_i$ intervals will be non-overlapping, meaning that any integer will be part of at most one of the intervals.

Batman is interested in whether he can weaken Superman for a particular number of minutes in total. Thusly, he wants to answer $Q$ $(1\le Q\le N+1)$ questions, where the $i$-th question is: "is it at all possible to weaken Superman during exactly $T_i$ minutes of the total $N$ minutes of the battle?" $(0\le T_i\le N)$. Please write a program to analyze the solar data and answer Batman's queries.

In cases worth $20/30$ of the points, $F_i\le 100$ and $B_{i,j}\le 100$.
In a subset of those cases worth $10/30$ of the points, $N\le 8$.

Input Specification

The first line will contain two space-separated integers $N$ and $Q$.
The next $N$ lines will each start with 2 space-separated integers $F_i$ and $M_i$, followed by $M_i$ space-separated pairs of integers $A_{i,j}$ and $B_{i,j}$ (for $i=1\dots N$ and $j=1\dots M_i$).
The last $Q$ lines will each contain a single integer $T_i$ (for $i=1\dots Q$).

Output Specification

$Q$ lines with one character per line. The $i$-th of these lines is Y if Batman can weaken Superman using simulated red sun radiation during exactly $T_i$ minutes, or N otherwise.

Sample Input

4 3
10 3 23 27 1 5 109 110
5 2 7 9 41 42
5 2 7 9 40 42
100 1 100 100
0
2
4

Sample Output

N
Y
N

Explanation

Batman predicts the battle to last a measly $4$ minutes. It's impossible for Batman to weaken Superman for $0$ minutes, since he'll always be emitting the appropriate frequency to produce red sun radiation the last round (the RSS radiation is fixed at $100$ MHz during that minute, which is a multiple of the solar radiation of $100$ MHz). It's also impossible for him to weaken Superman in all $4$ minutes, since there's no way he can produce red sun radiation in the second minute (the RSS cannot possibly emit a frequency which is a multiple of $5$ MHz). However, there are various ways in which Superman can be weakened for exactly $2$ minutes, such as if the following frequencies happen to be emitted by the RSS:

• $1$st minute: $110$ MHz (producing red sun radiation when interfered with the sun's $10$ MHz)
• $2$nd minute: $8$ MHz (not producing red sun radiation when interfered with the sun's $5$ MHz)
• $3$rd minute: $42$ MHz (not producing red sun radiation when interfered with the sun's $5$ MHz)
• $4$th minute: $100$ MHz (producing red sun radiation when interfered with the sun's $100$ MHz)