题目描述

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

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

输入格式

第一行：水库数量 $n$，管道数量 $m$（$1 \le n \le 100 000, 1 \le m \le 500 000$）。
下面 $n$ 行：第 $i$ 个水库的变化速度 $c_i$（$-10^9 \le c_i \le 10^9$）。
接下来 $m$ 行：$(u, v)$，保证没有重边。

输出格式

如果方案唯一，输出方案，每行一个数 $x_i$（$-10^9 \le xi \le 10^9$）表示第 $i$ 条管道的流量变化。放水为负数，灌水为正数。否则输出 0。

样例 1

input

4 3
-1
1
-3
1
1 2
1 3
1 4

output

2
-6
2

样例 2

input

4 5
1
2
1
2
1 2
2 3
3 4
4 1
1 3

output

0

数据范围与提示

$1 \le N \le 10^5,$ $1 \le M \le 5\times 10^5,$ $−10^9 \le c_i \le 10^9$。
如果方案唯一，$−10^9 \le x_i \le 10^9$。
对于 $30\%$ 的测试数据，水库为树结构。

翻译来自 abcdabcd987。