Zadanie

Jankine lístky

Počet bodov: 75

Janka už nie je študent. Ako neštudent už nemá právo na lístky na vlak zadarmo. A to je problém, pretože podľa budgetu (ktorý si tento týždeň usilovne pripravila), jej už neostane na knihy (ktoré sú na Slovensku luxusný tovar) od jej obľúbeného autora (ešte o tom nevie, ale je to Brandon Sanderson).

Našťastie má Janka aj riešenie. Všimla si, že keď si kúpite lístok z Bratislavy do Trenčína, lístok z Trenčína do Žiliny a lístok zo Žiliny do Kraľovian, tak v súčte tieto lístky stoja menej ako keď si kúpite lístok priamo z Bratislavy do Kraľovian. Ak ju niekedy stretnete, môžete sa jej spýtať, ako to zistila.

Teraz by Janku zaujímalo, či dokáže podobným spôsobom ušetriť aj na iných úsekoch jej obľúbenej trasy. Potrebuje totiž kúpiť maslo.

Úloha

Pri tejto úlohe skúmame ceny dopravy na jednej vlakovej linke v jednom smere.

Na vstupe dostaneme číslo \(N\) označujúce počet staníc na vlakovej linke. Stanice sú číslované od \(1\) (východisková stanica) po \(N\) (konečná stanica). Ďalej dostanete pre každú dvojicu staníc cenu lístka medzi nimi (v jednom smere).

Vašou úlohou bude pre \(M\) rôznych dvojíc staníc zistiť, koľko stojí najlacnejšia cesta medzi nimi.

Nie vždy platí, že priamy lístok medzi stanicami \(a\) a \(b\) je najlacnejšia voľba. Môže sa totiž stať, že keď nejaký úsek rozbijeme na podúseky, súčet cien lístkov na týchto podúsekoch je menší ako lístok pre celý úsek.

Niekedy najoptimálnejšia cena môže dokonca zahŕňať lístky, ktoré sa prekrývajú alebo zasahujú mimo skúmaný úsek. Napríklad si kúpite lístok zo stanice \(2\) do \(5\) a lístok zo stanice \(4\) do \(9\) a je to najlacnejšie možné kombo na cestovanie zo stanice \(3\) do \(8\).

Vstup a Výstup

Prvý riadok vstupu obsahuje kladné celé číslo \(N\) - počet miest.

Nasledujúcich \(N - 1\) riadkov popisuje ceny lístkov: \(k\)-ty z týchto riadkov obsahuje \(N - k\) medzerou oddelených celých čísel \(c_{k,l} (k < l \leq N)\). Tieto čísla reprezentujú ceny priamych lístkov zo stanice \(k\) do každej z nasledovných staníc. Platí, že \(0 < c_{k,l} < 2 000 000 000\).

Ďalší riadok obsahuje kladné celé číslo \(M\) - počet dopytov.

Nasledujúcich \(M\) riadkov popisuje jednotlivé dopyty: \(i\)-ty z týchto riadkov obsahuje dve medzerou oddelené celé čísla \(a_i\) a \(b_i\) (\(1 \leq a_i < b_i \leq N\)), reprezentujúce začiatočnú a cieľovú stanicu.

Na výstup vypíšte \(M\) riadkov, každý obsahujúci jedno kladné celé číslo \(r_i\) - najmenšiu možnú cenu za lístky, ktoré nám pokryjú celú cestu zo stanice \(a_i\) do stanice \(b_i\).

Body za túto úlohu sú rozdelené do 5 sád po 15 bodov podľa nasledovných kritérií:

1. \(N = 15\), \(M = 1\), pýtame sa na celý úsek a je zaručené, že v optimálnej trase sa lístky neprekrývajú

2. \(N = 15\), \(M = 1\), pýtame sa na celý úsek

3. \(N = 40\), \(M = 780\)

4. \(N = 1500\), \(M = 5\)

5. \(N = 350\), \(M = 61075\)

Príklad

Input:

4
22 31 60
14 28
30
3
1 4
1 3
3 4

Output:

50
31
28

Pri prvom dopyte sa nám oplatí kúpiť lístok zo stanice 1 do stanice 2 za 22 a potom lístok z 2 do 4 za 28.

Pri druhom dopyte je najlacnejší priamy lístok z 1 do 3 za 31.

Pri treťom dopyte by nás priamy lístok z 3 do 4 stál 30, ale ak si kúpime dlhší lístok z 2 do 4, bude nás stáť menej.

Input:

5
11 18 27 40
7 16 29
9 22
13
4
1 5
2 4
1 3
3 5

Output:

40
16
18
22

V tomto prípade sú ceny lístkov konzistentné, takže je nám úplne jedno, ako si lístky kupujeme.