#P18338. RDDCCD

RDDCCD

RDDCCD

标准输入,标准输出。

陈教授发明了一种支持 RDDCCD(Reverse Diagonal Digits, Calculate Common Divisor,反转对角线数位并计算最大公约数)操作的数据结构。一次操作会将矩阵中某条对角线上的每一个数的十进制数位反转,然后计算整个矩阵中所有数的最大公约数。

例如,反转12345得到54321,反转2748得到8472。

这种数据结构暂时还是商业秘密。给定初始矩阵以及操作序列,请自行实现能够高效完成这些操作的程序。

矩阵的行、列编号均从1开始。用 ai,ja_{i,j} 表示第 ii 行、第 jj 列的数。每次操作由一个字符 opop 和一个整数 tt 表示:

  • 若 opop 为 +,反转所有满足 i+j=ti+j=t 的格子中的数;
  • 若 opop 为 -,反转所有满足 i−j=ti-j=t 的格子中的数。

操作会持续改变矩阵。每次反转完成后,求当前全部 n2n^2 个数的最大公约数。

输入格式

第一行包含两个整数 n,qn,q,分别表示方阵的边长和操作次数。

接下来 nn 行,每行包含 nn 个整数。第 ii 行第 jj 个整数为初始值 ai,ja_{i,j}。

接下来 qq 行,每行包含一个字符 opkop_k 和一个整数 tkt_k,表示第 kk 次操作。

输出格式

输出 qq 行,每行一个整数,表示相应操作完成后整个矩阵所有数的最大公约数。

不输出初始矩阵的最大公约数。

数据范围与保证

  • 1≤n≤10001\le n\le1000;
  • 1≤q≤1061\le q\le10^6;
  • 1≤ai,j<1091\le a_{i,j}<10^9;
  • 初始的每个数都不以0结尾,因此数位反转不会丢失位数;
  • opk∈{+,−}op_k\in\{+,-\},且 −n<tk<2n-n<t_k<2n;
  • 每次操作至少反转一个格子中的数。

上述最后两个条件须同时满足。按1开始的行列编号,它们意味着:+ 操作的 tt 满足 2≤t<2n2\le t<2n;- 操作的 tt 满足 1−n≤t≤n−11-n\le t\le n-1。特别地,n=1n=1 时可用的操作是 - 0。

本题只有一组矩阵,不含测试用例数。

样例输入 1

3 5
202 4 6
8 12 21
32 44 82
+ 2
+ 5
- 0
+ 4
- 2

样例输出 1

1
2
1
1
2