#756. [Baltic2013]pipes

[Baltic2013]pipes

Description

n个水库,m条管道。Jester会在某些管道中间凿开一个洞,让水流出来或者用水泵把水打进去。保证这个流速是偶数。对于一条管道(u, v),如果在中间凿开了一个洞让水流出来,流速是2d m^3/s,那么水库uv失水速度为d m^3/s。同理,如果往一条管道(u, v)注水,流速为2p m^3/s,那么uv得到水的速度是p m^3/s

给定图的构造以及每个水库的水流的变化,问每条边的方案是否唯一。

Format

Input

第一行:水库数量n,管道数量m1 <= n <= 100 000, 1 <= m <= 500 000)下面n行:第i个水库的变化速度ci-10^9 <= ci <= 10^9)接下来m行:(u, v),保证没有重边

Output

如果方案唯一,输出方案,每行一个数xi-10^9 <= xi <= 10^9)表示第i条管道的流量变化。放水为负数,灌水为正数。否则输出0

Samples

输入样例1
4 3
-1
1
-3
1
1 2
1 3
1 4
 输入样例2
4 5
1
2
1
2
1 2
2 3
3 4
4 1
1 3
输出样例1
2
-6
2

输出样例2
0