Căn phòng của Bitaro có hình tam giác vuông cân với độ dài mỗi cạnh góc vuông bằng \(N\). Một điểm trong phòng được biểu diễn bằng tọa độ \((x,y)\), thỏa mãn \(0 \le x \le N\), \(0 \le y \le N\) và \(x+y \le N\). Đỉnh góc vuông là gốc tọa độ; hai cạnh góc vuông nằm trên trục \(x\) và trục \(y\).

Một ngày nọ, Bitaro nhận thấy căn phòng đầy bụi. Ban đầu có \(M\) hạt bụi trong phòng. Hạt bụi thứ \(i\) (\(1 \le i \le M\)) nằm tại \((X_i,Y_i)\). Nhiều hạt bụi có thể nằm tại cùng một điểm.

Bitaro định dùng chổi để quét phòng. Ta coi chổi là một đoạn thẳng nằm trong phòng và gọi độ dài đoạn thẳng đó là bề rộng của chổi. Bitaro chỉ dùng chổi theo hai cách sau:

• Thao tác H: Đặt chổi song song với trục \(y\), với một đầu ở gốc tọa độ. Sau đó di chuyển chổi theo chiều dương của trục \(x\) xa nhất có thể trong phòng, luôn giữ chổi song song với trục \(y\) và một đầu nằm trên trục \(x\). Nếu bề rộng chổi là \(l\), hạt bụi ở \((x,y)\) thỏa mãn \(x<N-l\) và \(y \le l\) sẽ được đẩy đến \((N-l,y)\). Tại điểm đến có thể đã có các hạt bụi khác.
• Thao tác V: Đặt chổi song song với trục \(x\), với một đầu ở gốc tọa độ. Sau đó di chuyển chổi theo chiều dương của trục \(y\) xa nhất có thể trong phòng, luôn giữ chổi song song với trục \(x\) và một đầu nằm trên trục \(y\). Nếu bề rộng chổi là \(l\), hạt bụi ở \((x,y)\) thỏa mãn \(x \le l\) và \(y<N-l\) sẽ được đẩy đến \((x,N-l)\). Tại điểm đến có thể đã có các hạt bụi khác.

Có \(Q\) sự kiện lần lượt xảy ra trong phòng. Sự kiện thứ \(j\) (\(1 \le j \le Q\)) thuộc một trong bốn loại:

• Bitaro xác định tọa độ của hạt bụi thứ \(P_j\).
• Bitaro dùng chổi có bề rộng \(L_j\) để thực hiện thao tác H.
• Bitaro dùng chổi có bề rộng \(L_j\) để thực hiện thao tác V.
• Thêm một hạt bụi tại \((A_j,B_j)\). Nếu trước sự kiện này có \(c\) hạt bụi, hạt bụi mới được đánh số \(c+1\).

Hãy viết chương trình nhận độ dài cạnh góc vuông của căn phòng, tọa độ ban đầu của các hạt bụi và thông tin về các sự kiện, rồi xác định tọa độ các hạt bụi được hỏi.

Dữ liệu vào

Dữ liệu được cho từ đầu vào chuẩn theo định dạng sau. Tất cả các giá trị đều là số nguyên.

N M Q
X_1 Y_1
...
X_M Y_M
(Sự kiện 1)
...
(Sự kiện Q)

Mỗi dòng (Sự kiện j) chứa hai hoặc ba số nguyên cách nhau bởi dấu cách. Gọi số nguyên đầu tiên là \(T_j\). Ý nghĩa của dòng đó như sau:

• Nếu \(T_j=1\), dòng chứa 1 P_j: xác định tọa độ của hạt bụi thứ \(P_j\) tại thời điểm xảy ra sự kiện thứ \(j\).
• Nếu \(T_j=2\), dòng chứa 2 L_j: dùng chổi có bề rộng \(L_j\) thực hiện thao tác H.
• Nếu \(T_j=3\), dòng chứa 3 L_j: dùng chổi có bề rộng \(L_j\) thực hiện thao tác V.
• Nếu \(T_j=4\), dòng chứa 4 A_j B_j: thêm một hạt bụi tại \((A_j,B_j)\).

Dữ liệu ra

Với mỗi sự kiện có \(T_j=1\), in ra một dòng chứa hoành độ và tung độ của hạt bụi thứ \(P_j\) tại thời điểm xảy ra sự kiện đó, theo đúng thứ tự các sự kiện.

Ràng buộc

• \(1 \le N \le 10^9\).
• \(1 \le M \le 500000\).
• \(1 \le Q \le 1000000\).
• \(0 \le X_i \le N\) với mọi \(1 \le i \le M\).
• \(0 \le Y_i \le N\) với mọi \(1 \le i \le M\).
• \(X_i+Y_i \le N\) với mọi \(1 \le i \le M\).
• Với mỗi sự kiện loại \(1\), \(P_j\) nằm từ \(1\) đến số hạt bụi có trong phòng khi sự kiện thứ \(j\) xảy ra.
• Với mỗi sự kiện loại \(2\) hoặc \(3\), \(0 \le L_j \le N-1\).
• Với mỗi sự kiện loại \(4\), \(0 \le A_j \le N\), \(0 \le B_j \le N\) và \(A_j+B_j \le N\).
• Có ít nhất một sự kiện có \(T_j=1\).

Phân nhóm

Các ràng buộc chung ở trên áp dụng cho mọi nhóm. Các ràng buộc bổ sung và số điểm của từng nhóm như sau:

1. \(1\) điểm: \(M \le 2000\) và \(Q \le 5000\).
2. \(10\) điểm: \(T_j \in \{1,2,4\}\) với mọi \(1 \le j \le Q\).
3. \(11\) điểm: \(T_j \in \{1,2,3\}\) với mọi \(1 \le j \le Q\); đồng thời \(X_i \le X_{i+1}\) và \(Y_i \ge Y_{i+1}\) với mọi \(1 \le i \le M-1\).
4. \(53\) điểm: \(T_j \in \{1,2,3\}\) với mọi \(1 \le j \le Q\).
5. \(25\) điểm: Không có ràng buộc bổ sung.

Ví dụ

6 2 10
1 1
4 0
4 2 3
3 3
1 1
4 1 2
2 3
2 0
1 4
3 2
1 3
1 2

1 3
3 2
3 3
6 0

9 4 8
2 3
3 1
1 6
4 3
2 6
1 3
2 2
1 4
2 3
1 2
2 4
1 1

3 6
4 3
7 1
6 3

8 1 8
1 5
4 4 1
2 6
1 2
2 3
4 2 2
2 5
1 1
1 3

4 1
3 5
3 2

7 4 9
1 5
2 2
4 2
5 0
2 6
2 3
1 2
3 6
1 4
3 1
1 1
2 2
1 3

4 2
5 1
1 6
5 2

20 5 25
10 6
0 4
2 1
1 0
2 3
2 18
3 9
4 1 5
4 0 2
3 10
4 3 3
3 3
2 9
4 9 1
3 12
1 4
3 19
1 3
1 9
2 1
1 7
1 6
4 3 3
1 10
1 1
1 5
2 0
1 2
2 2
1 7

2 17
2 17
9 8
0 17
1 17
3 3
10 10
2 17
2 17
0 17

Nguồn

Bản dịch tiếng Việt từ đề chính thức bằng tiếng Anh của Ủy ban Olympic Tin học Nhật Bản, kỳ trại huấn luyện mùa xuân JOI 2019/2020, ngày thi thứ nhất (20/03/2020). Đề gốc và bản dịch được cung cấp theo giấy phép CC BY-SA 4.0.