Trung tâm IOI là một cơ sở huấn luyện có chỗ ở và khu ẩm thực phục vụ các đoàn đông người. Khu ẩm thực có \(N\) cửa hàng xếp thành một hàng, đánh số từ \(1\) đến \(N\). Trước mỗi cửa hàng có một hàng đợi cho khách.

Hôm nay có \(M\) đoàn lưu trú tại trung tâm, đánh số từ \(1\) đến \(M\). Thành viên các đoàn xếp hàng theo một cách khá lạ để trò chuyện với nhau. Đôi khi cửa hàng tặng món tráng miệng miễn phí cho một khách trong hàng. JOI-kun làm việc tại đây, có nhiệm vụ ghi lại đoàn của từng người nhận quà.

Trước khi mở cửa, các hàng đợi đều trống. Trong ngày xảy ra \(Q\) sự kiện theo thứ tự. Sự kiện thứ \(i\) thuộc một trong ba loại:

• Vào hàng (Join): Với mỗi cửa hàng có số từ \(L_i\) đến \(R_i\), kể cả hai đầu, có \(K_i\) khách thuộc đoàn \(C_i\) vào cuối hàng đợi.
• Rời hàng (Leave): Với mỗi cửa hàng có số từ \(L_i\) đến \(R_i\), nếu có ít nhất \(K_i\) khách trong hàng thì \(K_i\) người đầu hàng rời đi; nếu không thì tất cả khách trong hàng rời đi.
• Phục vụ (Service): Nếu hàng của cửa hàng \(A_i\) có ít nhất \(B_i\) khách, cửa hàng tặng món tráng miệng cho người thứ \(B_i\) tính từ đầu hàng. Nếu không thì nhân viên cửa hàng ăn món đó.

JOI-kun làm mất bản ghi các đoàn của những người nhận quà. Cậu muốn khôi phục nó từ thông tin về \(Q\) sự kiện. Với mỗi sự kiện Phục vụ, hãy xác định có khách nhận quà hay không; nếu có, hãy tìm số hiệu đoàn của người đó.

Dữ liệu vào

Đọc từ đầu vào chuẩn, tất cả các giá trị đều là số nguyên:

N M Q
(Sự kiện 1)
...
(Sự kiện Q)

Mỗi dòng sự kiện bắt đầu bằng số nguyên \(T_i\):

• 1 L_i R_i C_i K_i: Vào hàng. Thêm \(K_i\) người thuộc đoàn \(C_i\) vào cuối hàng của mỗi cửa hàng từ \(L_i\) đến \(R_i\).
• 2 L_i R_i K_i: Rời hàng. Cho \(K_i\) người đầu hàng rời đi ở mỗi cửa hàng từ \(L_i\) đến \(R_i\), hoặc cho tất cả rời đi nếu hàng có ít hơn \(K_i\) người.
• 3 A_i B_i: Phục vụ. Tặng quà cho người thứ \(B_i\) trong hàng của cửa hàng \(A_i\) nếu người đó tồn tại; nếu không thì nhân viên ăn quà.

Dữ liệu ra

Với mỗi sự kiện có \(T_i=3\), theo đúng thứ tự xảy ra, in một dòng chứa số hiệu đoàn của người nhận quà; in 0 nếu nhân viên cửa hàng ăn món tráng miệng.

Ràng buộc

• \(1 \le N,M,Q \le 250\,000\).
• \(T_i\) thuộc \(\{1,2,3\}\).
• Nếu \(T_i=1\): \(1 \le L_i \le R_i \le N\), \(1 \le C_i \le M\), \(1 \le K_i \le 10^9\).
• Nếu \(T_i=2\): \(1 \le L_i \le R_i \le N\), \(1 \le K_i \le 10^9\).
• Nếu \(T_i=3\): \(1 \le A_i \le N\), \(1 \le B_i \le 10^{15}\).
• Có ít nhất một sự kiện với \(T_i=3\).

Chấm điểm

1. \(2\) điểm: \(N,Q\le2\,000\); \(K_i=1\) với mọi sự kiện Vào hàng hoặc Rời hàng.
2. \(5\) điểm: \(N,Q\le2\,000\).
3. \(7\) điểm: \(N,Q\le65\,000\); \(R_i-L_i\le10\) và \(K_i=1\) với mọi sự kiện Vào hàng.
4. \(21\) điểm: \(M=1\).
5. \(15\) điểm: \(N,Q\le65\,000\); \(K_i=1\) với mọi sự kiện Vào hàng hoặc Rời hàng.
6. \(13\) điểm: \(N,Q\le65\,000\); chỉ có sự kiện Vào hàng và Phục vụ.
7. \(26\) điểm: \(N,Q\le65\,000\).
8. \(11\) điểm: Không có giới hạn bổ sung.

Ví dụ

3 5 7
1 2 3 5 2
1 1 2 2 4
3 2 3
2 1 3 3
3 1 2
1 2 3 4 2
3 3 2

2
0
4

3 4 7
1 1 2 1 1
1 1 3 4 1
2 2 3 1
2 1 3 1
1 1 2 2 1
3 1 1
3 3 2

4
0

183326 218318 22
1 106761 160918 151683 574906362
3 68709 1
1 29240 156379 22166 957318472
1 14054 181502 82845 97183925
2 112033 122908 587808357
2 57819 160939 215041262
3 36674 524274467
1 35854 69866 32334 322730299
1 1384 7230 115069 454256926
1 44192 158235 8750 84192710
3 54457 1077490708
2 10592 110384 979714505
2 44594 79244 311724477
3 160965 97183926
1 88748 101697 39148 373927458
3 41166 58039001
1 91501 137591 205480 958877326
2 77775 169655 135756956
1 12497 57047 60918 15666764
1 47839 51716 144688 732270998
3 114514 774994894
3 48645 169986425

0
22166
32334
0
82845
8750
60918

Nguồn

JOI 2021 Spring Training Camp, Contest 1, JCIOI. Bản dịch tiếng Việt theo CC BY-SA 4.0.