一个齿轮系统能够正常运转，当且仅当对于任意一对相邻的齿轮 $(a, b)$，它们的半径与角速度的乘积之和为零，即 $r_a \omega_a + r_b \omega_b = 0$。

现在 Zag 有一个齿轮系统，他给出了齿轮之间的相邻关系和每个齿轮的半径，以及部分齿轮的角速度。他希望你求出每个齿轮的角速度。

输入格式

第一行包含三个整数 $n, m, k$ ($1 \le n, m \le 10^5, k \le n$)，分别表示齿轮的数量、相邻关系的条数以及已知角速度的齿轮数量。

接下来一行包含 $n$ 个整数 $r_1, r_2, \dots, r_n$ ($1 \le r_i \le 10^9$)，表示每个齿轮的半径。

接下来 $m$ 行，每行包含两个整数 $u, v$ ($1 \le u, v \le n$)，描述一对相邻的齿轮。

接下来 $k$ 行，每行包含两个整数 $p, v$ ($1 \le p \le n, |v| \le 10^9$)，表示 $\omega_p = v$。

输出格式

如果存在唯一解，输出一行 $n$ 个实数，按顺序描述每个齿轮的角速度。

如果无解，输出 0。

如果存在多个解，输出 -1。

如果你的答案与标准答案的绝对误差或相对误差不超过 $10^{-4}$，则判定为正确。

样例

输入样例 1

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

输出样例 1

6.00000000 -4.00000000 3.00000000 -2.40000000 2.00000000

输入样例 2

3 2 0
2 3 3
1 2
1 3

输出样例 2

-1

输入样例 3

4 4 2
1 3 7 4
1 2
2 3
3 4
4 1
1 666
2 -222

输出样例 3

666.00000000 -222.00000000 95.14285714 -166.50000000