3. Ťažké peniaze

Žaba sa dostal do Rady Trojstenu. To znamená, že dostal na zodpovednosť všetky Trojstenové peniaze a ich prerozdelenie. Preto si ich všetky prerozdelil do svojho vrecka a zmizol na Bahamy.

S veľkým množstvom peňazí sa jeho život zrazu stal oveľa šťastnejším. Nielenže ležal na pláži a popíjal mojito, ale zrazu sa pri ňom objavila aj očarujúco krásna slečna, ktorá ho mala rada pre to aký je. No a jeho jedinou kratochvíľou na krátenie času bolo chodenie po dražbách a kupovanie drahých obrazov, starých váz a luxusných áut.

Na dražbe je \(n\) miestností, v ktorých sa postupne dražia rôzne predmety. V niektorých sa draží dohora, v iných sa znižuje prestrelená cena. Občas sa v nejakej miestnosti začne dražiť nový predmet. V tom prípade nový predmet nahradil predchádzajúci predmet dražený v tejto miestnosti bez ohľadu na to či bol kúpený alebo nie. Dražba každého predmetu je definovaná dvoma parametrami: \(z\) a \(s\). \(s\) je počiatočná cena predmetu a \(z\) je hodnota, o ktorú sa každú sekundu zmení cena predmetu. Táto zmena môže byť kladná aj záporná.

Raz za čas vstane Žaba zo svojho lehátka na pláži, pozrie sa do všetkých miestností s číslami od \(a\) po \(b\) (vrátane týchto dvoch miestností) a ako správny boháč kúpi predmet s najväčšou aktuálnou cenou. Vašou úlohou je zistiť, koľko stál tento predmet v čase zakúpenia.

Úloha

Postupne vám budú prichádzať rôzne udalosti dvoch typov – začiatok dražby nového predmetu a Žabova kúpa.

Popis začiatku dražby je udaný štyrmi číslami \(t\), \(k\), \(z\) a \(s\). Hodnota \(t\) je sekunda, v ktorej dražba začala a \(k\) je miestnosť v ktorej sa dražba koná. Význam hodnôt \(z\) a \(s\) je vysvetlený v zadaní. Ak sa v miestnosti \(k\) dražil iný predmet, táto dražba je zrušená a nahradená novou dražbou. Zmena dražobnej ceny sa aplikuje na začiatku každej sekundy začínajúc sekundou \(t+1\).

Žabova kúpa je popísaná troma číslami \(t\), \(a\) a \(b\). \(t\) je čas, kedy išiel kupovať nový predmet a \(a\), \(b\) udáva interval čísiel miestností, z ktorých si vybral aktuálne najdrahší predmet. Kupovanie nastane až po tom ako sa ceny predmetov zmenili.

Formát vstupu

Na prvom riadku sú dve čísla \(n\) a \(m\). Prvé označuje počet miestností a druhé počet udalostí. Platí, že \(1\leq n \leq 100\,000\) a \(1\leq m \leq 300\,000\).

Nasleduje \(m\) riadkov. Na každom je popis jednej udalosti. Začiatok dražby nového predmetu bude popísaný ako 1 t k z s a kúpa bude zadaná ako 2 t a b. Udalosti sú dané v chronologickom poradí a žiadne dve udalosti sa nestali v tú istú sekundu. Platí, že absolútne hodnoty čísiel \(t\), \(z\) a \(s\) neprekročia \(10^6\).

Formát výstupu

Pre každú udalosť typu \(2\) vypíšte jedno číslo – hodnotu najdrahšieho predmetu, ktorý sa draží v miestnostiach \(a\) až \(b\). Ak v žiadnej z týchto miestností neprebieha dražba, vypíšte reťazec nema.

Príklad

Input:

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

Output:

12
17