Kế hoạch thực hiện công việc của một công ty là một danh sách gồm ~N~ công việc được đánh số thứ tự từ ~1~ đến ~N~, mỗi công việc cho biết thời gian để chuẩn bị và thời gian để thực hiện công việc đó. Tuy nhiên công ty chỉ có một đội ngũ nhân viên làm nhiệm vụ chuẩn bị và một đội ngũ nhân viên làm nhiệm vụ thực hiện công việc. Tại một thời điểm chỉ có một công việc được chuẩn bị và một công việc được thực hiện.

Thực tế khi triển khai, công ty có thêm ~M~ yêu cầu gồm một trong hai loại như sau:

• Thêm một công việc mới: Có thời gian chuẩn bị là ~u~ và thời gian thực hiện là ~v~. Công việc mới được đánh số tiếp theo trong danh sách;
• Loại bỏ công việc có số thứ tự ~k~.

Yêu cầu: Tìm cách sắp xếp tối ưu để ~N~ công việc ban đầu được hoàn thành sớm nhất. Với mỗi yêu cầu, đưa ra thời gian sớm nhất để hoàn thành công việc từ đầu đến thời điểm hoàn thành yêu cầu đó.

Dữ liệu vào từ tệp văn bản SCHEDU.INP:

• Dòng đầu tiên chứa hai số nguyên ~N~ và ~M~ ~(1 \le N \le 2 \times 10^5; \ 0 \le M \le 2 \times 10^5)~;
• ~N~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~x, y~ ~(1 \le x, y \le 10^9)~ mô tả thời gian chuẩn bị và thời gian thực hiện của ~N~ công việc đầu tiên;
• ~M~ dòng tiếp theo mô tả lần lượt các yêu cầu theo định dạng:
  • 1 u v: Mô tả yêu cầu có thêm một công việc mới có thời gian chuẩn bị là ~u~ và thời gian thực hiện là ~v~ ~(1 \le u, v \le 10^9)~;
  • 2 k: Mô tả yêu cầu loại bỏ công việc có thứ tự ~k~.

Dữ liệu đảm bảo tính nhất quán và luôn có đáp án. Không có công việc nào bị loại bỏ rồi mà xuất hiện yêu cầu loại bỏ sau đó và đảm bảo lúc nào cũng còn ít nhất một công việc.

Kết quả ghi ra tệp văn bản SCHEDU.OUT:

• Dòng đầu tiên ghi ra thời gian sớm nhất để ~N~ công việc ban đầu được hoàn thành;
• ~M~ dòng tiếp theo, tương ứng với mỗi yêu cầu ghi ra thời gian sớm nhất để hoàn thành các công việc từ đầu đến thời điểm hoàn thành yêu cầu đó.

Ví dụ

Input

2 0
1 3
2 3

Output

7

Input

1 4
4 3
1 3 8
1 5 2
2 1
2 3

Output

7
14
16
13
11

Ràng buộc

• Có ~25\%~ số test ứng với ~25\%~ số điểm có ~1 \le N \le 9; \ M = 0~;
• ~25\%~ số test khác ứng với ~25\%~ số điểm có ~1 \le N \le 20; \ M = 0~;
• ~25\%~ số test khác ứng với ~25\%~ số điểm có ~1 \le N \le 2 \times 10^5; \ M = 0~;
• ~25\%~ số test còn lại ứng với ~25\%~ số điểm không có ràng buộc gì thêm.