fuel

With the recent stock market crash, gas stations in Gabrovo have fallen into crisis. Kyusho regularly fills up his car in Gabrovo, but with today’s increased gas prices, he has no choice but to use public transportation. Faced with such a difficult choice, Kyusho set out to fix the situation.

There are $N$ gas stations in Gabrovo in total, numbered from $1$ to $N$, with $M$ bidirectional streets, each of which connecting two different gas stations. There is at most one street between each pair of gas stations. From each gas station, you can reach any other by moving along the streets. Each gas station has a fuel balance — an integer $c_i$ (it is possible for the balance to be negative). From time to time, a gas station drains fuel from all its neighbors (those to which there is a direct street), thus increasing its balance by $k_i$, where $k_i$ is the number of neighboring gas stations. In the same time, their balance decreases by one (even if it is already negative).

Kyusho knows that the people of Gabrovo will continue to pump fuel from each other until they all end up with a non-negative balance. Using his connections, he can convince each of them to rob his neighbors a certain number of times. But that’s where the problem comes in — Kyusho is not sure how to end up with no gas stations with a negative balance.

Task

Help Kyusho by writing a program that, given a map of gas stations and their balances, finds what instructions Kyusho should give.

Input data

The first line of the standard input contains two natural number $N$ and $M$ — the number of gas stations and the number of bidirectional streets between them. The next line contains $N$ space-separated integers $c_i$ — the balances of the gas stations. Еach of the the last $M$ lines contains two different numbers $A$ and $B$, indicating that there is a street between gas stations with numbers $A$ and $B$.

Output data

If no solution exists, print Impossible on the only line of standard output. Otherwise, print Possible on the first line. On the next line print $N$ integers $w_i$, separated by a space — how many times each of the gas stations must drain its neighbors so that in the end they all have a non-negative balance. Your solution is considered correct if in the end each gas station has a non-negative balance and for every $1 \leq i \leq N$ it is satisfied that $0 \leq w_i \leq 10^{18}$.

Constraints and clarifications

• $1 \leq N \leq 10^5$
• $N - 1 \leq M \leq N$
• $-10^4 \leq c_i \leq 10^4$
• $1 \leq A,B \leq N$, $A \neq B$
• From each gas station you can reach any other by moving along the streets.

Example 1

stdin

7 6
-4 -3 6 0 4 -7 5
2 1
1 3
1 4
4 5
4 6
6 7

stdout

Possible
6 9 0 4 0 6 1

Explanation

Gas station $1$ robs its neighbors $6$ times, increasing its balance by $6 \cdot 3 = 18$, but it is also robbed $9 + 0 + 4 = 13$ times, making its final balance equal to $−4 + 18 − 13 = 1$. All other gas stations are left with zero balance.
Illustration of the gas stations and initial balances:

Example 2

stdin

7 7
0 1 -1 4 -3 -1 1
1 2
2 3
3 4
4 5
5 1
1 6
4 7

stdout

Possible
4 3 3 1 4 5 0

Explanation

After following Kyusho’s instructions, all gas stations have a balance of $0$, except for the one with number $3$, which has a balance of $1$.

Example 3

stdin

3 3
1 0 -1
1 2
2 3
1 3

stdout

Impossible

Explanation

No matter how gas stations rob each other, they will always never all have a nonnegative balance.