5. Nádoby

Samo má doma veľa hadov. Chcel si kúpiť veľa hadíc (samíc hadov), aby neskôr mal aj veľa háďat. Tak si ich objednal z nemenovaného internetového obchodu, ale keď mu prišla zásielka, postihlo ho nepríjemné prekvapenie. Miesto hadíc (samíc hadov) mu omylom poslali hadice (hadice). No čo už, pomyslel si, nájdem si teda inú zábavu. A našiel si inú zábavu.

Úloha

Máme sústavu \(n\) nádob poprepájaných hadičkami. Na začiatku sú všetky nádoby prázdne. Nad prvou nádobou je kohútik, cez ktorý sa do tohto systému napúšťa voda. Funguje princíp spojených nádob.

Hadičkou začne voda pretekať, až jej hladina v niektorej z incidentných nádob dosiahne úroveň najvyššieho bodu danej hadičky. Vtedy sa rast hladiny v tej nádobe zastaví a začne sa napúšťať tá druhá a cez ňu prípadne ďalšie. Až sa hladiny vyrovnajú, zostanú vyrovnané navždy a ak napúšťanie pokračuje, budú stúpať súčasne.

Vašou úlohou je zistiť, z ktorej nádoby voda pretečie.

Formát vstupu

Na prvom riadku sú dve medzerou oddelené čísla \(n\) a \(k\) – počet nádob a počet hadičiek. Nádoby sú očíslované od \(1\) po \(n\).

Na druhom riadku je \(n\) čísel, \(d_1\) až \(d_n\) – výšky, v ktorých sa nachádza dno danej nádoby. Na treťom riadku je \(n\) čísel, \(h_1\) až \(h_n\) – výšky horných okrajov jednotlivých nádob.

Nasleduje \(k\) riadkov popisujúcich jednotlivé hadičky. Na \(i\)-tom riadku je päť medzerou oddelených celých čísel, \(x_i\), \(y_i\), \(a_i\), \(b_i\), \(c_i\). Táto hadica spája nádoby \(x_i\) a \(y_i\). Platí \(x_i \neq y_i\). Pripája sa do nádoby \(x_i\) vo výške \(a_i\) a do nádoby \(y_i\) vo výške \(b_i\). Jej najvyšší bod je vo výške \(c_i\). Platí \(a_i < c_i > b_i\) a koncové body hadice sú vyššie ako dno nádoby ku ktorej sa pripájajú. Koncový bod však môže byť vyššie ako horný okraj nádoby, v takomto prípade cez neho môže do nádoby voda iba natekať (vytekať nie).

Medzi tou istou dvojicou nádob môže viesť aj viac ako jedna hadička.

Všetky výškové údaje sú celé čísla z intervalu od \(0\) do \(10^9\) vrátane a sú navzájom rôzne.

Formát výstupu

Vypíšte jedno číslo, číslo nádoby ktorá pretečie.

Hodnotenie

Je 8 sád vstupov. Platia v nich nasledujúce obmedzenia:

Príklad

Input:

3 3
20 10 0
90 50 60
1 2 25 15 35
2 3 30 40 45
1 3 70 75 80

Output:

2

Keď hladina v nádobe 1 dosiahne výšku 35, začne sa napĺňať nádoba 2. Potom čo aj v nádobe 2 dosiahne výšku 35, voda začne stúpať v oboch nádobách súčasne, až kým nedosiahne výšku 45, kedy sa začne napúšťať nádoba 3. Keď voda aj v nej dosiahne výšku 45, začne voda stúpať vo všetkých nádobách súčasne, až dokým nedosiahne výšku 50, keď začne pretekať cez okraj nádoby 2 a hladina už ďalej stúpať nebude nikde.

Input:

5 6
30 50 70 40 90
300 280 290 210 110
1 2 220 200 230
3 4 100 120 170
3 4 130 60 150
4 5 160 190 260
1 5 180 250 270
4 2 140 80 240

Output:

4

Hoci je nádoba 5 najnižšia, voda sa do nej nedostane, skôr sa vyleje z nádoby 4.