#include<bits/stdc++.h> #define int long long using namespace std; struct mat{ int a[3][3],n; mat(){a[1][1]=a[1][2]=a[2][1]=a[2][2]=1e18,n=2;} }; mat times(mat A,mat B){ mat ret; for(int i=1;i<=2;i++){ for(int j=1;j<=2;j++){ for(int k=1;k<=2;k++){ ret.a[i][j]=min(A.a[i][k]+B.a[k][j],ret.a[i][j]); } } } return ret; } mat tree[200001<<2]; int x[200001],y[200001]; #define ls (now<<1) #define rs (now<<1|1) #define mid ((l+r)>>1) void build(int now,int l,int r){ // cout<<now<<' '<<l<<' '<<r<<'\n'; if(l==r){ mat A; A.a[1][1]=1+abs(x[l]-x[l+1]); A.a[2][1]=1+abs(y[l]-l-1)+abs(l+1-x[l+1]); A.a[1][2]=1+abs(l+1-x[l])+abs(l+1-y[l+1]); A.a[2][2]=1+abs(y[l]-y[l+1]); tree[now]=A; return ; } build(ls,l,mid); build(rs,mid+1,r); tree[now]=times(tree[ls],tree[rs]); } mat ask(int now,int l,int r,int x,int y){ if(l>=x&&r<=y) return tree[now]; if(mid<x) return ask(rs,mid+1,r,x,y); if(mid>=y) return ask(ls,l,mid,x,y); else return times(ask(ls,l,mid,x,y),ask(rs,mid+1,r,x,y)); } void add(int now,int l,int r,int X){ if(l==r){ mat A; A.a[1][1]=1+abs(x[l]-x[l+1]); A.a[2][1]=1+abs(y[l]-l-1)+abs(l+1-x[l+1]); A.a[1][2]=1+abs(l+1-x[l])+abs(l+1-y[l+1]); A.a[2][2]=1+abs(y[l]-y[l+1]); tree[now]=A; return ; } if(mid>=X) add(ls,l,mid,X); else add(rs,mid+1,r,X); tree[now]=times(tree[ls],tree[rs]); } int f[200001][2],n,m; int len(int x,int y,int xx,int yy){ return abs(x-xx)+abs(y-yy); } signed main(){ // freopen("_.in","r",stdin); ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>n; cin>>m; for(int i=1;i<n;i++){ cin>>x[i]>>y[i]; } if(n>2) build(1,1,n-2); while(m--){ int op;cin>>op; int a,b,c,d; if(op==1){ cin>>a>>b>>c; x[a]=b,y[a]=c; if(a!=n-1) add(1,1,n-2,a); add(1,1,n-2,a-1); continue; } cin>>a>>b>>c>>d; int s=max(a,b); int t=max(c,d); if(s>t){ swap(s,t); swap(a,c),swap(b,d); } if(s==t){ cout<<len(a,b,c,d)<<'\n'; continue; } else if(s+1==t){ cout<<min(len(a,b,s,x[s])+1+len(t,x[t-1],c,d),len(a,b,y[s],s)+1+len(y[t-1],t,c,d))<<'\n'; // cout<<min(len(a,b,s,x[s])+1+len(a+1,x[s],c,d),len(a,b,y[s],s)+1+len(y[s],s+1,c,d))<<'\n'; continue; } mat A; A.a[1][1]=len(a,b,s,x[s]); A.a[1][2]=len(a,b,y[s],s); // for(int i=s;i<=t-2;i++){ // mat T; // T.a[1][1]=1+abs(x[i]-x[i+1]); // T.a[2][1]=1+abs(y[i]-i-1)+abs(i+1-x[i+1]); // T.a[1][2]=1+abs(i+1-x[i])+abs(i+1-y[i+1]); // T.a[2][2]=1+abs(y[i]-y[i+1]); // A=times(A,T); // // } A=times(A,ask(1,1,n-2,s,t-2)); int f0=A.a[1][1],f1=A.a[1][2]; int ans=1e9; ans=min(f0+1+len(t,x[t-1],c,d),f1+1+len(y[t-1],t,c,d)); cout<<ans<<'\n'; } } /* 4 1 1 1 1 2 1 2 2 3 2 1 3 5 2 4 4 3 4 4 3 3 1 2 3 3 2 2 4 4 1 4 2 3 */