#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
const int64 INF64 = (int64)4e18;
// Giả định dạng input:
// N Q
// L1 R1
// L2 R2
// ...
// L_{N-1} R_{N-1}
//
// Sau đó Q dòng:
// type ...
// type = 1 i l r -> cập nhật đường i (1 <= i <= N-1): L_i = l, R_i = r
// type = 2 A B C D -> truy vấn: bắt đầu ở thành phố A vào thời B, đích C vào thời D
//
// Output: với mỗi truy vấn type=2 in ra số time-leap tối thiểu (non-negative) hoặc -1 nếu không thể.
// Hàm mô phỏng: bắt đầu thời điểm t0 tại thành phố A, cố gắng đi tới C.
// Returns earliest arrival time at city C if có thể, otherwise returns INF64 (không thể).
// Chúng ta dùng quy ước: để bắt đầu băng qua đường i vào thời t (đi từ i -> i+1),
// cần t trong [L[i], R[i]-1] (vì phải dùng khoảng [t,t+1] nằm trong [L_i, R_i]).
int64 earliest_arrival(int N, int A, int C, int64 t0, const vector<int64>& L, const vector<int64>& R) {
int64 t = t0;
if (A == C) return t; // ở đúng chỗ, có thể đợi tới D nếu cần
if (A < C) {
for (int i = A; i <= C-1; ++i) {
int64 Li = L[i];
int64 Ri = R[i] - 1; // tối đa start time cho phép
if (t > Ri) return INF64; // không kịp, vì đã vượt quá thời hạn cuối cùng để bắt đầu đi qua đường này
t = max(t, Li); // có thể đợi tới Li nếu cần
// bây giờ t in [Li, Ri], bắt đầu đi qua -> tới thành phố tiếp theo vào t+1
t = t + 1;
}
return t;
} else {
// đi trái: từ A -> A-1 -> ... -> C
// đường dùng khi đi từ x -> x-1 là đường index x-1
for (int i = A-1; i >= C; --i) {
int64 Li = L[i];
int64 Ri = R[i] - 1;
if (t > Ri) return INF64;
t = max(t, Li);
t = t + 1;
}
return t;
}
}
// Kiểm tra với k (số time-leap): có thể đạt tới (C,D) không?
bool can_with_k(int N, int A, int64 B, int C, int64 D, int64 k, const vector<int64>& L, const vector<int64>& R) {
int64 t0 = B - k;
int64 arrival = earliest_arrival(N, A, C, t0, L, R);
if (arrival == INF64) return false;
// nếu đến sớm hơn D thì có thể đợi tới D (chỉ được đợi tăng thời gian)
return arrival <= D;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N, Q;
if (!(cin >> N >> Q)) return 0;
// N thành phố, có N-1 đường 1..N-1
vector<int64> L(N), R(N); // we'll use indices 1..N-1, index 0 unused
for (int i = 1; i <= N-1; ++i) {
cin >> L[i] >> R[i];
}
while (Q--) {
int type;
cin >> type;
if (type == 1) {
int idx;
int64 l, r;
cin >> idx >> l >> r;
// cập nhật đường idx
L[idx] = l;
R[idx] = r;
} else if (type == 2) {
int A, C;
int64 B, D;
cin >> A >> B >> C >> D;
// Lower bound k: ít nhất phải có B - k <= D => k >= max(0, B-D)
int64 lb = 0;
if (B > D) lb = B - D;
// Nếu A == C: không cần đi đường nào, chỉ cần đảm bảo start time <= D
if (A == C) {
cout << lb << '\n';
continue;
}
// Exponential search để tìm high sao cho can_with_k(high) == true
int64 hi = max<int64>(1, lb);
// Cap hi to avoid infinite loop if impossible: cap at 4e18
bool found = false;
for (int iter = 0; iter < 62; ++iter) { // 62 iterations enough to cover up to ~4e18
if (can_with_k(N, A, B, C, D, hi, L, R)) { found = true; break; }
// tăng hi
if (hi > (INF64 / 2)) break;
hi = hi * 2;
}
if (!found) {
// thử thêm 1 lần với một giá trị rất lớn
if (!can_with_k(N, A, B, C, D, INF64/4, L, R)) {
cout << -1 << '\n';
continue;
} else {
hi = INF64/4;
}
}
// Binary search [lb, hi]
int64 lo = lb, ans = -1;
while (lo <= hi) {
int64 mid = lo + (hi - lo) / 2;
if (can_with_k(N, A, B, C, D, mid, L, R)) {
ans = mid;
hi = mid - 1;
} else lo = mid + 1;
}
if (ans == -1) cout << -1 << '\n';
else cout << ans << '\n';
} else {
// không hợp lệ theo giả định format
// ta có thể bỏ qua hoặc dừng
cerr << "Unknown query type: " << type << "\n";
return 0;
}
}
return 0;
}
