#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) { 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++) 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 p) { node S = {p,a[p]},T = {p+1,a[p]}; if(w(S) != w(T)) { t[x].s[0] = S; t[x].t[0] = T; t[x].d[0][0] = 1; } else { t[x].d[0][0] = inf; } S = {b[p],p}; T = {b[p],p+1}; if(w(S) != w(T)) { t[x].s[1] = S; t[x].t[1] = T; t[x].d[1][1] = 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,p); 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; scanf("%lld%lld%lld%lld",&a,&b,&c,&d); node s = {a,b},t = {c,d}; int 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 I = 0;I < 2;I++) for(int J = 0;J < 2;J++) ans = min(ans,dis(s,now.s[I])+now.d[I][J]+dis(now.t[J],t)); 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; }