给你一个含有 $n$ 个顶点和 $n(n - 1)$ 条边的带权有向图。对于任意一对不同的顶点 $1 \le i, j \le n$，存在一条边权为整数 $w(i, j)$ 的有向边，其中 $0 \le w(i, j) \le 2$。

请处理以下 $q$ 次操作：

• 1 a b：设 $dist(a, b)$ 为从顶点 $a$ 到顶点 $b$ 的最短有向路径长度（$1 \le a, b \le n$）。输出 $\min(dist(a, b), 2)$ 的值。
• 2 a b c：将 $w(a, b)$ 更新为 $c$（$1 \le a, b \le n, 0 \le c \le 2, a \ne b$）。

其中最多有 $2000$ 次类型 2 的操作。

输入格式

第一行包含两个整数 $n$ 和 $q$（$2 \le n \le 600, 1 \le q \le 10^6$）。

接下来的 $n$ 行，每行包含 $n$ 个整数。第 $i$ 行的第 $j$ 个整数为 $w(i, j)$（$0 \le w(i, j) \le 2$）。对于所有的 $i$，$w(i, i)$ 将被表示为 0，尽管实际上不存在这样的自环。

接下来的 $q$ 行，每行包含若干个整数，表示上述格式的操作。

保证至少有 1 次类型 1 的操作。

保证最多有 2000 次类型 2 的操作。

输出格式

对于每次类型 1 的操作，输出一个整数表示该操作的答案。每个答案应单独占一行。

样例

输入样例 1

5 10
0 1 2 2 2
2 0 2 2 2
2 2 0 1 2
2 2 2 0 2
2 2 2 2 0
1 1 2
1 2 1
1 1 3
1 1 4
1 4 5
1 5 5
2 4 5 0
1 4 5
1 2 5
1 1 5

输出样例 1

1
2
2
2
2
0
0
2
2