陈教授发明了一种支持“反转对角线数字，计算公约数”（Reverse Diagonal Digits, Calculate Common Divisor，简称 RDDCCD）操作的新型数据结构。该操作会反转矩阵中某条对角线上所有数字的数位，并计算矩阵中所有数字的最大公约数。

反转一个数字的数位是指将该数字以十进制形式写出，并从右向左读取。例如，12345 应变为 54321，2748 应变为 8472。

然而，该数据结构目前是商业机密。为了突破技术封锁，你决定重新发明该数据结构。请编写一个程序来高效地处理这些查询。

输入格式

第一行包含两个整数 $n, q$ ($1 \le n \le 1000, 1 \le q \le 10^6$)，分别表示矩阵的大小和操作次数。

接下来的 $n$ 行，每行包含 $n$ 个整数 $a_{ij}$ ($1 \le a_{ij} < 10^9, 1 \le i, j \le n$)，表示矩阵中的数字。保证所有数字的末位均不为 0。

接下来的 $q$ 行，每行包含一个字符 $op_k$ 和一个整数 $t_k$ ($op_k \in \{+, -\}, -n < t_k < 2n$)，表示一次操作。如果 $op_k$ 为 $+$，则该操作反转所有满足 $i + j = t_k$ 的 $a_{ij}$ 的数位。否则，该操作反转所有满足 $i - j = t_k$ 的 $a_{ij}$ 的数位。保证每次操作至少有一个数字被反转。

输出格式

输出 $q$ 行，每行包含一个整数，表示每次查询后的结果。

样例

输入 1

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

输出 1

1
2
1
1
2