Start

2020-03-21 03:00 AKDT

Alfa 2020

End

2020-03-21 08:00 AKDT
The end is near!
Contest is over.
Not yet started.
Contest is starting in -109 days 17:27:48

Time elapsed

5:00:00

Time remaining

0:00:00

Problem T
Veður

/problems/iceland.vedur/file/statement/is/img-0001.jpg
Mynd fengin af commons.wikimedia.org
Eins og oft áður er aftur komin bládoppótt veðurviðvörun á höfuðborgarsvæðinu svo fólk þarf að hafa varann á þegar það ferðast um. Þar sem ofurtölva veðurstofunnar fauk burt þarf að aðstoða þá við að plana ferðir borgarbúa.

Tákna má vindspá fyrir höfuðborgarsvæðið með tvívíðu korti af reitum þar sem hver tala inniheldur vindhraðann á þeim reit. Þar sem veðrið er svona slæmt finnst fólki í lagi að fara lengri leiðir en vanalega til að komast á leiðarenda, en það vill bara komast á leiðarenda í sem minnstum vindi. Það er hægt að ferðast milli aðlægra reita á kortinu (upp, niður, hægri og til vinstri en ekki á ská) og vill fólk fara leiðina sem lágmarkar hæsta vindstigið sem það verður fyrir á leiðinni.

Áður en ofurtölva veðurstofunnar fauk burt var búið að finna út úr því hvaða leið allir áttu að fara, en það glötuðust upplýsingarnar um hvað mesta vindstigið yrði á leiðinni. Þar sem fólk þarf að vita hversu undirbúið það þarf að vera þarf að finna út úr þessu.

Inntak

Fyrsta línan í inntakinu inniheldur tvær heiltölur $n$ og $m$ ($1 \leq n, m \leq 10^5$), hæð og breidd kortsins. Einnig gildir að $1 \leq n\cdot m \leq 10^5$.

Síðan koma $n$ línur, hver með $m$ tölum $v_{i,j}$ ($1 \leq v_{i,j} \leq 10^{18}$), sem tákna vindhraðann á reit kortsins í línu $i$ og dálki $j$.

Næst kemur ein lína með heiltölu $q$ ($1 \leq q \leq 10^5$) sem er fjöldi einstaklinga sem þurfa að fá að vita mesta vindstig sem þeir verða fyrir.

Loks fylgja $q$ línur með fjórum heiltölum hver $l_1, d_1, l_2, d_2$ ($1 \leq l_1, l_2 \leq n$ og $1 \leq d_1, d_2, \leq m$). Þetta táknar fyrirspurn um mesta vindstig sem einstaklingur verður fyrir á leiðinni frá reitnum í línu $l_1$ og dálki $d_1$ yfir á reitinn í línu $l_2$ og dálki $d_2$.

Úttak

Fyrir hverja fyrirspurn í inntakinu, skrifið út eina línu með heiltölu sem táknar mesta vindstigið sem einstaklingurinn þarf að þola ef hann velur leiðina á sem bestan hátt.

Stigagjöf

Hópur

Stig

Takmarkanir

1

30

$q = 1$

2

30

$l_1 = d_1 = 1$

3

40

Engar frekari takmarkanir

Sample Input 1 Sample Output 1
3 4
3 4 2 2
9 9 9 8
1 1 1 3
4
3 1 3 3
1 1 3 1
1 1 1 4
2 2 2 2
1
8
4
9