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
minutes in the entire battle. During
the
-th minute, the frequency of the solar radiation is forecasted to
be
megahertz. In order for Superman
to be weakened by red sun radiation during minute
, the frequency
produced by the RSS must be a multiple of the solar frequency during
that minute. In minute
, the RSS will randomly produce a frequency
from a set of
intervals. The
-th of
these intervals will consist of the integers from
to
inclusive, meaning that during
minute
, the RSS is capable of emitting radiation at any one
frequency from
megahertz to
megahertz for any
from
to
. For each minute
, the
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
questions, where the
-th question is: "is it at all possible
to weaken Superman during exactly
minutes of the total
minutes of the battle?"
. Please write a program to
analyze the solar data and answer Batman's queries.
In cases worth of the points,
and
.
In a subset of those cases worth of the points,
.
Input Specification
The first line will contain two space-separated integers and
.
The next lines will each start with 2 space-separated integers
and
, followed by
space-separated pairs of
integers
and
(for
and
).
The last lines will each contain a single integer
(for
).
Output Specification
lines with one character per line. The
-th of these lines is
Y
if Batman can weaken Superman using simulated red sun radiation
during exactly 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 minutes. It's impossible
for Batman to weaken Superman for
minutes, since he'll always be
emitting the appropriate frequency to produce red sun radiation the last
round (the RSS radiation is fixed at
MHz during that minute, which
is a multiple of the solar radiation of
MHz). It's also impossible
for him to weaken Superman in all
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
MHz). However, there are
various ways in which Superman can be weakened for exactly
minutes,
such as if the following frequencies happen to be emitted by the RSS:
st minute:
MHz (producing red sun radiation when interfered with the sun's
MHz)
nd minute:
MHz (not producing red sun radiation when interfered with the sun's
MHz)
rd minute:
MHz (not producing red sun radiation when interfered with the sun's
MHz)
th minute:
MHz (producing red sun radiation when interfered with the sun's
MHz)
Comments