Problem Description

A new town has just been established in a small country. As usual, Mirko has been appointed as the chief tax inspector. His duty is to ensure proper accounting for all different companies in the town.

There are $N$ offices along the main street, numbered from $1$ to $N$ from left to right. Initially, all offices are empty; over time, companies will move in and out of these offices. Occasionally, Mirko will pass by some offices and only check the wealthiest company currently in those offices.

A company moving in is described by four integers:

• $T$: The date of moving in. The day the town was established is considered day $1$.

• $K$: The office number.

• $Z$: The daily profit of the company (which can be negative if the company is in loss).

• $S$: The initial account balance of the company on the day it moves in.

If there is already a company in office $K$, it moves out when a new company moves in.

The new company starts operating (or earning profit) from the day after it moves in.

Mirko's inspection is described by three integers:

• $T$: The date of inspection. The day the town was established is considered day $1$.

• $A, B$: Mirko will pass through all offices in the range $[A, B]$.

Since Mirko only works at the end of the day, all companies have completed their business for the day and announced their profits by the time Mirko walks by.

Help Mirko write a program that, during each inspection, finds the account balance of the wealthiest company that Mirko checks.

Input Format

The first line of input contains two positive integers, $N$ ($1 \leq N \leq 10^5$) and $M$ ($1 \leq M \leq 3 \times 10^5$), representing the number of offices and the number of events, respectively.

The next $M$ lines each contain a description of an event, in the format 1 T K Z S (company moving in) or 2 T A B (Mirko's inspection).

All events are given in chronological order, with at most one event happening per day (i.e., $T$ will be strictly increasing). The number of days in the last event will be less than $10^6$, and the absolute values of all $Z$ and $S$ numbers will be less than $10^6$.

Output Format

For each of Mirko's inspections, output a line containing the account balance of the company Mirko checks, or the word nema if all offices he passes through are empty.

Sample Input and Output

Input Sample #1

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

Output Sample #1

12
17

Input Sample #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

Output Sample #2

8
10
14

Input Sample #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

Output Sample #3

-1
nema
7
31
17

见题面 Input 部分

见题面 Output 部分