我们正在开发 Or Machine，这是一种专门针对一种操作进行高度优化的计算机：即 C++ 中的 |= 运算符。

Or Machine 有 $n$ 个寄存器，每个寄存器包含一个小于 $2^8$ 的非负整数。我们将它们标记为 $x_1, x_2, \dots, x_n$。一个程序由包含 $l$ 个操作的列表表示。每个操作由一对整数 $(a, b)$ 表示，意味着机器应该用 $x_a$ 和 $x_b$ 的值的按位或（bitwise OR）来更新 $x_a$ 的值。

Or Machine 接收一个程序、寄存器的初始值以及一个正整数 $t$。运行时，程序会逐个执行程序中的每个操作。当执行完最后一个操作后，它会返回到第一个操作并重复该过程。机器在恰好执行完 $t$ 次操作后停止。

我们希望我们的机器比通用计算机快得多，而硬件优化可能还不够。你能帮我们进行一些软件优化吗？

输入格式

第一行包含三个整数 $n$、$l$ 和 $t$（$1 \le n, l \le 2^{18}$，$1 \le t \le 10^{18}$）。$l$ 是程序的长度。

接下来的 $l$ 行给出了程序。每行包含两个整数 $a$ 和 $b$（$1 \le a, b \le n$），表示参与给定操作的一对寄存器。

最后一行包含 $n$ 个整数，即寄存器 $x_1, \dots, x_n$ 的初始值（$0 \le x_i < 2^8$）。

输出格式

在单行中输出 $n$ 个整数，即执行 $t$ 次操作后寄存器 $x_1, \dots, x_n$ 的值。

样例

输入样例 1

5 4 5
1 2
2 3
2 4
4 4
8 0 5 3 10

输出样例 1

15 7 5 3 10