#include<bits/stdc++.h> #define ls (x<<1) #define rs (x<<1)|1 #define fi first #define se second using namespace std; typedef long long LL; typedef pair<int,int> PII; const int N = 200005; int n,m; struct matrix { LL a[2][2]; inline matrix(LL a00 = 0,LL a01 = 0,LL a10 = 0,LL a11 = 0) { a[0][0] = a00; a[0][1] = a01; a[1][0] = a10; a[1][1] = a11; } inline matrix operator*(matrix b) { return matrix(min(a[0][0]+b.a[0][0],a[0][1]+b.a[1][0]), min(a[0][0]+b.a[0][1],a[0][1]+b.a[1][1]), min(a[1][0]+b.a[0][0],a[1][1]+b.a[1][0]), min(a[1][0]+b.a[0][1],a[1][1]+b.a[1][1])); } } a[N]; PII p[N][4]; int dis(PII &x,PII &y) { return abs(x.fi-y.fi)+abs(x.se-y.se); } inline void work(int i) { a[i] = matrix(dis(p[i][2],p[i+1][0])+1,dis(p[i][2],p[i+1][1])+1,dis(p[i][3],p[i+1][0])+1,dis(p[i][3],p[i+1][1])+1); } struct tree { int l,r; matrix s; }t[N<<2]; void build(int x,int l,int r) { t[x].l = l; t[x].r = r; if(l == r) { t[x].s = a[l]; return; } int mid = (l+r)>>1; build(ls,l,mid); build(rs,mid+1,r); t[x].s = t[ls].s*t[rs].s; } void update(int x,int p) { if(t[x].l == t[x].r) { t[x].s = a[p]; return; } int mid = (t[x].l+t[x].r)>>1; if(p <= mid) update(ls,p); else update(rs,p); t[x].s = t[ls].s*t[rs].s; } matrix query(int x,int l,int r) { if(l <= t[x].l && t[x].r <= r) return t[x].s; int mid = (t[x].l+t[x].r)>>1; if(r <= mid) return query(ls,l,r); if(mid < l) return query(rs,l,r); return query(ls,l,r)*query(rs,l,r); } int main() { scanf("%d%d",&n,&m); for(int i = 1;i < n;i++) { p[i][0].fi = p[i][1].se = i; scanf("%d%d",&p[i][0].se,&p[i][1].fi); p[i][2] = p[i][0]; p[i][3] = p[i][1]; p[i][2].fi++; p[i][3].se++; } for(int i = 1;i < n-1;i++) work(i); build(1,1,n-2); PII tmp[2]; for(int i = 1,opt,x,l,r;i <= m;i++) { scanf("%d",&opt); if(opt == 2) { scanf("%d%d%d%d",&tmp[0].fi,&tmp[0].se,&tmp[1].fi,&tmp[1].se); if(max(tmp[0].fi,tmp[0].se)>max(tmp[1].fi,tmp[1].se)) swap(tmp[0],tmp[1]); l = max(tmp[0].fi,tmp[0].se); r = max(tmp[1].fi,tmp[1].se); if(l == r) { printf("%d\n",dis(tmp[0],tmp[1])); continue; } matrix ans(dis(tmp[0],p[l][0]),dis(tmp[0],p[l][1])); if(l+1 < r) ans = ans*query(1,l,r-2); printf("%lld\n",min(ans.a[0][0]+dis(p[r-1][2],tmp[1]),ans.a[0][1]+dis(p[r-1][3],tmp[1]))+1); } else { scanf("%d%d%d",&x,&p[x][0].se,&p[x][1].fi); p[x][2] = p[x][0]; p[x][3] = p[x][1]; p[x][2].fi++; p[x][3].se++; if(x > 1) { work(x-1); update(1,x-1); } if(x < n-1) { work(x); update(1,x); } } } return 0; }