#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]; }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 k = 0;k < 2;k++) for(int p = 0;p < 2;p++) ret.d[i][j] = min(ret.d[i][j],l.d[i][k]+dis(l.t[k],r.s[p])+r.d[p][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 build(int x,int l,int r) { if(l == r) { 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]}; } else { t[x].s[0] = {inf,inf}; t[x].t[0] = {inf,inf}; } 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}; } else { t[x].s[1] = {inf,inf}; t[x].t[1] = {inf,inf}; } for(int i = 0;i < 2;i++) for(int j = 0;j < 2;j++) t[x].d[i][j] = dis(t[x].s[i],t[x].t[j]); 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) { 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]}; } else { t[x].s[0] = {inf,inf}; t[x].t[0] = {inf,inf}; } 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}; } else { t[x].s[1] = {inf,inf}; t[x].t[1] = {inf,inf}; } for(int i = 0;i < 2;i++) for(int j = 0;j < 2;j++) t[x].d[i][j] = dis(t[x].s[i],t[x].t[j]); 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); l = max(a,b); r = max(c,d); s = {a,b}; t = {c,d}; if(l > r) { swap(a,c); swap(b,d); swap(l,r); swap(s,t); } if(l == r) { printf("%lld\n",abs(a-c)+abs(b-d)); continue; } 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; }