Background

Please read the initials of the pinyin of the problem name together.

Problem Description

Scarlet has a mysterious $n \times m$ table. Now Scarlet fills numbers into the table. She will start from some cell in the first row, and then, in the order of left to right, top to bottom, she fills positive integers starting from $1$, until she fills the last row completely.

To let you determine this table, Scarlet will tell you $s$ groups of consecutive numbers in the same row. After that, Scarlet will ask you $q$ queries. You need to answer, for each queried number, which row and which column it is filled in.

Input Format

The first line contains $4$ positive integers $n, m, s, q$.

The next $s$ lines each contain two positive integers $a_i, b_i$, meaning that the integers from $a_i$ to $b_i$ are in the same row of the table and are consecutive.

The next $q$ lines each contain one positive integer $A_i$, representing the number in each query.

Output Format

If no table satisfying the constraints exists, output one line Impossible!.

Otherwise, if the table satisfying the constraints is not unique, output one line Uncertain!.

Otherwise, output the xor sum of all row and column results (including the earlier 0 0 cases), in order to reduce the output file size so that Scarlet can easily upload the testdata to the server.

3 4 2 2
8 9
2 4
9
3

7

Hint

Table:

0001
2345
6789

$9$ is in row $3$, column $4$.

$3$ is in row $2$, column $2$.

$3 \oplus 4 \oplus 2 \oplus 2 = 7$ ($\oplus$ means the xor operation).

Constraints

For $30\%$ of the data, $1 \leq n, m, s, q \leq 50$.

For $60\%$ of the data, $1 \leq m, s \leq 2000$.

For $100\%$ of the data, $1 \leq n, m, A_i, a_i, b_i \leq 10^{18}$, $1 \leq s, q \leq 5 * 10^5$, and $0 \leq b_i - a_i \leq m - 1$.

Translated by ChatGPT 5