#include<bits/stdc++.h> #define ls (x<<1) #define rs (x<<1)|1 #define int long long using namespace std; const int N = 2e5+2; int n,m,inf = 1e9+7; int a[N],b[N]; struct node { int x,y; }; struct sth { node s[2],t[2]; int d[2][2]; bool tag[2]; }t[N<<2]; int dis(node a,node b) { if(a.x >= inf || b.x >= inf || a.y >= inf || b.y >= inf) return inf; return abs(a.x-b.x)+abs(a.y-b.y); } int w(node a) { return max(a.x,a.y); } sth merge(sth l,sth r) { sth ret; for(int i = 0;i < 2;i++) for(int j = 0;j < 2;j++) ret.d[i][j] = inf; for(int i = 0;i < 2;i++) for(int j = 0;j < 2;j++) for(int I = 0;I < 2;I++) for(int J = 0;J < 2;J++) ret.d[i][j] = min(ret.d[i][j],l.d[i][I]+dis(l.t[I],r.s[J])+r.d[J][j]); ret.s[0] = l.s[0]; ret.s[1] = l.s[1]; ret.t[0] = r.t[0]; ret.t[1] = r.t[1]; return ret; } void update(int x,int l) { if(w({l,a[l]}) != w({l+1,a[l]})) { t[x].s[0] = {l,a[l]}; t[x].t[0] = {l+1,a[l]}; t[x].tag[0] = 1; } else t[x].tag[0] = 0; if(w({b[l],l}) != w({b[l],l+1})) { t[x].s[1] = {b[l],l}; t[x].t[1] = {b[l],l+1}; t[x].tag[1] = 1; } else t[x].tag[1] = 0; if(t[x].tag[0]) t[x].d[0][0] = dis(t[x].s[0],t[x].t[0]); else t[x].d[0][0] = inf; if(t[x].tag[1]) t[x].d[1][1] = dis(t[x].s[1],t[x].t[1]); else t[x].d[1][1] = inf; t[x].d[1][0] = t[x].d[0][1] = inf; } void build(int x,int l,int r) { if(l == r) { update(x,l); return; } int mid = (l+r)>>1; build(ls,l,mid); build(rs,mid+1,r); t[x] = merge(t[ls],t[rs]); return; } sth ask(int x,int l,int r,int L,int R) { if(L <= l && r <= R) return t[x]; int mid = (l+r)>>1; if(L > mid) return ask(rs,mid+1,r,L,R); if(R <= mid) return ask(ls,l,mid,L,R); return merge(ask(ls,l,mid,L,R),ask(rs,mid+1,r,L,R)); } void modify(int x,int l,int r,int p) { if(l == r) { update(x,l); return; } int mid = (l+r)>>1; if(p <= mid) modify(ls,l,mid,p); else modify(rs,mid+1,r,p); t[x] = merge(t[ls],t[rs]); return; } signed main() { scanf("%lld%lld",&n,&m); for(int i = 1;i < n;i++) scanf("%lld%lld",&a[i],&b[i]); build(1,1,n-1); for(int i = 1;i <= m;i++) { int opt; scanf("%lld",&opt); if(opt == 2) { int a,b,c,d,l,r; node s,t; scanf("%lld%lld%lld%lld",&a,&b,&c,&d); s = {a,b}; t = {c,d}; l = w(s); r = w(t); if(l == r) printf("%lld\n",abs(a-c)+abs(b-d)); else { if(l > r) { swap(l,r); swap(s,t); } sth now = ask(1,1,n-1,l,r-1); int ans = inf; for(int j = 0;j < 2;j++) for(int k = 0;k < 2;k++) ans = min(ans,dis(s,now.s[j])+now.d[j][k]+dis(t,now.t[k])); printf("%lld\n",ans); } } else { int x,y,z; scanf("%lld%lld%lld",&x,&y,&z); a[x] = y; b[x] = z; modify(1,1,n-1,x); } } return 0; }