题目描述

输入一个 $n$ 行 $n$ 列的数组 $a$，第 $i$ 行第 $j$ 列为 $a_{i,j}$。

有 $n$ 次操作。每次操作都会给你两个参数：$op,pos$：

• 如果 $op=1$，表示需要你对第 $pos$ 行排序（从左往右，小到大有序）。
• 如果 $op=2$，表示需要你对第 $pos$ 列排序（从上往下，小到大排序）。

然后有 $n$ 次询问。每次操作都会给你两个参数：$x,y$，你需要输出 $a_{x,y}$。

输入格式

第一行一个整数 $n$。

接下来 $n$ 行，每行为 $n$ 个整数。即 $a$ 数组。

接下来 $n$ 行，每行为 $2$ 个整数，即 $n$ 次操作。

接下来 $n$ 行，每行为 $2$ 个整数，即 $n$ 次询问。

输出格式

输出 $n$ 行，每行一个整数，即 $n$ 次询问的答案。

3
5 3 1
4 1 2
9 7 3
2 2
1 1
2 1
1 1
2 2
3 3

1
3
3

样例解释

原数组

5 3 1
4 1 2
9 7 3

2 2 操作后（第 2 列排序）

5 1 1
4 3 2
9 7 3

1 1 操作后（第 1 行排序）

1 1 5
4 3 2
9 7 3

2 1 操作后（第 1 列排序）

1 1 5
4 3 2
9 7 3

数据规模与约定

对于 $100\%$ 的数据，$1\le n\le 1000$，$1\le pos,x,y\le n$，$1\le op\le 2$，$1\le a_{i,j}\le 10^9$

• 子任务 1（30 分）：保证数组所有数都相等。
• 子任务 2（30 分）：保证 $1\le n\le 100$。
• 子任务 3（40 分）：没有特殊限制。