#include <bits/stdc++.h>
typedef long long ll;
const ll inf = 1e15;
struct Query {
ll a, b, c, d;
int i;
};
template <typename T> class SparseTable {
public:
int max_p;
std::vector<T> orig;
std::vector<std::vector<T>> min, max;
SparseTable(const std::vector<T> &x) : orig(x) {
const int n = x.size();
max_p = std::floor(std::log2(n));
min = std::vector(max_p + 1, std::vector<T>(n));
max = std::vector(max_p + 1, std::vector<T>(n));
for (int i = 0; i < n; ++i) {
min[0][i] = max[0][i] = x[i];
}
for (int p = 1; p <= max_p; ++p) {
for (int i = 0; i < n - (1 << (p - 1)); ++i) {
min[p][i] = std::min(min[p - 1][i], min[p - 1][i + (1 << (p - 1))]);
max[p][i] = std::max(max[p - 1][i], max[p - 1][i + (1 << (p - 1))]);
}
}
}
T query_min(int a, int b) {
if (a == b) {
return orig[a];
}
int p = std::ceil(std::log2(b - a + 1)) - 1;
return std::min(min[p][a], min[p][b - (1 << p) + 1]);
}
T query_max(int a, int b) {
if (a == b) {
return orig[a];
}
int p = std::ceil(std::log2(b - a + 1)) - 1;
return std::max(max[p][a], max[p][b - (1 << p) + 1]);
}
};
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);
std::vector<ll> orig_max(n), orig_min(n);
for (int i = 0; i < n; ++i) {
orig_max[i] = l[i] - i;
orig_min[i] = r[i] - i - 1;
}
SparseTable<ll> table_max(orig_max), table_min(orig_min);
auto binary_search = [&](int i, ll t) -> std::pair<ll, ll> {
int idx1 =
*std::ranges::partition_point(std::views::iota(i, n), [&](int j) {
return table_max.query_max(i, j) <= t - i;
}); // first index such that l <= t_then is not true
int idx2 =
*std::ranges::partition_point(std::views::iota(i, n), [&](int j) {
return t - i <= table_min.query_min(i, j);
}); // first index such that t_then <= r-1 is not true
return {idx1, idx2};
};
int lim = std::log2(n) + 1;
std::vector jump(n + 1,
std::vector(2, std::vector<std::pair<int, int>>(lim)));
std::vector cost(n + 1, std::vector(2, std::vector<ll>(lim)));
// jump[{i, j}][bt] = {i, j}
// cost[{i, j}][bt] = x
// base cases for binary lift
jump[n][0][0] = {n, 0}, jump[n][1][0] = {n, 1};
for (int i = 0; i < n; ++i) {
std::vector<ll> idx = {l[i], r[i] - 1};
for (int j = 0; j < 2; ++j) {
auto res = binary_search(i, idx[j]);
if (res.first < res.second) {
jump[i][j][0] = std::make_pair(res.first, 0LL);
} else {
jump[i][j][0] = std::make_pair(res.second, 1LL);
cost[i][j][0] =
std::max(0LL, idx[j] + (res.second - i) - (r[res.second] - 1));
}
}
}
for (int bt = 1; bt < lim; ++bt) {
for (int i = 0; i <= n; ++i) {
for (int j = 0; j < 2; ++j) {
auto dest = jump[i][j][bt - 1];
cost[i][j][bt] =
cost[i][j][bt - 1] + cost[dest.first][dest.second][bt - 1];
jump[i][j][bt] = jump[dest.first][dest.second][bt - 1];
}
}
}
auto bin_lift = [&](int i, int j,
int max_i) -> std::pair<std::pair<int, int>, ll> {
ll ans = 0;
for (int bt = lim - 1; bt >= 0; --bt) {
if (i + (1 << bt) >= n) {
continue;
}
if (jump[i][j][bt].first > max_i) {
continue;
}
ans += cost[i][j][bt];
auto dest = jump[i][j][bt];
i = dest.first, j = dest.second;
}
return {{i, j}, ans};
};
for (auto &[a, b, c, d, i] : queries) {
// process query
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] = bin_lift(res.first, 0, c - 1);
cost += cost_del;
b = dest.second == 0 ? l[dest.first] : r[dest.first] - 1;
b += (c - 1) - dest.first;
if (b > r[c - 1] - 1) {
cost += b - (r[c - 1] - 1);
b = r[c - 1] - 1;
}
cost += std::max(0LL, b + 1 - d);
} else {
b += res.second - a;
if (b > r[res.second] - 1) {
cost += b - (r[res.second] - 1);
b = r[res.second] - 1;
}
auto [dest, cost_del] = bin_lift(res.second, 1, c - 1);
cost += cost_del;
b = dest.second == 0 ? l[dest.first] : r[dest.first] - 1;
b += (c - 1) - dest.first;
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;
for (int i = 0, a, c, t; i < q; ++i) {
ll b, d;
std::cin >> t >> a >> b >> c >> d;
--a, --c;
if (a == c) {
ans[i] = std::max(0LL, b - d);
continue;
}
if (a < c) {
q1.push_back({a, b, c, d, i});
} else {
q2.push_back({n - a - 1, b, n - c - 1, d, i});
}
}
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 (auto &i : ans) {
std::cout << i << '\n';
}
}
