Ngày xưa, nền văn minh IOI phát triển dọc một con sông thẳng, rồi bị núi lửa hủy diệt. Khi đó mặt đất phẳng và được xem là trục \(x\); trục \(y\) biểu diễn độ cao. Đường \(y=0\) là mặt đất, \(y>0\) ở trên mặt đất và \(y<0\) ở dưới đất. Lớp địa chất hình thành \(a\) năm trước khi nền văn minh diệt vong ban đầu nằm trên đường \(y=-a\).

Sau đó xảy ra \(Q\) chuyển động địa chất. Chuyển động thứ \(i\) được mô tả bởi \(X_i,D_i,L_i\), với \(D_i\in\{1,2\}\):

• Nếu \(D_i=1\), một đứt gãy dọc đường hệ số góc 1 qua \((X_i,0)\) được tạo ra. Mọi điểm \((x,y)\) nằm phía trên đường này chuyển thành \((x+L_i,y+L_i)\).
• Nếu \(D_i=2\), một đứt gãy dọc đường hệ số góc \(-1\) qua \((X_i,0)\) được tạo ra. Mọi điểm \((x,y)\) nằm phía trên đường này chuyển thành \((x-L_i,y+L_i)\).
• Ngay sau đó, toàn bộ lớp địa chất trong miền \(y>0\) bị phong hóa và biến mất.

Với mỗi \(i\) từ 1 đến \(N\), hãy xác định lớp địa chất đang lộ trên mặt đất giữa \((i-1,0)\) và \((i,0)\) được hình thành bao nhiêu năm trước khi nền văn minh IOI diệt vong.

Dữ liệu vào

• Dòng đầu chứa \(N,Q\).
• \(Q\) dòng tiếp theo: dòng \(i\) chứa \(X_i,D_i,L_i\).

Dữ liệu ra

In ra \(N\) dòng. Dòng \(i\) là tuổi của lớp địa chất trên đoạn mặt đất từ \((i-1,0)\) đến \((i,0)\).

Ràng buộc

• \(1\le N,Q\le200000\).
• \(-10^9\le X_i\le10^9\).
• \(1\le D_i\le2\).
• \(1\le L_i\le10^9\).

Phân nhóm

• Nhóm 1 (18 điểm): \(N\le100\), \(Q\le100\), \(-100\le X_i\le100\), và \(L_i=1\) với mọi \(i\).
• Nhóm 2 (16 điểm): \(N\le3000\), \(Q\le3000\).
• Nhóm 3 (66 điểm): không có ràng buộc bổ sung.

Ví dụ

10 2
12 1 3
2 2 2

3
3
5
5
5
5
5
5
2
2

10 6
14 1 1
17 1 1
-6 2 1
3 2 1
4 1 1
0 2 1

5
5
4
5
5
5
5
5
4
4

15 10
28 1 7
-24 2 1
1 1 1
8 1 1
6 2 1
20 1 3
12 2 2
-10 1 3
7 2 1
5 1 2

15
14
14
14
14
12
12
12
12
12
12
12
15
15
12

Nguồn

Kỳ thi chung kết Olympic Tin học Nhật Bản 2015/2016, bài 5.