#include <bits/stdc++.h>
typedef long long ll;
const ll inf = 1e15;
struct Query {
ll a, b, c, d;
int i, t;
};
template <typename T> class SegmentTree {
public:
std::vector<T> seg;
int n;
T idt;
std::function<T(T, T)> f = [](T a, T b) { return a + b; };
SegmentTree(int n) : n(n), idt(0) { seg.resize(4 * n, idt); }
SegmentTree(int n, const std::function<T(T, T)> &f, T idt)
: n(n), idt(idt), f(f) {
seg.resize(4 * n, idt);
}
T query(int v, int tl, int tr, int l, int r) {
if (tl > tr or l > r or tr < l or r < tl) {
return idt;
}
if (l <= tl and tr <= r) {
return seg[v];
}
int tm = (tl + tr) / 2;
return f(query(2 * v, tl, tm, l, r), query(2 * v + 1, tm + 1, tr, l, r));
}
T query(int l, int r) { return query(1, 0, n, l, r); }
void set(int v, int tl, int tr, int idx, T x) {
if (tl > tr or idx < tl or idx > tr) {
return;
}
if (tl == tr) {
seg[v] = x;
return;
}
int tm = (tl + tr) / 2;
set(2 * v, tl, tm, idx, x);
set(2 * v + 1, tm + 1, tr, idx, x);
seg[v] = f(seg[2 * v], seg[2 * v + 1]);
}
void set(int idx, T x) { set(1, 0, n, idx, x); }
// For a max segtree
int first_greater(int v, int tl, int tr, int i, T x) {
if (tr < i || seg[v] <= x) {
return n;
}
if (tl == tr) {
return tl;
}
int tm = (tl + tr) / 2;
int res = first_greater(2 * v, tl, tm, i, x);
if (res != n) {
return res;
}
return first_greater(2 * v + 1, tm + 1, tr, i, x);
}
int first_greater(int i, T x) { return first_greater(1, 0, n, i, x); }
// For a min segtree
int first_less(int v, int tl, int tr, int i, T x) {
if (tr < i || seg[v] >= x) {
return n;
}
if (tl == tr) {
return tl;
}
int tm = (tl + tr) / 2;
int res = first_less(2 * v, tl, tm, i, x);
if (res != n) {
return res;
}
return first_less(2 * v + 1, tm + 1, tr, i, x);
}
int first_less(int i, T x) { return first_less(1, 0, n, i, x); }
};
void solve(int n, int q, std::vector<ll> l, std::vector<ll> r,
std::vector<Query> queries, std::vector<ll> &ans) {
l.push_back(inf);
r.push_back(inf + 1);
SegmentTree<ll> max(n, [&](ll a, ll b) { return std::max(a, b); }, -inf);
SegmentTree<ll> min(n, [&](ll a, ll b) { return std::min(a, b); }, inf);
for (int i = 0; i < n; ++i) {
max.set(i, l[i] - i);
min.set(i, r[i] - i - 1);
}
auto binary_search = [&](int i, ll t) -> std::pair<ll, ll> {
int idx1 = max.first_greater(i, t - i);
int idx2 = min.first_less(i, t - i);
return {idx1, idx2};
};
std::vector<int> jump(2 * n + 2);
std::vector<ll> cost(2 * n + 2);
jump[2 * n] = 2 * n, jump[2 * n + 1] = 2 * n + 1;
const int block_sz = std::sqrt(2 * n + 2);
std::vector<int> jump_block(2 * n + 2);
std::vector<ll> cost_block(2 * n + 2);
// recalculates values for our block
auto recalculate = [&](int idx) {
int block_num = idx / block_sz;
for (int i = std::min(2 * n + 1, block_sz * (block_num + 1)) - 1;
i >= block_sz * block_num; --i) {
if (jump[i] >= std::min(2 * n + 1, block_sz * (block_num + 1))) {
jump_block[i] = jump[i];
cost_block[i] = cost[i];
} else {
jump_block[i] = jump_block[jump[i]];
cost_block[i] = cost_block[jump[i]] + cost[i];
}
}
};
// updates the values of jump and cost
auto set_base_cases = [&](int i, std::vector<ll> idx) {
for (int j = 0; j < 2; ++j) {
auto res = binary_search(i, idx[j]);
if (res.first < res.second) {
jump[2 * i + j] = 2 * res.first;
cost[2 * i + j] = 0;
} else {
jump[2 * i + j] = 2 * res.second + 1;
cost[2 * i + j] =
std::max(0LL, idx[j] + (res.second - i) - (r[res.second] - 1));
}
recalculate(2 * i + j);
}
};
// base cases
for (int i = 0; i < n; ++i) {
set_base_cases(i, {l[i], r[i] - 1});
}
auto query = [&](int i, int max_i) -> std::pair<int, ll> {
ll ans = 0;
while (jump_block[i] / 2 <= max_i) {
ans += cost_block[i];
i = jump_block[i];
}
while (jump[i] / 2 <= max_i) {
ans += cost[i];
i = jump[i];
}
return {i, ans};
};
for (auto &[a, b, c, d, i, t] : queries) {
// process query
if (t == 1) {
l[a] = b, r[a] = c;
max.set(a, l[a] - a);
min.set(a, r[a] - a - 1);
set_base_cases(a, {b, c - 1});
} else {
ll cost = 0;
auto res = binary_search(a, b);
if (c <= std::min(res.first, res.second)) {
b += c - a;
cost += std::max(0LL, b - d);
ans[i] = std::max(ans[i], cost);
continue;
}
if (res.first < res.second) {
b = l[res.first];
auto [dest, cost_del] = query(2 * res.first, c - 1);
cost += cost_del;
b = (dest & 1) == 0 ? l[(dest >> 1)] : r[(dest >> 1)] - 1;
b += (c - 1) - (dest >> 1);
} else {
b += res.second - a;
if (b > r[res.second] - 1) {
cost += b - (r[res.second] - 1);
}
auto [dest, cost_del] = query(2 * res.second + 1, c - 1);
cost += cost_del;
b = (dest & 1) == 0 ? l[(dest >> 1)] : r[(dest >> 1)] - 1;
b += (c - 1) - (dest >> 1);
}
if (b > r[c - 1] - 1) {
cost += b - (r[c - 1] - 1);
b = r[c - 1] - 1;
}
cost += std::max(0LL, b + 1 - d);
ans[i] = std::max(ans[i], cost);
}
}
}
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
int n, q;
std::cin >> n >> q;
std::vector<ll> l(n - 1), r(n - 1);
for (int i = 0; i < n - 1; ++i) {
std::cin >> l[i] >> r[i];
}
l.push_back(inf);
r.push_back(inf + 1);
std::vector<ll> ans(q);
std::vector<Query> q1, q2;
int j = 0;
for (int i = 0, t; i < q; ++i) {
ll a, b, c, d;
std::cin >> t;
if (t == 1) {
std::cin >> a >> b >> c;
--a;
q1.push_back({a, b, c, 0, 0, 1});
q2.push_back({a, b, c, 0, 0, 1});
} else {
std::cin >> a >> b >> c >> d;
--a, --c;
if (a == c) {
ans[j++] = std::max(0LL, b - d);
continue;
}
if (a < c) {
q1.push_back({a, b, c, d, j, 2});
} else {
q2.push_back({n - a - 1, b, n - c - 1, d, j, 2});
}
j++;
}
}
solve(n, q, l, r, q1, ans);
std::reverse(l.begin(), l.end() - 1);
std::reverse(r.begin(), r.end() - 1);
solve(n, q, l, r, q2, ans);
for (int i = 0; i < j; ++i) {
std::cout << ans[i] << '\n';
}
}
