题目描述

盛隆同学刚学完C++的二维数组和函数部分，于是他自己写了2个函数对二维数组进行练习。两个函数如下：

int n, a[1005][1005];
// 注意，这里的n和数组a是全局变量
void f1() {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            int t = a[i][j];
            a[i][j] = a[j][i];
            a[j][i] = t;
        }
    }
}
void f2() {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n - i + 1; j++) {
            int t = a[i][j];
            a[i][j] = a[n-j+1][n-i+1];
            a[n-j+1][n-i+1] = t;
        }
    }
}

现给出一个 $n \times n$ 的矩阵 $a$，矩阵的行列下标均从 $1$ 开始，也就是说矩阵中的第 $i$ 行第 $j$ 列的元素保存在 $a[i][j]$ 中。

现在盛隆同学想要对矩阵 $a$ 进行 $Q$ 次操作，操作共有三种，参数分别如下：

• 1：调用函数 $f1$。
• 2：调用函数 $f2$。
• 3 x y：输出矩阵 $a$ 目前第 $x$ 行第 $y$ 列的元素。

输入格式

第一行两个整数 $n,Q$，表示矩阵的大小和操作的次数。

接下来 $n$ 行，每行 $n$ 个整数，表示矩阵 $a$。

接下来 $Q$ 行，每行一个操作，操作格式如题目描述。

输出格式

对于每个操作 3 x y，输出一行一个整数，表示矩阵 $a$ 目前第 $x$ 行第 $y$ 列的元素。

样例数据

输入样例 #1

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

输出样例 #1

8

原矩阵经过 $2$ 次操作后的矩阵如下：

9 8 7
6 5 4
3 2 1

所以 $a[1][2] = 8$。

输入样例 #2

4 4
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
1
3 1 2
2
3 2 3

输出样例 #2

5
10

数据范围

对于 $20\%$ 的数据，没有操作一和操作二，只有操作三。

对于 $50\%$ 的数据，$1 \le n \le 500$，$1 \le Q \le 100$。

对于 $100\%$ 的数据，$1 \le n \le 1000$，$1 \le Q \le 10000$， $0 \le a_{ij} \le 10^9$，$1 \le x,y \le n$。