CF990F.Flow Control

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?

你必须处理一个非常复杂的供水系统。该系统由 $n$ 个节点和 $m$ 条管道组成，其中第 $i$ 条管道连接节点 $x_i$ 和 $y_i$。

你唯一能做的就是调节这些管道。你需要选择 $m$ 个整数 $f_1, f_2, \dots, f_m$ 作为各管道的设定值。第 $i$ 条管道将每秒从节点 $x_i$ 向节点 $y_i$ 输送 $f_i$ 单位的水（若 $f_i$ 为负，则该管道将每秒从节点 $y_i$ 向节点 $x_i$ 输送 $|f_i|$ 单位的水）。允许将 $f_i$ 设为 $-2 \cdot 10^9$ 到 $2 \cdot 10^9$ 范围内的任意整数。

为使系统正常运行，还需满足如下约束条件：对每个 $i \in [1, n]$，第 $i$ 个节点均关联一个数值 $s_i$，表示该节点的流入流量与流出流量之差必须恰好等于 $s_i$（若 $s_i$ 非负，则第 $i$ 个节点每秒必须接收 $s_i$ 单位的水；若 $s_i$ 为负，则第 $i$ 个节点每秒必须向其他节点输送 $|s_i|$ 单位的水）。

你能否选择整数 $f_1, f_2, \dots, f_m$，使得所有关于流入与流出流量的约束均被满足？

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.

第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$）—— 表示节点的数量。

第二行包含 $n$ 个整数 $s_1, s_2, \dots, s_n$（$-10^4 \le s_i \le 10^4$）—— 表示各节点的约束条件。

第三行包含一个整数 $m$（$0 \le m \le 2 \cdot 10^5$）—— 表示管道的数量。

接下来的 $m$ 行中，第 $i$ 行包含两个整数 $x_i$ 和 $y_i$（$1 \le x_i, y_i \le n$，且 $x_i \ne y_i$）—— 描述第 $i$ 条管道。保证输入中每个无序对 $(x, y)$ 至多出现一次（即在 $(x, y)$ 首次出现后，不会再出现 $(x, y)$ 或 $(y, x)$）。保证任意两个节点之间均存在一条沿管道构成的路径。

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.

如果可以选出满足所有入流和出流要求的整数 $f_1, f_2, \dots, f_m$，则在第一行输出 "Possible"；随后输出 $m$ 行，其中第 $i$ 行应包含 $f_i$ —— 即为第 $i$ 条管道选择的设定值（管道按其在输入中出现的顺序编号）。

否则，仅在一行中输出 "Impossible"。