A1254 | [COCI-2012_2013-contest2]#2 INSPEKTOR

A new town was just inaugurated in a small country. As usual, Mirko has secured the position of the chief tax inspector. His duty is ensuring adequate accounting in all the different companies in the town.
There are N business offices along the main street, numbered 1 to N from left to right. All offices are empty in the beginning; in time, companies will move in and out of these offices. From time to time, Mirko will pass by some of the offices and inspect the accounting of only one company, the currently wealthiest one in those offices.
A company moving in is described by four integers:
 T – the move-in day, numbered from town inauguration (which is day 1),  K – the office number,  Z – the daily profit of the company (can be negative if the company is losing money),  S – balance of the company's account on move-in day.
If there is already a company in office K, that company moves out when the new company moves in.
The new company doesn't open for business (or earn profit) until the day after move-in.
Mirko's inspection stroll is described by three integers:
 T – the inspection day, numbered from town inauguration,  A and B – Mirko will pass by all offices with numbers between A and B, inclusive.
Since Mirko works only at the end of the day, all companies will have already finished business and posted profit for the day by the time of Mirko's stroll.
Help Mirko by writing a program to find, for each stroll, the account balance of the currently wealthiest company that Mirko is passing by.

The first line of input contains two positive integers, N (1 ≤ N ≤ 100 000) and M (1 ≤ M ≤ 300 000),
the number of offices and events, respectively.
Each of the following M lines contains a description of one event, formatted either as “1 T K Z S” (for company move-in) or as “2 T A B” (for Mirko's inspection stroll).
All events are given chronologically, and at most one event will happen each day (that is, T will be strictly increasing). The last event's day number will be less than 106 , and all Z and S numbers' absolute values will be less than 10^
6.

For each Mirko's stroll output a line containing the account balance of the company that Mirko will inspect, or the word “nema” (without quotes) if all offices that he will pass by are empty.