Hotham 市再次受到其最著名的恶棍 Jester 的袭击。这一次他的目标是 Hotham 的供水系统。Hotham 的淡水储存在 $N$ 个水库中，这些水库由 $M$ 根管道连接。从任意一个水库到任意另一个水库至少存在一条路径（可能由多根管道组成）。此外，每根管道连接两个不同的水库，且任意两个水库之间最多只有一根管道。

Jester 破坏了其中一些管道，并一直在从中排水。出于他爱开玩笑的本性，Jester 确保从任何一根管道排出的水量都是偶数立方米每秒（$m^3/s$）。如果从连接水库 $u$ 和 $v$ 的管道中排出 $2d\ m^3/s$ 的水，那么 $u$ 和 $v$ 各损失 $d\ m^3/s$ 的水。

为了让事情更加混乱，Jester 实际上向一些被破坏的管道中注水，而不是从中排水。同样，注入任何一根管道的水量也是偶数 $m^3/s$。如果向连接水库 $u$ 和 $v$ 的管道中注入 $2p\ m^3/s$ 的水，那么 $u$ 和 $v$ 各获得 $p\ m^3/s$ 的水。每个水库中水量的净变化量是与其相连的管道所带来的获得量和损失量的总和。正式地，如果一个水库连接的管道中，有 $2d_1, 2d_2, \dots, 2d_a\ m^3/s$ 的水被排出，且有 $2p_1, 2p_2, \dots, 2p_b\ m^3/s$ 的水被注入，那么该水库水量的净变化量为 $p_1 + p_2 + \dots + p_b - d_1 - d_2 - \dots - d_a$。

Hotham 市长在水库中安装了传感器，但没有在管道中安装。因此，他可以观察到每个水库中水量的净变化，但不知道每根管道中排出或注入了多少水。

你的任务是编写一个程序来帮助市长。给定关于水库网络和每个水库净变化量的完整信息，你的程序应该判断这些信息是否足以唯一确定 Jester 的计划。如果对于每根管道排出或注入的水量只有唯一一种可能性，那么该计划就可以被唯一确定。注意，这些水量不需要对所有管道都相同。如果存在唯一一种可能性，你的程序应该将其输出。

输入格式

输入的第一行包含两个整数：$N$，表示 Hotham 的水库数量，和 $M$，表示管道数量。

接下来的 $N$ 行，每行包含一个整数 $c_i$：表示水库 $i$ ($1 \le i \le N$) 的净变化量。这 $N$ 行中的第 $i$ 行包含 $c_i$。

接下来的 $M$ 行，每行包含两个整数 $u_i$ 和 $v_i$ ($1 \le i \le M$)。每行表示在水库 $u_i$ 和 $v_i$ ($1 \le u_i, v_i \le N$) 之间有一根管道。这 $M$ 行中的第 $i$ 行包含 $u_i$ 和 $v_i$。

输入数据保证总是描述了一组可以由 Jester 实现的实际水库变化。

输出格式

如果无法唯一确定 Jester 的计划，你的程序应该输出单行，包含一个整数 0。

否则，你的程序应该输出 $M$ 行，每行包含一个整数 $x_i$ ($1 \le i \le M$)。第 $i$ 行应该包含 $x_i$。

• 如果 Jester 从连接 $u_i$ 和 $v_i$ 的管道中排出了 $d_i\ m^3/s$ 的水，则令 $x_i = -d_i$。
• 如果 Jester 向连接 $u_i$ 和 $v_i$ 的管道中注入了 $p_i\ m^3/s$ 的水，则令 $x_i = p_i$。
• 如果 Jester 没有从连接 $u_i$ 和 $v_i$ 的管道中添加或移除水，则令 $x_i = 0$。

数据范围

• $1 \le N \le 100\,000$
• $1 \le M \le 500\,000$
• $-10^9 \le c_i \le 10^9$
• 如果 Jester 的计划可以被唯一确定，$-10^9 \le x_i \le 10^9$。

在价值 30 分的测试用例中，Hotham 的水网是一棵树。

样例

输入样例 1

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

输出样例 1

2
-6
2

输入样例 2

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

输出样例 2

0