Woburn Challenge 2017-18 Round 3 - Senior Division

Problem 3: Down for Maintenance

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 24 hours. During each 24-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 24 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 N (0 ≤ N ≤ 100,000) times of day (measured in microseconds since midnight) at which he knows that the site is up, the i-th of which is U_i (0 ≤ U_i < 86,400,000,000). He's similarly made a list of M (0 ≤ M ≤ 100,000) times of day at which he knows that the site is down, the i-th of which is D_i (0 ≤ D_i < 86,400,000,000). All N + M 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 I (1 ≤ I ≤ 1,000,000,000) inactive intervals in each 24-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 I 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 K (1 ≤ K ≤ 100,000) possibly non-distinct times of day, the i-th of which is Q_i (0 ≤ Q_i < 86,400,000,000). 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 I inactive intervals are laid out).

Subtasks

In test cases worth 8/26 of the points, N ≤ 50, M ≤ 50, K ≤ 50, U_i ≤ 100,000, D_i ≤ 100,000, and Q_i ≤ 100,000.
In test cases worth another 9/26 of the points, U_i ≤ 100,000, D_i ≤ 100,000, and Q_i ≤ 100,000.

Input Format

The first line of input consists of a single integer, I.
The next line consists of a single integer, N.
N lines follow, the i-th of which consists of a single integer, U_i, for i = 1..N.
The next line consists of a single integer, M.
M lines follow, the i-th of which consists of a single integer, D_i, for i = 1..M.
The next line consists of a single integer, K.
K lines follow, the i-th of which consists of a single integer, Q_i, for i = 1..K.

Output Format

Either the string "Impossible" if there can't be exactly I inactive intervals, or K lines, the i-th of which is a string describing the status of time Q_i (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 (30,000). It's possible for the site to be up at that time, if the pair of inactive intervals are for example 15,000…25,000 and 70,000…2000. It's also possible for it to be down at that time, if the pair of inactive intervals are for example 65,000…5000 and 20,000…32,000. On the other hand, the statuses of three other queried times are guaranteed over all possible sets of two inactive intervals.

All Submissions
Best Solutions

Point Value: 15 (partial)
Time Limit: 4.00s
Memory Limit: 128M
Added: Mar 23, 2018
Author: SourSpinach

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)