P4885 Catastrophic Disaster.

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

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.

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.

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.

Table: ```plain 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