Giải bài trực tuyến

Cho bộ N số nguyên không âm (a₁, a₂, …, a_N) 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 (u, oper, v). Những quy tắc này sẽ biến đổi dãy số A gồm N phần tử (a₁, a₂, …, a_N) thành dãy số B cũng gồm N phần tử (b₁, b₂, ... , b_N). Trong đó, quy tắc thứ i như sau:

b_i = a_u oper a_v, với oper là 1 trong 3 phép toán and, or, xor.

Yêu cầu: Cho bộ (a₁, a₂, ... , a_N) 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, …, M, 1, 2, …,M, 1, 2, ... Hãy xác định giá trị cuối cùng của (a₁, a₂, …, a_N) 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 a₁, a₂, …, a_N

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 ≤ M ≤ 100 cho tất cả các test.

• Trong 30% test đầu tiên: 1 ≤ N ≤ 10; 0 ≤ a_i ≤ 10⁹; 0 ≤ K ≤ 100. 
• Trong 30% test tiếp theo: 1 ≤ N ≤ 3; 0 ≤ a_i ≤ 100; 0 ≤ K ≤ 10⁹. 
• Trong 40% test tiếp theo: 1 ≤ N ≤ 10; 0 ≤ a_i ≤ 10⁹, K ≤ 10⁹. 

Thời gian chạy: 0.5s cho mỗi test

Chú ý:

• Trong thời gian thi, bài của bạn chỉ được chấm với test đề bài.
• Nếu bài của bạn chạy đúng trên máy mình, nhưng sai khi nộp lên SPOJ, bạn có thể kiểm tra ở ideone. Chú ý khi submit lên ideone, để chế độ Secret để người khác không đọc được code của bạn.

Example

Input:
2 3 5
1 2
1 and 2
1 or 2

1 or 2
1 xor 2

1 xor 2
1 and 2 

Output:
3 3

Giải thích

(1, 2) ⇒ (0, 3) ⇒ (3, 3) ⇒ (0, 3) ⇒ (0, 3) ⇒ (3, 3)