#pragma GCC optimize(3)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double db;
const double eps=1e-10;
const int maxn=1e5+5;
const int gs=50; 
struct point
{
    int x,y;
}a[maxn];
int n,m;
int Up[gs],Dw[gs],CC[gs];
int tup[maxn<<2][gs],tdw[maxn<<2][gs];
#define lson now<<1
#define rson now<<1|1
bool cmp_up(int x,int y)
{
    if(a[x].x==a[y].x) return a[x].y>a[y].y;
    return a[x].x<a[y].x;
}
int st[gs],top;
void merge_up(int *A,int *B,int *C)
{
    int posa=0,posb=0,posc=0; top=0;
    while(A[posa] && B[posb])
    {
        if(cmp_up(A[posa],B[posb]))
            CC[posc++]=A[posa++];
        else CC[posc++]=B[posb++];
    }
    while(A[posa]) CC[posc++]=A[posa++];
    while(B[posb]) CC[posc++]=B[posb++];
    // printf("0%d ",posc);
    for(int i=0;i<posc;i++)
    {
        point u=a[CC[i]];
        if(i && u.x==a[CC[i-1]].x) continue;
        while(top>1 && 1ll*(a[st[top]].y-a[st[top-1]].y)*(u.x-a[st[top]].x)<=1ll*(u.y-a[st[top]].y)*(a[st[top]].x-a[st[top-1]].x))
            top--;
        st[++top]=CC[i];
    }
    for(int i=1;i<=top;i++)
        C[i-1]=st[i];
    C[top]=0;
    // printf("%d\n",top);
}
bool cmp_dw(int x,int y)
{
    if(a[x].x==a[y].x) return a[x].y<a[y].y;
    return a[x].x<a[y].x;
}
void merge_dw(int *A,int *B,int *C)
{
    int posa=0,posb=0,posc=0; top=0;
    while(A[posa] && B[posb])
    {
        if(cmp_dw(A[posa],B[posb]))
            CC[posc++]=A[posa++];
        else CC[posc++]=B[posb++];
    }
    while(A[posa]) CC[posc++]=A[posa++];
    while(B[posb]) CC[posc++]=B[posb++];
    // printf("1%d ",posc);
    for(int i=0;i<posc;i++)
    {
        point u=a[CC[i]];
        if(i && u.x==a[CC[i-1]].x) continue;
        while(top>1 && 1ll*(a[st[top]].y-a[st[top-1]].y)*(u.x-a[st[top]].x)>=1ll*(u.y-a[st[top]].y)*(a[st[top]].x-a[st[top-1]].x))
            top--;
        st[++top]=CC[i];
    }
    for(int i=1;i<=top;i++)
        C[i-1]=st[i];
    C[top]=0;
    // printf("%d\n",top);
}
void pushup(int now)
{
    merge_up(tup[lson],tup[rson],tup[now]);
    merge_dw(tdw[lson],tdw[rson],tdw[now]);
}
void build(int now,int l,int r)
{
    if(l==r)
    {
        tup[now][0]=tdw[now][0]=r;
        tup[now][1]=tdw[now][1]=0;
        return;
    }
    int mid=l+r>>1;
    build(lson,l,mid);
    build(rson,mid+1,r);
    pushup(now);
}
void modify(int now,int l,int r,int pos)
{
    if(l==r) return ;
    int mid=l+r>>1;
    if(pos<=mid) modify(lson,l,mid,pos);
    else modify(rson,mid+1,r,pos);
    pushup(now);
}
void query(int now,int l,int r,int L,int R)
{
    if(l>=L && r<=R)
    {
        merge_up(Up,tup[now],Up);
        merge_dw(Dw,tdw[now],Dw);
        return;
    }
    int mid=l+r>>1;
    if(L<=mid) query(lson,l,mid,L,R);
    if(mid<R) query(rson,mid+1,r,L,R);
}
struct dpoint
{
    db x,y;
    dpoint () {}
    dpoint(db xx,db yy)
    {
        x=xx; y=yy;
    }
}b[gs<<1];
db dis(dpoint x,dpoint y)
{
    return sqrt((x.x-y.x)*(x.x-y.x)+(x.y-y.y)*(x.y-y.y));
}
dpoint center(dpoint x,dpoint y,dpoint z)
{
    db a1=y.x-x.x,b1=y.y-x.y,
     c1=(a1*a1+b1*b1)/2,a2=z.x-x.x,
     b2=z.y-x.y,c2=(a2*a2+b2*b2)/2,
     d=a1*b2-a2*b1;
    return dpoint(x.x+(c1*b2-c2*b1)/d,x.y+(a1*c2-a2*c1)/d);
}
int calc()
{
    int t=0,pos=0;
    while(Up[pos]) b[t++]=dpoint(a[Up[pos]].x,a[Up[pos]].y),pos++;
    pos=0; while(Dw[pos]) b[t++]=dpoint(a[Dw[pos]].x,a[Dw[pos]].y),pos++;
    // for(int i=0;i<t;i++) printf("%.2f %.2f\n",b[i].x,b[i].y);
    random_shuffle(b,b+t);
    dpoint O=b[0];
    db R=0.0;
    for(int i=1;i<t;i++) if(dis(b[i],O)>R+eps)
    {
        O=b[i]; R=0;
        for(int j=0;j<i;j++) if(dis(b[j],O)>R+eps)
        {
            O=dpoint((b[i].x+b[j].x)/2,(b[i].y+b[j].y)/2);
            R=dis(O,b[i]);
            for(int k=0;k<j;k++)
                if(dis(b[k],O)>R+eps)
                    O=center(b[k],b[i],b[j]),R=dis(O,b[i]);
        }
    }
    return ceil(R);
}
int main()
{
    // freopen("a.in","r",stdin);
    // freopen("a.out","w",stdout);
    int T; scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)
            scanf("%d%d",&a[i].x,&a[i].y);
        build(1,1,n);
        // int pos=0;
        // while(tup[1][pos]) printf("%d ",tup[1][pos]),pos++;
        // printf("\n");
        while(m--)
        {
            int opt,x,y; scanf("%d",&opt);
            if(opt==1)
            {
                scanf("%d",&x);
                scanf("%d%d",&a[x].x,&a[x].y);
                modify(1,1,n,x);
            }
            else
            {
                scanf("%d%d",&x,&y);
                Up[0]=Dw[0]=0;
                query(1,1,n,x,y);
                printf("%d\n",calc());
            }
        }
    }
    return 0;
}