JOI-kun là một nhà sinh học. Cậu dự định thực hiện một thí nghiệm với kiến và các viên đường.

Thí nghiệm diễn ra trên một thanh thẳng dài \(10^9\), đặt theo chiều từ trái sang phải. Điểm cách đầu trái của thanh một khoảng \(x\) được gọi là điểm có tọa độ \(x\).

Ban đầu, trên thanh không có gì. JOI-kun thực hiện \(Q\) thao tác. Thao tác thứ \(i\) (\(1\le i\le Q\)) được mô tả bởi ba số nguyên \(T_i,X_i,A_i\):

• Nếu \(T_i=1\), đặt thêm \(A_i\) con kiến tại điểm có tọa độ \(X_i\).
• Nếu \(T_i=2\), đặt thêm \(A_i\) viên đường tại điểm có tọa độ \(X_i\).

Kiến và đường rất nhỏ nên có thể có nhiều con kiến hoặc nhiều viên đường tại cùng một điểm. Nhiều thao tác cũng có thể được thực hiện tại cùng một tọa độ.

Những con kiến trong thí nghiệm có một đặc tính kỳ lạ. Nếu JOI-kun vỗ tay, mỗi con kiến thực hiện hành động sau đúng một lần: nếu có viên đường nào cách nó không quá \(L\), nó tùy ý chọn một viên như vậy và ăn viên đó. Có thể nhiều con kiến cùng ăn một viên đường vào cùng một thời điểm.

Với mỗi \(k\) từ \(1\) đến \(Q\), hãy trả lời câu hỏi: giả sử JOI-kun vỗ tay sau thao tác thứ \(k\), số viên đường lớn nhất có thể được ít nhất một con kiến ăn là bao nhiêu?

Hãy viết chương trình trả lời tất cả các câu hỏi từ dãy thao tác và giá trị \(L\).

Lưu ý JOI-kun không thực sự vỗ tay trong quá trình thực hiện các thao tác. Vì vậy, vị trí của kiến không thay đổi và các viên đường không bị ăn mất; mỗi câu hỏi là một giả định riêng trên toàn bộ những gì đã được đặt lên thanh.

Dữ liệu vào

Dữ liệu được cho theo định dạng sau. Mọi giá trị đều là số nguyên.

Q L
T_1 X_1 A_1
T_2 X_2 A_2
...
T_Q X_Q A_Q

Dữ liệu ra

In \(Q\) dòng. Dòng thứ \(k\) ghi số viên đường lớn nhất có thể được ít nhất một con kiến ăn nếu JOI-kun vỗ tay sau thao tác thứ \(k\).

Ràng buộc

• \(1\le Q\le500000\).
• \(1\le L\le10^9\).
• \(T_i\in\{1,2\}\) với mọi \(1\le i\le Q\).
• \(0\le X_i\le10^9\) với mọi \(1\le i\le Q\).
• \(1\le A_i\le10^9\) với mọi \(1\le i\le Q\).

Phân nhóm

• Nhóm 1 (6 điểm): \(Q\le3000\).
• Nhóm 2 (16 điểm): \(L=1\); với mọi \(1\le i\le Q\), ta có \(X_i\le Q-1\) và \(X_i+T_i\) là số chẵn.
• Nhóm 3 (26 điểm): \(Q\) là số chẵn; \(T_i=1\) với mọi \(1\le i\le Q/2\), và \(T_i=2\) với mọi \(Q/2+1\le i\le Q\).
• Nhóm 4 (52 điểm): Không có ràng buộc bổ sung.

Ví dụ

4 1
1 1 1
2 2 1
1 3 1
2 0 1

0
1
1
2

20 1
2 16 778913911
1 7 558407445
1 1 589762439
1 17 74646747
1 1 149104909
1 15 956697952
2 6 389372991
2 4 867453845
1 15 157353445
1 9 846177695
1 7 747107163
2 10 525670462
2 16 478912944
2 6 301733761
2 12 132966485
1 1 748012313
2 10 830922632
1 19 969484637
1 13 370330582
1 1 464798040

0
0
0
74646747
74646747
778913911
1168286902
1168286902
1168286902
1168286902
1168286902
1693957364
2103741597
2405475358
2405475358
2405475358
2725982591
2725982591
2858949076
2858949076

20 6
2 27 12
2 9 11
1 36 10
2 39 4
2 14 9
2 33 7
2 38 20
2 0 20
2 25 16
1 14 3
1 13 19
2 6 4
2 15 6
2 33 4
1 12 11
1 44 1
2 17 14
2 12 19
1 48 18
2 30 16

0
0
0
4
4
10
10
10
10
13
30
30
32
32
40
41
44
44
44
44

20 268886972
1 984472666 733463744
1 478477245 94817772
1 242536956 330762563
1 65794782 319137646
1 320548477 937296140
1 815011370 938193848
1 565184190 917533785
1 245417414 534089975
1 529908772 977043962
1 603891865 700935654
2 167042244 479827216
2 173921297 798343455
2 916159596 810126726
2 999299355 465535307
2 965968070 501768990
2 936073643 174976034
2 832859952 778072072
2 955489596 704853861
2 246733786 382428992
2 227669861 390905006

0
0
0
0
0
0
0
0
0
0
479827216
1278170671
2088297397
2553832704
2949828263
2949828263
3727900335
3727900335
4110329327
4501234333

Nguồn

JOI 2021/2022, kỳ thi tuyển chọn mùa xuân, ngày thi thứ ba (22/03/2022). Đề của Ủy ban Olympic Tin học Nhật Bản (JCIOI). Bản dịch tiếng Việt theo giấy phép CC BY-SA 4.0.