问题描述

本题读入量较大，请选择合理的读入方式

给定一个 $n\times n$ 的矩阵 $a,b$，整数 $k$，矩阵 $a$ 每行每列都是 $1$ 到 $n$ 的排列。有 $q$ 次操作，为如下操作之一：

• X x 将矩阵 $a,b$ 每行向右循环移位 $x$ 格。
• Y x 将矩阵 $a,b$ 每列向右循环移位 $x$ 格。
• I $b_{i,j}\rightarrow b_{i,a_{i,j}}$ ，同时将 $a$ 矩阵每行变成原来的逆排列。
• C $b_{i,j}\rightarrow b_{a_{i,j},j}$ ，同时将 $a$ 矩阵每列变成原来的逆排列。
• Q 查询最小的 $x$ 符合以下条件：

对于任意 $1\le y\le n,y\not=x$，满足 $\sum_{i=1}^n[b_{x,i}= b_{y,i}]=k$。

输入格式

第一行三个整数 $n,k,q$ 。

第 $2∼n+1$ 行每行n个整数表示矩阵 $a$。

第 $n+2∼2n+1$ 行每行 $n$ 个整数表示矩阵 $b$。

第 $2n+2∼2n+q+1$ 行，每行代表一次操作。

输出格式

对于每次 $Q$ 询问输出答案。

1.in

2 1 10
1 2
2 1
1 1
1 2
Y 1
I
Q
X 1
Q
I
C
Q
Q
C

1.ans

1
1
1
1

2.in/2.ans 见下发文件。

$1\le n\le2000,1\le k,b_{i,j}\le n,1\le x < n , 1 \le q\le10^6$

特殊性质：保证没有操作 I,C。

下发文件