Kuong là một người rất kén ăn. Để ngăn chặn thói quen kén ăn của Kuong, bạn bè của cậu quyết định đặt nhiều loại nguyên liệu khác nhau lên chiếc bánh pizza mà Kuong yêu thích. Chiếc bánh pizza này có hình tròn, trong đó miếng đầu tiên và miếng cuối cùng được nối liền với nhau.

Độ ưa thích của bánh pizza đối với Kuong là giá trị lớn nhất của tổng độ ưa thích của các miếng pizza liên tiếp. Ngoài ra, độ ưa thích của một miếng pizza bằng tổng độ ưa thích của các nguyên liệu được đặt trên miếng đó. Độ ưa thích của một miếng pizza không có nguyên liệu nào là 0.

Vì việc không chọn miếng pizza nào mà vẫn gọi là độ ưa thích của bánh pizza thì thật kỳ lạ, nên độ ưa thích của bánh pizza chỉ bao gồm các trường hợp chọn từ một miếng pizza trở lên.

Ban đầu, không có nguyên liệu nào trên bánh pizza. Bạn bè của Kuong thực hiện tổng cộng $Q$ lần các hành động sau:

• 1 $a$ $b$: Đặt một nguyên liệu có độ ưa thích là $b$ ($-10^9 \le b \le 10^9$) lên miếng thứ $a$ ($1 \le a \le S$).
• 2: Hỏi độ ưa thích của bánh pizza hiện tại của Kuong là bao nhiêu.

Dòng đầu tiên chứa số lượng miếng pizza $S(1 \le S \le 200\,000)$ và số lượng hành động của bạn bè Kuong $Q(1 \le Q \le 500\,000)$, cách nhau bởi dấu cách.

Tiếp theo là $Q$ dòng, mỗi dòng mô tả một hành động.

Hành động 2 được đưa ra ít nhất một lần.

Tất cả các số được đưa vào đều là số nguyên.

Với mỗi hành động 2, hãy in ra độ ưa thích của bánh pizza của Kuong.

Ví dụ

Dữ liệu vào 1

5 12
1 1 3
1 2 3
1 3 -5
2
1 5 3
2
1 4 3
2
1 4 -5
2
1 3 4
2

Dữ liệu ra 1

6
9
12
9
9