Državno natjecanje 2018. / Osnovna škola (7. razred) - 2. zadatak

Jednog lijepog subotnjeg jutra Aladin je šetao uz Bospor i sasvim slučajno na podu ugledao tablicu ispunjenu brojevima. Uze Aladin tu tablicu u ruke, pogladi ju, kad tamo začuje se glas s neba: “Aladine, sine Cassimov, pronašao si drevnu tablicu. Ako točno odgovoriš na mojih Q pitanja vezanih uz tu tablicu osvojit ćeš Fiat Multiplu kao nagradu.” Kako je Fiat Multipla Aladinov auto iz snova, zamolio je tebe da mu pomogneš odgovoriti na pitanja.

Tablica ima N redaka i M stupaca. Svako od Q pitanja je oblika: “Aladine, sortiraj od manjeg prema većem retke po stupcu A. Redak P je manji od retka D ako je vrijednost retka P u stupcu A manja od vrijednosti retka D u stupcu A. Nakon što si sortirao retke, ispiši vrijednost koja se nalazi na sjecištu retka X i stupca Y u sortiranoj tablici”.

ULAZNI PODATCI

U prvom retku nalaze se dva prirodna broja N i M (1 ≤ N, M ≤ 500). U sljedećih N redaka nalazi se po M prirodnih brojeva koji opisuju izgled tablice. Svaki od tih brojeva je manji od 1001. Niti u jednom stupcu neće se pojaviti dva ista broja.

U sljedećem retku nalazi se prirodan broj Q (1 ≤ Q ≤ 106).

U sljedećih Q redaka nalaze se po tri prirodna broja Ai, Xi i Yi (1 ≤ Ai, Yi ≤ M, 1 ≤ Xi ≤ N) koji opisuju ito pitanje.

IZLAZNI PODATCI

U Q redaka treba ispisati odgovore na pitanja.

PRIMJERI TEST PODATAKA

Ulaz

3 3
2 2 3
3 1 2
1 3 1
3
1 1 2
1 2 2
1 3 2

Izlaz

3
2
1

Ulaz

3 4
46 30 13 17
31 45 38 37
10 26 44 15
1
2 1 3

Izlaz

44

Ulaz

3 2
3 5
1 4
6 9
2
2 2 1
1 1 2

Izlaz

3
4

Objašnjenje

Opis drugog primjera: Nakon što tablicu sortiramo po pravilu iz teksta prema pitanju iz testa primjera, tablica izgleda:

Traženo polje je podebljano.