Cho bộ ~N~ số nguyên không âm ~\left(a_{1}, a_{2}, \ldots, a_{N}\right)~ và một danh sách gồm ~M~ bộ quy tắc biến đổi.

Ta định nghĩa một bộ quy tắc biến đổi gồm ~N~ quy tắc biến đổi ~\left(u, oper, v\right)~. Những quy tắc này sẽ biến đổi dãy số ~A~ gồm ~N~ phần tử ~\left(a_1, a_2, \ldots , a_N\right)~ thành dãy số ~B~ cũng gồm ~N~ phần tử ~\left(b_1, b_2, \ldots, b_N\right)~. Trong đó, quy tắc thứ ~i~ như sau:

Yêu cầu: Cho bộ ~\left(a_{1}, a_{2}, \ldots, a_{N}\right)~ ban đầu, ~M~ bộ quy tắc biến đổi và số ~K~. Ta lần lượt biến đổi dãy ~A~ ban đầu thông qua các bộ quy tắc theo thứ tự sau: ~1,\; 2,\; \ldots,\; M,\; 1,\; 2,\; \ldots,\;M, \;1,\;2, \;\ldots~ Hãy xác định giá trị cuối cùng của ~\left(a_{1}, a_{2}, \ldots, a_{N}\right)~ sau ~K~ lần biến đổi.

Input

Gồm một dòng ghi ~3~ số ~N~, ~M~ và ~K~.

Dòng thứ ~2~ ghi ~N~ số ban đầu ~\left(a_{1}, a_{2}, \ldots, a_{N}\right)~

Tiếp theo là ~M~ nhóm dòng mô tả ~M~ bộ quy tắc biến đổi; mỗi bộ quy tắc được ghi trên ~N~ dòng gồm ~3~ giá trị ~u~ oper ~v~. Các bộ quy tắc biến đổi được ghi cách nhau một dòng trống.

Output

In ra ~N~ số nguyên là bộ số thu được sau ~K~ lần biến đổi.

Giới hạn

~1 \leq M \leq 100~ cho tất cả các test.

• Trong ~30\%~ test đầu tiên: ~1 \leq N \leq 10;~ ~0 \leq a_i \leq 10^9;~ ~0 \leq K \leq 100~.
• Trong ~30\%~ test tiếp theo: ~1 \leq N \leq 3;~ ~0 \leq a_i \leq 100;~ ~0 \leq K \leq 10^{9}~.
• Trong ~40\%~ test tiếp theo: ~1 \leq N \leq 10;~ ~0 \leq a_i \leq 10^{9}~; ~K \leq 10^9~ .

Sample Input

2 3 5
1 2
1 and 2
1 or 2

1 or 2
1 xor 2

1 xor 2
1 and 2

Sample Output

3 3

Note

~(1~, ~2)~ ~\rightarrow~ ~(0~, ~3)~ ~\rightarrow~ ~(3~, ~3)~ ~\rightarrow~ ~(0~, ~3)~ ~\rightarrow~ ~(0~, ~3)~ ~\rightarrow~ ~(3~, ~3)~