Mislav và Marko đã nghĩ ra một trò chơi mới có tên là Rotate một cách sáng tạo. Đầu tiên, Mirko tưởng tượng một dãy số có độ dài ~N~ và chia nó thành các phần, mỗi phần chứa ~K~ số (~K~ chia đều cho ~N~). Phần đầu tiên chứa các số ở ~K~ vị trí đầu tiên trong chuỗi, phần thứ hai chứa ~K~ vị trí tiếp theo, v.v.

Sau đó, Marko yêu cầu Mislav áp dụng một số thao tác trên chuỗi, mỗi thao tác là một trong hai loại sau:

1. Xoay các số ở từng phần sang trái/phải theo vị trí ~X~

2. Xoay toàn bộ chuỗi sang trái/phải theo vị trí ~X~

Lưu ý rằng thao tác loại 2 có thể thay đổi các số thuộc mỗi phần. Sau khi áp dụng tất cả các thao tác, Mislav tiết lộ trình tự cuối cùng cho Marko. Nhiệm vụ của Marko là tìm ra trình tự bắt đầu của Mislav. Anh ấy đã nhờ bạn giúp đỡ.

Input

• Dòng đầu tiên của đầu vào chứa ba số nguyên dương: ~N~ ~(1 \le N \le 100 000)~, độ dài của chuỗi, ~K~ ~(1 \le K \le 100 000)~, kích thước của mỗi phần và ~Q~ ~(1 \le Q \le 100 000)~, số lượng hoạt động.
• Mỗi dòng trong số ~Q~ dòng sau chứa hai số nguyên: ~A~ ~(1 ≤ A ≤ 2)~, loại hoạt động và ~X~ ~(-100 000 ≤ X ≤ 100 000)~, số lượng vị trí cần xoay. Số âm biểu thị góc quay sang trái, trong khi số dương biểu thị góc quay sang phải.
• Dòng cuối cùng của đầu vào chứa ~N~ số nguyên ~Z_i~ ~(0 ≤ Zi \le 100 000)~ biểu thị chuỗi cuối cùng (sau khi áp dụng tất cả các thao tác).

Output

• Dòng đầu ra đầu tiên và duy nhất phải chứa trình tự bắt đầu được yêu cầu.

Scoring

• Trong dữ liệu kiểm tra có giá trị ít nhất 40% tổng số điểm, N sẽ tối đa là 100.
• Trong dữ liệu kiểm tra có giá trị ít nhất 70% tổng số điểm, K sẽ tối đa là 100.

Sample Input 1

4 2 2
2 2
1 1
3 2 1 0

Sample Output 1

0 1 2 3

Sample Input 2

8 4 4
1 3
1 15
1 -5
2 -1
6 10 14 19 2 16 17 1

Sample Output 2

6 10 14 1 2 16 17 19

Sample Input 3

9 3 5
1 1
2 -8
2 9
1 1
2 -4
3 1 8 7 4 5 2 6 9

Sample Output 3

5 3 6 9 7 1 8 2 4

Làm rõ ví dụ đầu tiên:

• Chuỗi bắt đầu là 0 1 2 3. Sau thao tác đầu tiên, chuỗi là 2 3 0 1 và sau thao tác thứ hai, nó trở thành 3 2 1 0. Điều này tương ứng với chuỗi cuối cùng.