Halloween là một lễ hội truyền thống lớn được tổ chức vào ngày 31 tháng 10 hàng năm, trước ngày Lễ Các Thánh của đạo Kitô giáo. Đây là một ngày lễ được tổ chức để đánh dấu sự kết thúc của vụ mùa thu hoạch và bắt đầu mùa đông lạnh giá, nhằm tưởng nhớ những người quá cố, gồm các vị thánh, các vị tử đạo và tất cả những người thân đã qua đời. Ngày nay, lễ hội Halloween thường được tổ chức rộng rãi trên khắp thế giới, quy mô lớn hay nhỏ tùy theo mỗi quốc gia. Các biểu tượng đặc trưng cho lễ hội này là những trái bí ngô đèn lồng, hình ảnh phù thủy ma mị, trái táo độc, những con ma quỷ máu me, ghê rợn hay những con vật báo hiệu cho cái chết như cú mèo, dơi,... Trong ngày này, mọi người thường hóa trang thành những nhân vật ma quái, xuất hiện cùng nhau dưới ánh trăng, tham dự các bữa tiệc được trang trí rùng rợn.

Một trong những hoạt động thú vị ngày Halloween đó chính là trick or treat. Trẻ con sẽ hóa trang thành những nhân vật khác nhau, sau đó gõ cửa từng nhà để xin kẹo. Trick nghĩa là: đánh lừa, trò chơi tinh ma nghịch ngợm. Treat là tiếp đón, đối xử tử tế, tiếp đãi. Câu này có nghĩa là: Nếu muốn chúng tôi không chơi xấu thì hãy đãi chúng tôi cái gì đi. Trò này xuất phát từ niềm tin của người phương Tây: trong suốt lễ hội Samhain, vị thần Druids cho rằng người chết sẽ tìm đến lừa, gây hoang mang, lo sợ và phá hoại con người. Những hồn ma đi lại ăn xin và đến nhà nào, gia chủ phải cung cấp thức ăn cho chúng.

Pan là con gái của một ông chủ nhà máy sản xuất bánh kẹo, nên nhà cô lúc nào cũng đầy kẹo. Biết được điều này, bọn trẻ con trong xóm luôn chực chờ trước sân vườn nhà cô mỗi đêm Halloween để được phát kẹo. Halloween năm nay cũng không phải là một ngoại lệ. Cô đã lập danh sách tất cả các đứa trẻ trong xóm và đánh số ứng với từng đứa một số nguyên dương riêng biệt. Mỗi đứa trẻ khi vào nhà cô sẽ cầm một tô chứa được ~x~ viên kẹo và nếu muốn chia kẹo cho nó thì cô sẽ phải đổ đầy tô. Vì sức người có hạn, nên cô dự tính sẽ chỉ phát kẹo cho đúng ~K~ đứa trẻ, và đương nhiên là tốn ít kẹo nhất có thể. Hiện tại là buổi chiều và sân vườn nhà cô đang không có đứa trẻ nào cả. Nhưng một chút nữa thôi, chúng sẽ lần lượt ùa vào. Sẽ có ~n~ thời điểm, mỗi thời điểm sẽ diễn ra một trong ba thay đổi sau:

1) Một đứa trẻ đang không ở trong vườn đi vào với một cái tô mới

2) Một đứa trẻ đang ở trong vườn rời khỏi vườn

3) Pan thay đổi ý định, hay cụ thể hơn là thay đổi số ~K~

Pan muốn biết được số kẹo mình cần phải dùng sau mỗi thay đổi. Tuy nhiên, vì có quá nhiều thay đổi nên việc tính số kẹo cần dùng sẽ khá phức tạp. Vì thế, Pan giao nhiệm vụ cho bạn - quản gia của cô ấy - tính số kẹo cần dùng sau mỗi thay đổi.

INPUT

• Dòng đầu tiên gồm hai số nguyên dương ~n~ và ~K~ ( ~K ≤ n~ ), lần lượt là số lượng thay đổi và số ~K~ ban đầu
• ~n~ dòng tiếp theo sẽ là các thay đổi, sẽ có dạng là một trong ba dạng sau:

1) ~a~ ~x~ ~( 0 < a ≤ n, 0 < x ≤ 10^9)~ : đứa trẻ có số hiệu ~a~ đi vào vườn với tô chứa được ~x~ viên kẹo

2) ~-a~ ~( 0 < a ≤ n )~ : đứa trẻ có số hiệu ~a~ rời khỏi vườn

3) ~0~ ~x~ ~( 0 < x ≤ n )~ : Pan thay đổi ý định và ~K~ có giá trị mới là ~x~

Dữ liệu đảm bảo đứa trẻ chỉ vào vườn khi nó đang không ở trong vườn và chỉ ra khỏi vườn khi nó đang ở trong vườn.

OUTPUT

• Gồm ~n~ dòng, dòng thứ ~i~ là số lượng kẹo tối thiểu cần dùng sau thay đổi thứ ~i~, nếu không thể phát được thì in ra ~-1~

Ví dụ

Input 1

10 2
1 8
2 10
3 4
-1
4 7
-3
1 4
-2
-4
-1

Output 1

-1
18
12
14
11
17
11
11
-1
-1

Input 2

10 3
1 18
0 1
2 5
0 2
3 24
0 3
-2
4 6
2 9
0 2

Output 2

-1
18
5
23
23
47
-1
48
33
15

Subtask 1: 30% số test thỏa mãn ~n ≤ 1000~

Subtask 2: 30% số test thỏa mãn ~n ≤ 100000~, không có thay đổi dạng 3

Subtask 3: 20% số test thỏa mãn ~n ≤ 100000~

Subtask 4: 20% số test thỏa mãn ~n ≤ 500000~