Richest Tenant Company

There are N offices, numbered 1 through N from left to right. Initially, every office is empty.

When a company moves in, the following information is given.

• T: the move-in day. The first day of the office business is day 1.
• K: the office number
• Z: the amount the company earns or loses per day. This value may be negative.
• S: the amount of money the company has on its move-in day

If a new company moves into an office K that is already occupied, the previous company leaves that office on that day. A company spends its entire move-in day moving, so it earns no profit on that day. After that, while the company remains in the office, its money changes by exactly Z after work each day. Therefore, if a company moves in on day T0 with S money and is still in the same office after work on day D, its money is S + (D - T0) × Z.

Sometimes a continuous office interval is inspected to find the richest company in it. The interval has offices A and B as endpoints, and A may be greater than B. Each inspection is made after all work for that day has finished.

Given all move-in and inspection events in chronological order, answer every inspection.

The first line contains the number of offices N and the number of events M. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ 300,000)

Each of the next M lines describes one event in chronological order.

• Company move-in: 1 T K Z S
• Inspection: 2 T A B

At most one event happens on any day, so T is always given in increasing order. The day of the last event is less than 1,000,000. The absolute values of Z and S are also each less than 1,000,000.

For each inspection, print one line containing the largest amount of money held by any company in the inspected interval. If no company occupies an office in that interval, print nema.