Description

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

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

Format

Input

第一行：水库数量n，管道数量m （1 <= 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