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)~
Comments