시간 제한메모리 제한제출정답맞힌 사람정답 비율
1.5 초 1024 MB44221760.714%

문제

(tu nedostaje neki tekst, zadatak će inače biti preumjetan, a postoji jedna jako lijepa, prikladna priča…)

Zadana je tablica prirodnih brojeva $P$ veličine $NxN$. Dobije se $M$ upita i na svaki upit za zadane $L$ i $R$ treba odgovoriti koliko iznosi $\max{(P[i][j])}$ gdje je $L ≤ i, j ≤ R$.

입력

U prvom su retku prirodni brojevi $N$ ($1 ≤ N ≤ 2\,000$) i $M$ ($1 ≤ M ≤ \min{(500\,000, N \times N)}$).

U sljedećih $N$ redaka nalazi se po $N$ prirodnih brojeva manjih od $1\,000\,000\,000$.

U zadnjih $M$ redaka nalaze se prirodni brojevi $L$ i $R$ ($1 ≤ L ≤ R ≤ N$).

출력

U $M$ redaka ispiši odgovore na tražene upite.

예제 입력 1

3 4
1 2 3
4 1 2
3 1 2
1 1
1 3
2 3
1 2

예제 출력 1

1
4
2
4

예제 입력 2

5 3
4 8 2 2 1
2 3 6 8 3
2 2 7 2 9
7 8 6 7 4
7 5 7 1 1
3 5
2 4
1 3

예제 출력 2

9
8
8

힌트

Opis prvog probnog primjera:

  1. upit: $\max{(P[1][1])}=1$
  2. upit: $\max{(P[1][1], P[1][2], P[1][3], P[2][1], P[2][2], P[2][3], P[3][1], P[3][2], P[3][3])}=4$
  3. upit: $\max{(P[2][2], P[2][3], P[3][2], P[3][3])}=2$
  4. upit: $\max{(P[1][1], P[1][2], P[2][1], P[2][2])}=4$