Flow Control

매우 복잡한 급수 시스템을 다루어야 한다. 이 시스템은 n개의 연결점과 m개의 파이프로 구성되며, i-th 파이프는 연결점 $x_i$와 $y_i$를 연결한다.

할 수 있는 일은 파이프를 조정하는 것뿐이다. m개의 정수 $f_1$, $f_2$, ..., $f_m$을 선택하여 파이프의 설정값으로 사용해야 한다. i-th 파이프는 연결점 $x_i$에서 연결점 $y_i$로 초당 $f_i$ 단위의 물을 보낸다($f_i$가 음수라면, 파이프는 연결점 $y_i$에서 연결점 $x_i$로 초당 |$f_i$| 단위의 물을 보낸다). $f_i$에는 -2 ⋅ $10^9$부터 2 ⋅ $10^9$까지의 임의의 정수를 설정할 수 있다.

시스템이 올바르게 작동하려면 몇 가지 제약 조건을 만족해야 한다. 모든 i ∈ $[1, n]$에 대해, i-th 연결점에는 수 $s_i$가 지정되어 있으며, 이는 i-th 연결점의 유입 유량과 유출 유량의 차이가 정확히 $s_i$여야 함을 의미한다($s_i$가 음수가 아니라면 i-th 연결점은 초당 $s_i$ 단위의 물을 받아야 하며, 음수라면 i-th 연결점은 다른 연결점들로 초당 |$s_i$| 단위의 물을 보내야 한다).

유입 및 유출 유량에 관한 모든 요구 사항을 만족하도록 정수 $f_1$, $f_2$, ..., $f_m$을 선택할 수 있는가?

첫 번째 줄에 연결점의 수를 나타내는 정수 n (1 ≤ n ≤ 2 ⋅ $10^5$)이 주어진다.

두 번째 줄에 연결점들에 대한 제약 조건인 n개의 정수 $s_1$, $s_2$, ..., $s_n$ (-$10^4$ ≤ $s_i$ ≤ $10^4$)이 주어진다.

세 번째 줄에 파이프의 수를 나타내는 정수 m (0 ≤ m ≤ 2 ⋅ $10^5$)이 주어진다.

이어지는 m개 줄 중 i-th 줄에는 두 정수 $x_i$와 $y_i$ (1 ≤ $x_i$, $y_i$ ≤ n, $x_i$ ≠ $y_i$)이 주어진다. 이는 i-th 파이프에 대한 설명이다. 각 무순서 쌍 (x, y)는 입력에 최대 한 번만 등장한다. 즉, (x, y)가 처음 등장한 뒤에는 (x, y) 또는 (y, x) 쌍이 등장하지 않는다. 모든 연결점 쌍에 대해 두 연결점을 잇는 파이프를 따른 경로가 존재함이 보장된다.

유입 및 유출 유량에 관한 모든 요구 사항을 만족하도록 정수 $f_1$, $f_2$, ..., $f_m$을 선택할 수 있다면 첫 번째 줄에 "Possible"을 출력한다. 그런 다음 m개의 줄을 출력하며, i-th 줄에는 파이프에 대해 선택한 설정값 $f_i$을 출력한다. 파이프에는 입력에 등장하는 순서대로 번호가 매겨진다.

그렇지 않다면 유일한 줄에 "Impossible"을 출력한다.