#include <bits/stdc++.h>
typedef long long ll;
const ll inf = 1e15;
struct Query {
ll a, b, c, d;
int i;
};
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);
const int lim = std::log2(n) + 1;
std::vector ansl(n, std::vector<std::pair<ll, ll>>(lim)),
ansr(n, std::vector<std::pair<ll, ll>>(lim));
for (int i = 0; i < n; ++i) {
ansl[i][0] = {0, l[i] + 1};
ansr[i][0] = {0, r[i]}; // 0 jumps means we don't need anything
if (i != n - 1) {
ll v1 = std::max(0LL, ansl[i][0].second - (r[i + 1] - 1));
ll v2 = std::max(0LL, ansr[i][0].second - (r[i + 1] - 1));
ansl[i][0].first += v1;
ansr[i][0].first += v2;
ansl[i][0].second -= v1;
ansr[i][0].second -= v2;
}
}
auto _ansl = [&](int i, int x) -> std::pair<ll, ll> {
ll cost = 0, time = l[i];
for (int bt = 0; bt < lim; ++bt) {
if (x & (1 << bt)) {
cost += ansl[i][bt].first;
time = ansl[i][bt].second;
i += (1 << bt);
}
}
return {cost, time};
};
auto _ansr = [&](int i, int x) -> std::pair<ll, ll> {
ll cost = 0, time = r[i] - 1;
for (int bt = 0; bt < lim; ++bt) {
if (x & (1 << bt)) {
cost += ansr[i][bt].first;
time = ansr[i][bt].second;
i += (1 << bt);
}
}
return {cost, time};
};
std::vector jump_min(n, std::vector<ll>(lim)),
jump_max(n, std::vector<ll>(lim));
for (int i = 0; i < n; ++i) {
jump_max[i][0] = l[i] - i;
jump_min[i][0] = r[i] - i - 1;
}
for (int bt = 1; bt < lim; ++bt) {
for (int i = 0; i < n; ++i) {
jump_min[i][bt] = jump_min[i][bt - 1];
jump_max[i][bt] = jump_max[i][bt - 1];
if (i + (1 << (bt - 1)) < n) {
jump_min[i][bt] =
std::min(jump_min[i][bt], jump_min[i + (1 << (bt - 1))][bt - 1]);
jump_max[i][bt] =
std::max(jump_max[i][bt], jump_max[i + (1 << (bt - 1))][bt - 1]);
}
}
}
auto _ans = [&](int i, int x, ll t) -> std::pair<ll, ll> {
int idx1 = i;
ll max_val = l[i] - i;
for (int bt = lim - 1; bt >= 0; --bt) {
if (idx1 + (1 << bt) >= n) {
continue;
}
if (std::max(max_val, jump_max[idx1 + 1][bt]) <= t - i) {
max_val = std::max(max_val, jump_max[idx1 + 1][bt]);
idx1 += 1 << bt;
}
}
if (max_val <= t - i) {
idx1 = std::min(n, idx1 + 1);
}
int idx2 = i;
ll min_val = r[i] - i - 1;
for (int bt = lim - 1; bt >= 0; --bt) {
if (idx2 + (1 << bt) >= n) {
continue;
}
if (t - i <= std::min(min_val, jump_min[idx2 + 1][bt])) {
min_val = std::min(min_val, jump_min[idx2 + 1][bt]);
idx2 += 1 << bt;
}
}
if (t - i <= min_val) {
idx2 = std::min(n, idx2 + 1);
}
ll free_jumps = std::max(0, std::min(idx1, idx2) - i);
if (x <= free_jumps) {
ll del = std::max(0LL, t + x - (r[i + x] - 1));
return {del, t + x - del};
}
if (idx1 < idx2) {
auto p = _ansl(idx1, x - free_jumps);
return p;
} else {
auto p = _ansr(idx2, x - free_jumps);
return {t + free_jumps - (r[idx2] - 1) + p.first, p.second};
}
};
for (int bt = 1; bt < lim; ++bt) {
for (int i = 0; i + (1 << bt) < n; ++i) {
auto [ans1, t1] =
_ans(i + (1 << (bt - 1)), 1 << (bt - 1), ansl[i][bt - 1].second);
auto [ans2, t2] =
_ans(i + (1 << (bt - 1)), 1 << (bt - 1), ansr[i][bt - 1].second);
ansl[i][bt] = {ansl[i][bt - 1].first + ans1, t1};
ansr[i][bt] = {ansr[i][bt - 1].first + ans2, t2};
}
}
for (auto &[a, b, c, d, i] : queries) {
if (a == c) {
continue;
}
auto [cost, time] = _ans(a, c - a - 1, b);
if (time < l[c - 1]) {
time = l[c - 1];
} else if (time > r[c - 1] - 1) {
cost += time - (r[c - 1] - 1);
time = r[c - 1] - 1;
}
time++;
if (time > d) {
cost += time - d;
}
ans[i] = std::max(ans[i], cost);
}
l.pop_back();
r.pop_back();
}
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];
}
std::vector<Query> q1, q2;
for (int i = 0, a, b, c, d, t; i < q; ++i) {
std::cin >> t >> a >> b >> c >> d;
--a, --c;
if (a <= c) {
q1.push_back({a, b, c, d, i});
} else {
q2.push_back({a, b, c, d, i});
}
}
std::vector<ll> ans(q);
solve(n, q, l, r, q1, ans);
// std::reverse(l.begin(), l.end());
// std::reverse(r.begin(), r.end());
// for (auto &[a, b, c, d, i] : q2) {
// a = n - a - 1, c = n - c - 1;
// }
// solve(n, q, l, r, q2, ans);
for (auto &i : ans) {
std::cout << i << '\n';
}
}
