990F · Flow Control

Problem: You have to handle a very complex water distribution system. The system consists of $n$ junctions and $m$ pipes, $i$-th pipe connects junctions $x_i$ and $y_i$.

The only thing you can do is adjusting the pipes. You have to choose $m$ integer numbers $f_1$, $f_2$, ..., $f_m$ and use them as pipe settings. $i$-th pipe will distribute $f_i$ units of water per second from junction $x_i$ to junction $y_i$ (if $f_i$ is negative, then the pipe will distribute $|f_i|$ units of water per second from junction $y_i$ to junction $x_i$). It is allowed to set $f_i$ to any integer from $-2 \cdot 10^9$ to $2 \cdot 10^9$.

In order for the system to work properly, there are some constraints: for every $i \in [1, n]$, $i$-th junction has a number $s_i$ associated with it meaning that the difference between incoming and outcoming flow for $i$-th junction must be exactly $s_i$ (if $s_i$ is not negative, then $i$-th junction must receive $s_i$ units of water per second; if it is negative, then $i$-th junction must transfer $|s_i|$ units of water per second to other junctions).

Can you choose the integers $f_1$, $f_2$, ..., $f_m$ in such a way that all requirements on incoming and outcoming flows are satisfied?

Input Format: The first line contains an integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of junctions.

The second line contains $n$ integers $s_1, s_2, \dots, s_n$ ($-10^4 \le s_i \le 10^4$) — constraints for the junctions.

The third line contains an integer $m$ ($0 \le m \le 2 \cdot 10^5$) — the number of pipes.

$i$-th of the next $m$ lines contains two integers $x_i$ and $y_i$ ($1 \le x_i, y_i \le n$, $x_i \ne y_i$) — the description of $i$-th pipe. It is guaranteed that each unordered pair $(x, y)$ will appear no more than once in the input (it means that there won't be any pairs $(x, y)$ or $(y, x)$ after the first occurrence of $(x, y)$). It is guaranteed that for each pair of junctions there exists a path along the pipes connecting them.

Output Format: If you can choose such integer numbers $f_1, f_2, \dots, f_m$ in such a way that all requirements on incoming and outcoming flows are satisfied, then output "Possible" in the first line. Then output $m$ lines, $i$-th line should contain $f_i$ — the chosen setting numbers for the pipes. Pipes are numbered in order they appear in the input.

Otherwise output "Impossible" in the only line.