A Lex Matrix is a matrix of size \(m×n\), \(m\) rows, \(n\) columns. Rows are numbered from \(1\) to \(m\), top to bottom. Columns
are numbered from \(1\) to \(n\), left to right. $A_{x,y} is the \(y\)-th value on row \(x\). Each row is a permutation of \(1, 2, ..., n\).

Lex Matrix A is considered greater than Lex Matrix B if compare each cell starting from the first row, left to right
then to the next row and so on, the first pair of cells \((i, j)\) where \(A_{i,j} \ne B_{i,j} , A_{i,j} > B_{i,j}\) hold.

Given a Lex Matrix \(A\), You are allowed to pick 2 rows/columns, swap them and repeat by picking again as many
times as you want, modify to achieve the greatest possible Lex Matrix from \(A\). Let’s call this maximal matrix A'.

Given q pairs of number \(x_i\) and \(y_i (1 \le x_i \le m, 1 \le y_i \le n)\), find the value of \(A'_{x_i,y_i}\)

Input

• The first line of input contains 2 integers \(m\) and \(n (1 \le m, n \le 500)\).
• The next \(m\) lines, representing Lex Matrix \(A\), each contains \(n\) numbers, a permutation of \(1, 2, ..., n\).
• The next line contains one integer \(q (1 \le q \le 10000)\).
• The next q lines, each contains 2 integers \(x_i\) and \(y_i (1 \le x_i \le m, 1 \le y_i \le n)\).

Output

• Output \(q\) lines, each contains one integer, the value of \(A'_{x_i,y_i}\).

Example

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

3
1