#include<bits/stdc++.h> using namespace std; const int N = 2e5 + 5; int n, m; int x[N], y[N]; int op; int a, b, c, d; inline int dis(int a, int b, int c, int d){ return abs(a - c) + abs(b - d); } int dp[N][2]; int main(){ ios::sync_with_stdio(false); cin >> n >> m; for(int i = 1; i < n; ++ i){ cin >> x[i] >> y[i]; } while(m --){ cin >> op; if(op == 1){ cin >> a >> b >> c; x[a] = b; y[a] = c; } if(op == 2){ cin >> a >> b >> c >> d; int k1 = max(a, b); int k2 = max(c, d); if(k1 == k2){ cout << abs(a - c) + abs(b - d) << '\n'; continue; } if(k1 > k2){ swap(k1, k2); swap(a, c); swap(b, d); } // int ans = n * 2; // cout << k1 << ' ' << k2 << '\n'; // cout << a << ' ' << b << ' ' << c << ' ' << d << '\n'; dp[k1 + 1][0] = dis(a, b, k1, x[k1]) + 1; dp[k1 + 1][1] = dis(a, b, y[k1], k1) + 1; // cout << k1 + 1 << ": " << dp[k1 + 1][0] << ' ' << dp[k1 + 1][1] << '\n'; for(int i = k1 + 2; i <= k2; ++ i){ dp[i][0] = min(dp[i - 1][0] + dis(i - 1, x[i - 2], i - 1, x[i - 1]) + 1, dp[i - 1][1] + dis(y[i - 2], i - 1, i - 1, x[i - 1]) + 1); dp[i][1] = min(dp[i - 1][0] + dis(i - 1, x[i - 2], y[i - 1], i - 1) + 1, dp[i - 1][1] + dis(y[i - 2], i - 1, y[i - 1], i - 1) + 1); // cout << i << ": " << dp[i][0] << ' ' << dp[i][1] << '\n'; } cout << min(dp[k2][0] + dis(k2, x[k2 - 1], c, d), dp[k2][1] + dis(y[k2 - 1], k2, c, d)) << '\n'; } } return 0; } /* 看数据范围就知道不能直接建图 到时候画图找找规律罢 敲，题意理解错了，x y 只连两个相邻的点 若想从第 k 层走到第 k + 1 层，只有 i = k 时，x y 两种选择 感觉 dp (i, x[i]) --> (i + 1, x[i]) (y[i], i) --> (y[i], i + 1) dp[k][0] 表示走到第 k 层 (k, x[k - 1]) 的位置时的最小答案 dp[k][1] 表示走到第 k 层 (y[k - 1], k) 的位置时的最小答案 dp[k][0] = min{dp[k - 1][0] + dis(), dp[k - 1][1] + dis()} 感觉还行，long long应该就不用开了 */