#include<bits/stdc++.h> #define int long long using namespace std; struct edge{ int from,to; }e[5000001];int head[5000001],size; vector<int> E[500001]; void addedge(int x,int y){ e[++size].to=y; e[size].from=head[x],head[x]=size; } int vis[10001],dis[10001]; void bfs(int s,int I,int t){ vis[s]=I; dis[s]=0; queue<int> q; q.push(s); while(!q.empty()){ int now=q.front();q.pop(); if(now==t) return ; for(int i=head[now];i;i=e[i].from){ int u=e[i].to; if(vis[u]!=I){ vis[u]=I; dis[u]=dis[now]+1; q.push(u); } } for(int u:E[now]){ if(vis[u]!=I){ vis[u]=I; dis[u]=dis[now]+1; q.push(u); } } } } bool A=1,B=1; int n,m; int X[200001],Y[200001]; struct Q{ int op,a,b,c,d; }q[200001]; int c[200001]; #define lb(x) (x&-x) void add(int x,int k){ while(x<=n){ c[x]+=k; x+=lb(x); } } int ask(int x){ if(!x) return 0; int ret=0; while(x){ ret+=c[x]; x-=lb(x); } return ret; } int ask(int l,int r){ if(l>r) return 0; return ask(r)-ask(l-1); } int f[200001][2]; //int f(int x,int y){ // return (x-1)*n+y; //} int solve(int x,int y,int xx,int yy){ if(max(x,y)==max(xx,yy)){ return abs(x-xx)+abs(y-yy); } int s=max(x,y),t=max(xx,yy); if(s>t) swap(x,xx),swap(y,yy),swap(s,t); if(y>x){ swap(x,y),swap(xx,yy); } int ans=0; ans+=abs(X[s]-y); ans+=(t-s)+ask(s,t-2); ans+=abs(t-xx)+abs(X[t-1]-yy); return ans; } signed main(){ // freopen("_.in","r",stdin); ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>n>>m; for(int i=1;i<n;i++){ cin>>X[i]>>Y[i]; if(X[i]!=Y[i]) B=0; } for(int i=1;i<=m;i++){ cin>>q[i].op; if(q[i].op==1) cin>>q[i].a>>q[i].b>>q[i].c,A=0; else cin>>q[i].a>>q[i].b>>q[i].c>>q[i].d; if(q[i].op==1&&q[i].b!=q[i].c) B=0; } if(B){ for(int i=1;i<n;i++){ add(i,abs(X[i]-X[i+1])); } for(int i=1;i<=m;i++){ if(q[i].op==1){ int pos=q[i].a; add(pos-1,-abs(X[pos-1]-X[pos])); add(pos,-abs(X[pos]-X[pos+1])); X[pos]=q[i].b; add(pos-1,abs(X[pos-1]-X[pos])); add(pos,abs(X[pos]-X[pos+1])); } else{ int x=q[i].a,y=q[i].b,xx=q[i].c,yy=q[i].d; int s=max(x,y); int ans; ans=min(solve(s,X[s],xx,yy)+abs(s-x)+abs(X[s]-y),solve(Y[s],s,xx,yy)+abs(Y[s]-x)+abs(s-y)); cout<<ans<<'\n'; } } } // else if(A){ // // } else{ for(int i=1;i<=m;i++){ if(q[i].op==1){ int pos=q[i].a; X[pos]=q[i].b; Y[pos]=q[i].c; } else{ int x=q[i].a,y=q[i].b,xx=q[i].c,yy=q[i].d; if(max(x,y)==max(xx,yy)){ cout<<abs(x-xx)+abs(y-yy)<<'\n';continue; } int s=max(x,y),t=max(xx,yy); if(s>t) swap(x,xx),swap(y,yy),swap(s,t); f[s][0]=abs(x-s)+abs(X[s]-y); f[s][1]=abs(Y[s]-x)+abs(s-y); for(int i=s+1;i<=t;i++){ // (i,X[i-1]), (Y[i-1],i) // (i,X[i]), (Y[i],i) f[i][0]=min(f[i-1][0]+1+abs(X[i-1]-X[i]),f[i-1][1]+1+abs(i-Y[i])+abs(X[i-1]-i)); f[i][1]=min(f[i-1][0]+1+abs(i-Y[i])+abs(X[i-1]-i),f[i-1][1]+1+abs(Y[i-1]-Y[i])); f[i][0]=min(f[i][0],f[i][1]+abs(i-Y[i])+abs(X[i]-i)); f[i][1]=min(f[i][1],f[i][0]+abs(i-Y[i])+abs(X[i]-i)); } // cout<<f[s][0]<<' '<<f[s][1]<<'\n'; // (xx,yy) (t,X[t-1]) (Y[t-1],t) cout<<min(f[t-1][0]+1+abs(xx-t)+abs(yy-X[t-1]),f[t-1][1]+1+abs(xx-Y[t-1])+abs(yy-t))<<'\n'; } } // for(int i=1;i<=n;i++){ // for(int j=1;j<i;j++){ // addedge(f(i,j),f(i,j+1)); // addedge(f(i,j+1),f(i,j)); // } // } // for(int j=1;j<=n;j++){ // for(int i=1;i<j;i++){ // addedge(f(i,j),f(i+1,j)); // addedge(f(i+1,j),f(i,j)); // } // } // for(int i=1;i<n;i++){ // E[f(i,X[i])].push_back(f(i+1,X[i])); // E[f(Y[i],i)].push_back(f(Y[i],i+1)); // } // for(int i=1;i<=m;i++){ // if(q[i].op==1){ // int pos=q[i].a; // E[f(pos,X[pos])].clear(); // E[f(Y[pos],pos)].clear(); // X[pos]=q[i].b,Y[pos]=q[i].c; // E[f(pos,X[pos])].push_back(f(pos+1,X[pos])); // E[f(Y[pos],pos)].push_back(f(Y[pos],pos+1)); // } // else{ // int x=q[i].a,y=q[i].b,xx=q[i].c,yy=q[i].d; // if(max(x,y)==max(xx,yy)){ // cout<<abs(x-xx)+abs(y-yy)<<'\n'; // continue; // } // int s=max(x,y),t=max(xx,yy); // if(s>t) swap(x,xx),swap(y,yy),swap(s,t); // if(y>x){ // swap(x,y),swap(xx,yy); // } // bfs(f(x,y),i,f(xx,yy)); // cout<<dis[f(xx,yy)]<<'\n'; // } // } } }