Se dă o matrice cu numere naturale nenule, pătratică, cu liniile şi coloanele numerotate de la 1 la N. Fiecare număr din matrice reprezintă înălţimea unui pilon plasat în acea poziţie.

Putem plasa un observator „sub” matrice (adică pe o poziţie i j cu i > N şi 1 ≤ j ≤ N), de unde poate vedea în trei direcţii:

• nord (pe coloana j);
• nord-vest (elemente din matrice de pe poziţii is,js cu i - is = j - js, dacă există astfel de elemente);
• nord-est (elemente din matrice de pe poziţii is,js cu i - is = js - j, dacă există astfel de elemente);

Plasat într-o poziţie şi privind pe una dintre direcţii, observatorul poate vedea doar pilonii pe care nu îi separă de observator niciun pilon cu înălţimea mai mare şi nici egală. În exemplul alăturat avem o matrice cu 5 linii şi 5 coloane. Observatorul de pe poziţia (6,1) va vedea pe direcţia nord doar pilonii de înălţimi 1, 2 şi 5 (celulele haşurate), iar în direcţia nord-est, doar pilonul cu înălţimea 7.

Observatorul de pe poziţia (8,1) va vedea pe direcţia nord de asemenea pilonii de înălţimi 1, 2 şi 5, iar în direcţia nord-est, pilonii de înălţimi 1 şi 4.

Cerinţa

Se cunoaşte configuraţia matricei şi mai multe poziţii posibile ale observatorului. Să se determine, pentru fiecare poziţie, numărul de piloni pe care îi vede observatorul plasat acolo.

Date de intrare

Fişierul matrice1.in are pe prima linie un număr natural N, dimensiunea matricei. Pe fiecare din următoarele N linii se găsesc câte N numere naturale. Numerele de pe aceeaşi linie se separă prin câte un spaţiu.

Pe linia următoare se găseşte un număr Q care reprezintă numărul de poziţii ale observatorului. Pe fiecare dintre următoarele Q linii sunt câte 2 numere naturale, separate printr-un un spaţiu, reprezentând o poziţie a observatorului (mai întâi linia, apoi coloana).

Date de ieşire

Fişierul matrice1.out va avea Q linii. Pe fiecare linie se găseşte numărul de piloni văzuţi de observator din fiecare poziţie a sa, în ordinea dată în fişierul de intrare.

Restricţii

• 2 ≤ N ≤ 500
• 1 ≤ Q ≤ 500.000
• Elementele matricei sunt numere naturale cuprinse între 1 şi 30.000 (inclusiv)
• Pentru fiecare poziţie i,j a observatorului avem N + 1 ≤ i ≤ 2 * N şi 1 ≤ j ≤ N;

Exemplu

matrice1.in

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

matrice1.out

4
5
7

Explicaţie

Pentru prima poziţie, 6, 1 observatorul vede 3 piloni în direcţia nord şi un pilon în direcţia nord-est, în total 4.