{"code":"icpc21lexmatrix","name":"Lexigraphical Matrix","description":"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\r\nare 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$.\r\n\r\nLex Matrix A is considered greater than Lex Matrix B if compare each cell starting from the first row, left to right\r\nthen 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.\r\n\r\nGiven a Lex Matrix $A$, You are allowed to pick 2 rows/columns, swap them and repeat by picking again as many\r\ntimes as you want, modify to achieve the greatest possible Lex Matrix from $A$. Let’s call this maximal matrix A'.\r\n\r\nGiven 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}$\r\n\r\n

Input

\r\n\r\n- The first line of input contains 2 integers $m$ and $n (1 \\le m, n \\le 500)$.\r\n- The next $m$ lines, representing Lex Matrix $A$, each contains $n$ numbers, a permutation of $1, 2, ..., n$.\r\n- The next line contains one integer $q (1 \\le q \\le 10000)$.\r\n- 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)$.\r\n\r\n

Output

\r\n\r\n- Output $q$ lines, each contains one integer, the value of $A'_{x_i,y_i}$.\r\n\r\n

Example

\r\n\r\n!!! question \"Test 1\"\r\n\r\n ???+ \"Input\"\r\n ```sample\r\n 2 3\r\n 1 2 3\r\n 1 2 3\r\n 2\r\n 1 1\r\n 2 3\r\n ```\r\n \r\n ???+ success \"Output\"\r\n ```sample\r\n 3\r\n 1\r\n ```","points":400.0,"partial":false,"time_limit":1.0,"memory_limit":262144,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}