给定二维平面上的 $n$ 个点 $p_1, p_2, \dots, p_n$。你需要执行 $q$ 次操作。每次操作为以下两种之一：

• “1 k x y” ($1 \le k \le n, 1 \le x, y \le 10^8$)：将点 $p_k$ 的坐标修改为 $(x, y)$。
• “2 l r” ($1 \le l \le r \le n$)：求最小的非负整数 $R$，使得存在一个半径为 $R$ 的圆可以覆盖点 $p_l, p_{l+1}, \dots, p_r$。注意，当且仅当一个点位于圆内或圆周上时，称该点被覆盖。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 3$)，表示测试用例的数量。对于每个测试用例：

第一行包含两个整数 $n$ 和 $q$ ($1 \le n, q \le 100\,000$)，分别表示点的数量和操作的数量。

接下来的 $n$ 行中，第 $i$ 行包含两个整数 $x_i$ 和 $y_i$ ($1 \le x_i, y_i \le 10^8$)，描述点 $p_i$ 的坐标。

接下来的 $q$ 行，每行描述一个上述格式的操作。

保证所有 $x_i, y_i, x, y$ 的值均在各自范围内均匀随机生成。随机性条件不适用于样例测试，但你的程序必须通过样例。

输出格式

对于每次查询，输出一行一个整数，表示最小半径。

样例

输入 1

1
5 5
1 1
2 2
3 1
3 3
2 5
2 1 5
2 1 1
2 1 2
1 1 10 1
2 1 5

输出 1

3
0
1
5