Problem Description

You are given $n$ points $p_1,p_2,\dots,p_n$ on the 2D plane. You need to perform $q$ operations. Each operation is one of the following:

''$\texttt{1 k x y}$'' ($1 \leq k \leq n$, $1\leq x,y\leq 10^8$): Change the coordinate of the point $p_k$ into $(x,y)$.

''$\texttt{2 l r}$'' ($1 \leq l\leq r\leq n$): Find the minimum non-negative integer $R$ such that you can cover all the points $p_l,p_{l+1},\dots,p_r$ using a single circle whose radius is $R$.

Note that a point is considered to be covered if and only if it is inside the circle or on the border of the circle.

Input

The first line contains a single integer $T$ ($1 \leq T \leq 3$), the number of test cases. For each test case:

The first line of the input contains two integers $n$ and $q$ ($1 \leq n,q \leq 100\,000$), denoting the number of points and the number of operations.

In the next $n$ lines, the $i$-th line contains two integers $x_i$ and $y_i$ ($1\leq x_i,y_i\leq 10^8$), describing the coordinate of $p_i$.

Each of the next $q$ lines describes an operation in formats described in the statement above.

It is guaranteed that all the values of $x_i$, $y_i$, $x$, $y$ are chosen uniformly at random from integers in their corresponding ranges. The randomness condition does not apply to the sample test case, but your solution must pass the sample as well.

Output

For each query, print a single line containing an integer, denoting the minimum radius.

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

3
0
1
5