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