#include "bits/stdc++.h"
using namespace std;
#define fi first
#define se second
#define vi vector<int>
#define pb push_back
#define eb emplace_back
#define pii pair<int,int>
#define mp make_pair
#define rep( i , a , b ) for( int i = (a) , i##end = b ; i <= i##end ; ++ i )
#define per( i , a , b ) for( int i = (a) , i##end = b ; i >= i##end ; -- i )
#define mem( a ) memset( a , 0 , sizeof (a) )
#define all( x ) x.begin() , x.end()
//#define int long long
typedef long long ll;
const int MAXN = 2e5 + 10;
int n , q;

int sgn( double t ) {
	if( fabs( t ) < 1e-7 ) return 0;
	return t < 0 ? -1 : 1; 
}

struct poi {
	double x , y;
	void in() {
		int X , Y;
		scanf("%d%d",&X,&Y);
		x = X , y = Y;
	}
	poi( ) {}
	poi( int x , int y ) : x(x) , y(y) {}
} A[MAXN] ;

poi operator - ( const poi& a , const poi& b ) {
	return poi( a.x - b.x , a.y - b.y );
}
poi operator + ( const poi& a , const poi& b ) {
	return poi( a.x + b.x , a.y + b.y );
}

bool operator < ( const poi& a , const poi& b ) { // X first , Y second
    return !sgn( a.x - b.x ) ? sgn( a.y - b.y ) < 0 : sgn( a.x - b.x ) < 0;
}

double det( poi a , poi b ) {
	return a.x * 1ll * b.y - a.y * 1ll * b.x;
}

struct node {
	vector<poi> S;
	node operator + ( const node& A ) {
		if( !S.size() ) return A;
		if( !A.S.size() ) return *this;
		node res;
		res.S = S;
		res.S.insert( res.S.end() , A.S.begin() , A.S.end() );
		if( res.S.size() == 1 ) return res;
		sort( all( res.S ) );
		auto& V = res.S;
		int n = V.size() , cur = -1;
		vector<poi> ret( n * 2 );
		rep( i , 0 , n - 1 ) {
			while( cur > 0 && sgn( det( ret[cur] - ret[cur - 1] , V[i] - ret[cur - 1] ) ) <= 0 ) -- cur;
			ret[++ cur] = V[i];
		}
		int t = cur;
		per( i , n - 2 , 0 ) {
			while( cur > t && sgn( det( ret[cur] - ret[cur - 1] , V[i] - ret[cur - 1] ) ) <= 0 ) -- cur;
			ret[++ cur] = V[i];
		}
		ret.resize( cur );
		V = ret;
		return res;
	}
} T[MAXN << 2] ;

void build( int rt , int l , int r ) {
	if( l == r ) {
		T[rt].S.clear();
		T[rt].S.pb( A[l] );
		return;
	}
	int m = l + r >> 1;
	build( rt << 1 , l , m ) , build( rt << 1 | 1 , m + 1 , r );
	T[rt] = T[rt << 1] + T[rt << 1 | 1];
}

node que( int rt , int l , int r , int L , int R ) {
	if( L <= l && R >= r ) return T[rt];
	int m = l + r >> 1;
	node re;
	if( L <= m ) re = que( rt << 1 , l , m , L , R );
	if( R > m ) re = re + que( rt << 1 | 1 , m + 1 , r , L , R );
	return re;
}

void mdfy( int rt , int l , int r , int p , int x , int y ) {
	if( l == r ) {
		T[rt].S.pop_back();
		T[rt].S.eb( x , y );
		return;
	}
	int m = l + r >> 1;
	if( p <= m ) mdfy( rt << 1 , l , m , p , x , y );
	else mdfy( rt << 1 | 1 , m + 1 , r , p , x , y );
	T[rt] = T[rt << 1] + T[rt << 1 | 1];
}

std::mt19937 rnd(std::chrono::system_clock::now().time_since_epoch().count());

double dis( const poi& a , const poi& b ) {
	return hypot( a.x - b.x , a.y - b.y );
}

double det( double a , double b , double c , double d ) {
	return a * d - b * c;
}

poi cent( const poi& a , const poi& b , const poi& c ) {
	double a1 = ( a.x * a.x + a.y * a.y ) / 2;
	double b1 = ( b.x * b.x + b.y * b.y ) / 2;
	double c1 = ( c.x * c.x + c.y * c.y ) / 2;
	poi ret;
	double fr = det( b.x , b.y , c.x , c.y ) - det( a.x , a.y , c.x , c.y ) + det( a.x , a.y , b.x , b.y );
	ret.x = det( b1 , b.y , c1 , c.y ) - det( a1 , a.y , c1 , c.y ) + det( a1 , a.y , b1 , b.y );
	ret.y = det( b.x , b1 , c.x , c1 ) - det( a.x , a1 , c.x , c1 ) + det( a.x , a1 , b.x , b1 );
	ret.x /= fr , ret.y /= fr;
	return ret;
}

int getans( const node& S ) {
	auto A = S.S;
	shuffle( all( A ) , rnd );
	int n = A.size();
	poi C = A[0]; double r = 0;
	rep( i , 1 , n - 1 ) if( sgn( dis( A[i] , C ) - r ) > 0 ) {
		C = A[i] , r = 0;
		rep( j , 0 , i - 1 ) if( sgn( dis( A[j] , C ) - r ) > 0 ) {
			C = A[i] + A[j]; C.x /= 2 , C.y /= 2;
			r = dis( C , A[j] );
			rep( k , 0 , j - 1 ) if( sgn( dis( A[k] , C ) - r ) > 0 ) {
				C = cent( A[i] , A[j] , A[k] );
				r = dis( A[i] , C );
			}
		}
	}
	return ceil( r );
}

void solve() {
//	poi re = cent( poi( 1 , 1 ) , poi( 2 , 2 ) , poi( 3 , 1 ) );
//	cout << re.x << ' ' << re.y << endl;
	cin >> n >> q;
	rep( i , 1 , n ) A[i].in();
	build( 1 , 1 , n );
	rep( i , 1 , q ) {
		int op , l , r , x , y;
		scanf("%d",&op);
		if( op == 1 ) {
			scanf("%d%d%d",&l,&x,&y);
			mdfy( 1 , 1 , n , l , x , y );
		} else {
			scanf("%d%d",&l,&r);
			node re = que( 1 , 1 , n , l , r );
//			for( poi s : re.S ) {
//				printf("%lf %lf\n",s.x,s.y);
//			}
			printf("%d\n",getans( re ) );
		}
	}
}

signed main() {
//	freopen("in","r",stdin);
//	freopen("out","w",stdout);
	int T;cin >> T;while( T-- ) solve();
//	solve();
}