Một thị trấn mới vừa được khánh thành ở một đất nước nhỏ. Như thường lệ, Mirko đã đảm bảo vị trí chánh thanh tra thuế. Nhiệm vụ của anh ấy là đảm bảo kế toán đầy đủ ở tất cả các công ty khác nhau trong thị trấn.

Có ~N~ văn phòng kinh doanh dọc theo con phố chính, được đánh số từ ~1~ đến ~N~ từ trái sang phải. Lúc đầu tất cả các văn phòng đều trống rỗng; theo thời gian, các công ty sẽ di chuyển ra vào các văn phòng này. Thỉnh thoảng, Mirko sẽ đi ngang qua một số văn phòng và kiểm tra sổ sách kế toán của một công ty duy nhất, hiện là công ty giàu có nhất trong các văn phòng đó.

Một công ty chuyển đến được mô tả bằng bốn số nguyên:

• ~T~ – ngày dọn vào ở, tính từ ngày khánh thành thị trấn (là ngày 1),
• ~K~ – số văn phòng,
• ~Z~ – lợi nhuận hàng ngày của công ty (có thể âm nếu công ty thua lỗ),
• ~S~ – số dư tài khoản của công ty vào ngày chuyển đến.

Nếu đã có một công ty ở văn phòng ~K~, công ty đó sẽ chuyển đi khi công ty mới chuyển đến. Công ty mới không mở cửa kinh doanh (hoặc kiếm được lợi nhuận) cho đến ngày sau khi chuyển đến. Chuyến đi kiểm tra của Mirko được mô tả bằng ba số nguyên:

• ~T~ – ngày kiểm tra, tính từ ngày khánh thành thị trấn,
• ~A~ và ~B~ – Mirko sẽ đi ngang qua tất cả các văn phòng có số từ ~A~ đến ~B~.

Vì Mirko chỉ làm việc vào cuối ngày nên tất cả các công ty đều đã hoàn thành công việc kinh doanh và ghi nhận lợi nhuận trong ngày tính đến thời điểm Mirko đi dạo. Hãy giúp Mirko bằng cách viết một chương trình để tìm số dư tài khoản của công ty giàu có nhất hiện nay mà Mirko đi ngang qua mỗi lần đi dạo.

Input

• Dòng đầu tiên chứa hai số nguyên dương lần lượt là ~N~ ~(1 \le N \le 100 000)~ và ~M~ ~(1 \le M \le 300 000)~, tương ứng là số lượng văn phòng và sự kiện.
• Mỗi ~M~dòng tiếp theo chứa mô tả về một sự kiện, được định dạng là “1 ~T~ ~K~ ~Z~ ~S~” (dành cho việc chuyển đến công ty) hoặc là “2 ~T~ ~A~ ~B~” (dành cho chuyến đi kiểm tra của Mirko).
• Tất cả các sự kiện được đưa ra theo trình tự thời gian và nhiều nhất một sự kiện sẽ xảy ra mỗi ngày (nghĩa là ~T~ sẽ tăng dần). Số ngày của sự kiện cuối cùng sẽ nhỏ hơn ~10^6~ và tất cả giá trị tuyệt đối của các số ~Z~ và ~S~ sẽ nhỏ hơn ~10^6~.

Output

• Với mỗi lần Mirko đi dạo, hãy ghi một dòng chứa số dư tài khoản của công ty mà Mirko sẽ kiểm tra hoặc từ “nema” (không có dấu ngoặc kép) nếu tất cả các văn phòng mà anh ấy đi qua đều trống.

Sample Input 1

2 4
1 1 1 2 4
1 2 2 3 2
2 5 1 2
2 7 1 2

Sample Output 1

12
17

Sample Input 2

3 6
1 1 1 4 -2
1 2 2 2 6
2 3 3 1
2 4 3 1
1 5 3 -6 20
2 6 2 3

Sample Output 2

8
10
14

Sample Input 3

5 9
1 1 5 4 -5
2 2 3 5
1 3 4 6 9
2 4 1 2
1 6 2 2 3
2 8 2 1
1 9 4 0 17
2 10 5 5
2 11 1 4

Sample Output 3

-1
nema
7
31
17