Woburn Challenge 2017-18 Round 3 - Senior Division

Dave spends most of his free time on the internet, and especially loves hanging out on a hot new website. Unfortunately, in order to be able to handle the heavy traffic that it receives, the site frequently needs to be taken down for maintenance!
The site's maintenance schedule repeats every hours. During each
-hour cycle, it has one or more inactive intervals of time for which
it's down. Each interval spans some positive amount of time (though it
may be arbitrarily short), is less than
hours long, and may span from
the end of one day to the start of another. All of the intervals are
disjoint from one another (in other words, no point in time is inside
multiple intervals, inclusive). The site is neither always up nor always
down.
The schedule isn't publicly available, but Dave has noted down some
observations about the site's status at various times of the day. He's
made a list of
times of day (measured in
microseconds since midnight) at which he knows that the site is up, the
-th of which is
. He's
similarly made a list of
times of day at
which he knows that the site is down, the
-th of which is
. All
of these times are distinct.
Recently, one piece of information regarding the maintenance schedule
has finally surfaced - the Government of Canada has reported that their
site has exactly
inactive intervals in
each
-hour cycle. However, Dave isn't quite sure whether the
government should be trusted… As such, he'd first like to determine
whether or not it's even possible for there to be exactly
inactive
intervals according to his own observations.
If it is possible, he'd like to use this additional knowledge to help
deduce some additional information about the maintenance schedule, in
order to optimize his browsing time. He's interested in a list of
possibly non-distinct times of day, the
-th
of which is
. For each of these
times, he'd like to determine whether the site would definitely be up at
that time, definitely be down, or that its status would be unknown (it
might be either up or down depending on how the
inactive intervals are
laid out).
Subtasks
In test cases worth of the points,
,
,
,
,
, and
.
In test cases worth another of the points,
,
, and
.
Input Specification
The first line of input consists of a single integer, .
The next line consists of a single integer, .
lines follow, the
-th of which consists of a single integer,
, for
.
The next line consists of a single integer, .
lines follow, the
-th of which consists of a single integer,
, for
.
The next line consists of a single integer, .
lines follow, the
-th of which consists of a single integer,
, for
.
Output Specification
Either the string Impossible
if there can't be exactly inactive
intervals, or
lines, the
-th of which is a string describing the
status of time
(either
Up
, Down
, or Unknown
).
Sample Input
2
3
33582
9061
62057
3
78415
21592
1344
5
50000
30000
9061
66666
0
Sample Output
Up
Unknown
Up
Unknown
Down
Sample Explanation
Consider the second queried time of day (). It's possible for the
site to be up at that time, if the pair of inactive intervals are for
example
and
. It's also possible for it to be
down at that time, if the pair of inactive intervals are for example
and
. On the other hand, the statuses of three
other queried times are guaranteed over all possible sets of two
inactive intervals.
Comments