8. Obchod mení cenu kryptomeny!

Táto úloha je podobná úlohe s pred dvoch kôl, Ako Jemo Etku spoznal. Rozdiel je v tom, že sa ceny kryptomien menia v čase, a sú iné obmedzenia na vstup.

Jemko sa ešte stále pokúša očariť Etku pri pulte s kryptomenami. Každý deň chodí do Teska a nakupuje kryptomeny čo najvýhodnejšie. Etkinu pozornosť sa mu ale zachytiť nedarí.

Prednedávnom ale spravil objav a hneď mu svitlo, kde by mohol byť problém—všimol si, že každý deň sa v Tesku zmení cena práve jednej kryptomeny. Háčik bol v tom, že doteraz predpokladal, že tieto ceny sú konštantné. Ak pri nákupe zoberie do úvahy tieto zmeny, tak jeho nákupy budú skutočne optimálne, a takúto optimálnosť si Etka určite všimne.

Úloha

V Tesku predávajú \(n\) kryptomien, ktoré sú vyložené na pulte v jednom dlhom rade. Každá kryptomena má nejakú cenu v obchode a nejakú hodnotu na trhu. Jemko bude obchod navštevovať nasledujúcich \(q\) dní. Na začiatku dňa sa zmení cena práve jednej kryptomeny, hodnoty ale zostávajú rovnaké.

Pretože Jemko chodí vždy večer, na pulte je vždy z každej meny už len \(1\) minca. Pre každú návštevu vieme, koľko má Jemko peňazí v peňaženke a odkiaľ pokiaľ vidí, a zaujíma nás odpoveď na otázku: “Akú najväčšiu hodnotu vie Jemko nakúpiť, ak si vyberá len medzi menami, na ktoré dovidí?”

Formát vstupu

Na prvom riadku vstupu sú dve celé čísla \(n\) a \(q\) oddelené medzerou: počet rôznych kryptomien a počet dní, počas ktorých Jemko navštívi Tesko. Kryptomeny sú číslované od \(1\) po \(n\).

Ďalší riadok je prázdny.

Nasleduje \(n\) riadkov, v každom sú dve medzerou oddelené celé čísla \(c_i\), \(h_i\): počiatočná cena \(i\)-tej kryptomeny v Tesku, a hodnota tejto kryptomeny na trhu.

Ďalší riadok je prázdny.

Na konci bude \(q\) riadkov popisujúcich udalosti v jednotlivých dňoch: Jemkove návštevy a zmeny cien v obchode. V každom riadku je pätica čísel \(k_i\), \(b_i\), \(l_i\), \(r_i\), \(p_i\) oddelených medzerou. Prvé dve čísla hovoria, že cena kryptomeny \(k_i\) sa na začiatku dňa zmení na \(b_i\). Posledné tri čísla hovoria, že Jemko má v peňaženke \(p_i\) peňazí a môže nakupovať kryptomeny od \(l_i\) po \(r_i\), vrátane.

Formát výstupu

Pre každú Jemkovu návštevu Teska vypíšte jeden riadok a v ňom jedno celé číslo: najväčšiu hodnotu, ktorú vie Jemko nakúpiť.

Hodnotenie

Pre jednotlivé sady vstupov platia nasledovné obmedzenia.

Vo všetkých vstupoch platia nasledovné obmedzenia pre ceny kryptomien a peňaženku: \(1 \leq c_i, b_i, p_i \leq 50\).

Pre hodnoty kryptomien platí \(0 \leq h_i \leq 10^6\).

Kryptomeny indexujeme od jednotky; platí teda \(1 \leq k_i \leq n\) a \(1 \leq l_i \leq r_i \leq n\).

Príklad

Input:

5 3

5 5
6 6
7 7
8 8
9 9

1 7 1 5 22
2 8 1 5 22
3 9 1 5 22

Output:

22
20
17