Test số 2 và 3 của subtask 2 bị lỗi, khi dòng thứ 3 rỗng, không có xâu nào.

Do đây là test chính thức, mình sẽ không tiến hành sửa test. Khi dòng thứ 3 rỗng, các bạn in ra dãy gốc (không thực hiện bất cứ thao tác cập nhật nào) nha.

Một trung tâm dữ liệu theo dõi trạng thái của ~N~ máy chủ được xếp thành một vòng tròn. Tại thời điểm ban đầu, ta thu được một dãy số nguyên không âm, gọi là dãy ~C~, gồm ~N~ phần tử lần lượt là ~C_1, C_2, \dots, C_N~.

Hệ thống lưu song song hai bản ghi:

• dãy trạng thái hiện tại ~X~,
• dãy trạng thái tích lũy ~Y~.

Ở thời điểm ban đầu, cả hai dãy đều giống với dãy ~C~.

Ba phép xử lý bit được hỗ trợ là xor, and và or. Đồng thời, hệ thống còn có khả năng "xoay trái" dãy ~X~ một số bước cố định: tức là mọi phần tử trong dãy đều được đẩy sang trái ~S~ vị trí theo kiểu vòng tròn, phần tử ở đầu vòng sẽ quay về cuối.

Ngoài các phép toán đó, hệ thống còn nhận trước một danh sách gồm ~M~ bộ lọc, mỗi bộ lọc là một trong ba từ khóa xor, and hoặc or. Trong suốt quá trình chạy, hệ thống sẽ thực hiện ~R~ vòng lặp; trong mỗi vòng lặp, lần lượt áp dụng từng bộ lọc theo thứ tự trong danh sách.

Cách thức hoạt động của một vòng lặp như sau:

1. Trước khi áp dụng mỗi bộ lọc, hệ thống xoay dãy ~X~ sang trái đúng ~S~ bước.
2. Giả sử đang ở bộ lọc thứ ~j~:
   • Nếu đó là xor, thì với từng vị trí ~i~, giá trị hiện tại của ~Y_i~ được thay bởi kết quả xor giữa ~X_i~ và ~Y_i~.
   • Nếu đó là and, thì ~Y_i~ được cập nhật bằng phép and giữa ~X_i~ và ~Y_i~.
   • Nếu đó là or, thì ~Y_i~ được cập nhật bằng phép or giữa ~X_i~ và ~Y_i~.

Yêu cầu: Xác định trạng thái cuối cùng của toàn bộ dãy ~Y~ sau khi tất cả các vòng lặp đã hoàn thành.

Input

• Dòng đầu chứa bốn số nguyên ~N~, ~M~, ~S~ và ~R~ (~0 \le S < N \le 2 \times 10^5~; ~1 \le M \le 10~; ~1 \le R \le 10^9~) — lần lượt là độ dài dãy, số bộ lọc mỗi vòng, bước xoay trái và số vòng lặp của quy trình.
• Dòng thứ hai là ~N~ số nguyên không âm ~C_1, C_2, \dots, C_N~ (~0 \le C_i \le 10^9~), đồng thời cũng là giá trị khởi tạo của cả ~X~ và ~Y~.
• Dòng thứ ba chứa ~M~ từ, mỗi từ là một trong ba chuỗi ký tự xor, and hoặc or. Đây là danh sách bộ lọc được áp dụng trong mỗi vòng lặp, theo đúng thứ tự trong dòng này.

Output

• Gồm ~N~ số nguyên, biểu thị nội dung cuối cùng của dãy ~Y~.