Giải bài trực tuyến Học viện Công nghệ Bưu chính Viễn Thông

Tí và Tèo cùng nhau chơi trò chơi. Họ có N tấm thẻ, trên mỗi tấm thẻ có ghi một số nguyên dương và xếp các số lên bàn. Đầu tiên, Tí sẽ chia N số này thành các đoạn, mỗi đoạn chứa K số (N luôn chia hết cho K). Đoạn 1 sẽ chứa K số đầu tiên, đoạn 2 sẽ chứa K số tiếp theo, ....

Sau đó, họ sẽ thực hiện các thao tác sau. Có 2 loại thao tác:

1. Quay từng đoạn sang trái/phải X bước. 

2. Quay cả dãy số sang trái/phải X bước.

Chú ý rằng thao tác 2 sẽ làm thay đổi thành phần của từng đoạn. 

Tí thực hiện Q thao tác xong và đưa dãy số ban đầu trở thành 1 dãy số mới. Và Tèo cần phải tìm ra dãy số ban đầu.

Anh ấy thực sự cần các bạn giúp đỡ!

Input

Dòng đầu tiên chứa 3 số nguyên dương: N (1 <= N <= 100 000), chiều dài của dãy số, K
(1 <= K <= 100 000), kích thước mỗi đoạn, and Q (1 <= Q <= 100 000), số các thao tác thực hiện.

Q dòng tiếp theo chứa 2 số: A (1 <= A <= 2), loại thao tác, và X (-100 000 <= X <= 100 000), số bước quay dãy. Nếu X < 0 có nghĩa là ta quay dãy số sang bên trái, X > 0 là quay sang phải.

Dòng cuối cùng chứa N số nguyên dương Zi (0 <= Zi <= 100 000) là dãy số thu được sau khi thực hiện tất cả Q thao tác trên.

Output

In ra một dòng duy nhất chứa dãy số ban đầu.

Example

Input 1:

4 2 2 
2 2 
1 1 
3 2 1 0

Output 1:
0 1 2 3

Input 2:

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

Output 2:

6 10 14 1 2 16 17 19

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

Output 3:

5 3 6 9 7 1 8 2 4

Giải thích ví dụ 1: Dãy số ban đầu là 0 1 2 3.

Sau phép thao tác thứ nhất, dãy số sẽ là 2 3 0 1.

Và sau thao tác thứ 2, ta thu được dãy 3 2 1 0, tương ứng với dãy số Zi đã cho.