#include <bits/stdc++.h>
using namespace std;
// each point has h[i] a[i] b[i]
// two points (i, j) can see each other if max(a[i], a[j]) <= abs(i - j) <= min(b[i], b[j])
// can try to break the abs and maybe do something with increasing b[i] or a[i], but a better way is to do this:
// - WLOG assume j < i
// - then for each j, the i it can reach form a continuous range
// - and for each i, the j it can reach also form a continuous range
// - so iterate over increasing i, and we turn on and off j as necessary
// - then for each i, we can get the answer of the relevant range and find out what is the max and min, from there find out the
// max diff
// - O(nlog(n)) in total assuming we use a segment tree to get min and max from a range
//
// this find the max over all doesn't help with the range queries, but we can use it it help with the range query using some
// sqrt trick:
// - pick block size K then the each query is split into blocks
// - the whole blocks and mixing with each other can be precalculated:
// - there's O(n / K) such blocks and we can calculate the answer in n * O(n / K + K) total:
// - for each element, iterate over its possible range, it can only contribute to some blocks
// - for the whole blocks, we only need to get the max and min, so it's O(1)
// - for the non whole block, just iterate over everything
// - for the remaining part, we can just iterate over the items and get in the range
// - which can be done as allocated offline query to each element
// - total should be K * q * complexity of the DS
//
//
//
//
// is there some 2d idea?
// - consider a square of [1, n] * [1, n]
// - for each query, we are effectively computing the max of the distance when paired inside [l, r] * [l, r]
// - |h[i] - h[j]| = max(h[i] - h[j], h[j] - h[i]) so instead of maximising the distance, we can maximise the signed distance
// - let the row i and column j cell to be h[i] - h[j]
// - if we choose every pairs then:
// - just add h[i] to all the row
// - just add -h[j] to all the column
// - which is O(n) rectangle adds
// - then we can try to block the bad cell:
// - for each i, there is at most 2 ranges where we can use i
// - so we can filter out the ranges where we can pair i
// - so add -inf to where we are not allowed to pair
// - then we have a 2d structures where to query [l, r], we need to get the max inside a square [l, r] * [l, r]
// - this is not really possible or it's very advanced
// - quadtree can't handle the 1 x n rects well
// - segment tree of segment trees can't really do the lazy update well
// shift the range into -5e8 5e8 to make the number works
constexpr int INF = 1e9;
int n;
constexpr int MAX_N = 2e5;
constexpr int BLOCK_SIZE = 256;
constexpr int BLOCK_COUNT = (MAX_N - 1) / BLOCK_SIZE + 1;
class point_t {
public:
int h, a, b;
} p[MAX_N];
int pre_result[BLOCK_COUNT][BLOCK_COUNT];
vector<int> turn_on[MAX_N];
vector<int> turn_off[MAX_N];
multiset<int> block_set[BLOCK_COUNT];
int block_id(const int &i) { return i / BLOCK_SIZE; }
bool is_block_start(const int &i) { return i % BLOCK_SIZE == 0; }
void precalculate() {
const int block_count = block_id(n - 1) + 1;
// calculate where we need to turn on or off the left paired element
for (int i = 0; i < n; i++) {
int l = i + p[i].a;
int r = i + p[i].b;
if (l < n) turn_on[l].push_back(i);
if (r + 1 < n) turn_off[r + 1].push_back(i);
}
// calculate the result
for (int i = 0; i < block_count; i++)
for (int j = i; j <= block_count; j++) pre_result[i][j] = -1;
for (int i = 0; i < n; i++) {
// first turn on and off the relevant items
for (auto &&j : turn_off[i]) {
auto &&s = block_set[block_id(j)];
s.erase(s.find(p[j].h));
}
for (auto &&j : turn_on[i]) {
auto &&s = block_set[block_id(j)];
s.insert(p[j].h);
}
// then each block now have the elements that can see this elements
const int b_id = block_id(i);
// iterate over each elements this can see
const int r = i - p[i].a;
int l = max(0, i - p[i].b);
while (l <= r) {
if (is_block_start(l) && (block_id(l) != block_id(r))) {
// can get the whole blocks
const auto l_b_id = block_id(l);
auto &&s = block_set[l_b_id];
if (!s.empty()) {
auto &&result = pre_result[l_b_id][b_id];
auto &&block_max = *s.rbegin();
auto &&block_min = *s.begin();
result = max(result, max(block_max - p[i].h, p[i].h - block_min));
}
l += BLOCK_SIZE;
} else {
// can only get l
if ((l + p[l].a <= i) && (l + p[l].b >= i)) {
const auto l_b_id = block_id(l);
auto &&result = pre_result[l_b_id][b_id];
result = max(result, abs(p[l].h - p[i].h));
}
l++;
}
}
}
// pre_result[a][b] now contains all the way to pair block a and block b
// use dp to get it to contain all the result when pairing all the items
for (int diff = 0; diff < block_count; diff++) {
for (int l = 0; l + diff < block_count; l++) {
int r = l + diff;
if (r + 1 < n) pre_result[l][r + 1] = max(pre_result[l][r + 1], pre_result[l][r]);
if (l > 0) pre_result[l - 1][r] = max(pre_result[l - 1][r], pre_result[l][r]);
}
}
}
class segment_tree_t {
public:
pair<int, int> st[MAX_N * 4 + 1];
int node_id[MAX_N];
void build(int i, int l, int r) {
st[i].first = INF;
st[i].second = -INF;
if (l == r) {
node_id[l] = i;
} else {
int m = (l + r) / 2;
build(i * 2, l, m);
build(i * 2 + 1, m + 1, r);
}
}
template <bool TURN_ON>
void update(const int &u) {
int i = node_id[u];
if constexpr (TURN_ON) {
st[i].first = st[i].second = p[u].h;
} else {
st[i].first = INF;
st[i].second = -INF;
}
i /= 2;
while (i) {
st[i].first = min(st[i * 2].first, st[i * 2 + 1].first);
st[i].second = max(st[i * 2].second, st[i * 2 + 1].second);
i /= 2;
}
}
pair<int, int> get(const int &i, const int &l, const int &r, const int &u, const int &v) {
if (l > v || r < u) return {INF, -INF};
if (u <= l && v >= r) return st[i];
int m = (l + r) / 2;
auto [left_min, left_max] = get(i * 2, l, m, u, v);
auto [right_min, right_max] = get(i * 2 + 1, m + 1, r, u, v);
return {min(left_min, right_min), max(left_max, right_max)};
}
pair<int, int> get(const int &u, const int &v) {
if (u > v) return {INF, -INF};
// it's possible to do this non recursive too but let's keep it simple
return get(1, 0, n - 1, u, v);
}
} tree;
class point_query_t {
public:
int l, r, i, id;
};
// right queries mean we are trying to pair i with something to the right of it, in the range l r
// left queries mean the reversed
deque<point_query_t> right_queries;
deque<point_query_t> left_queries;
deque<point_query_t> queries;
int q;
int ans[MAX_N];
void process_left_queries() {
// query, try to pair with the left side of the array
sort(left_queries.begin(), left_queries.end(), [](const auto &A, const auto &B) { return A.i < B.i; });
queries.clear();
tree.build(1, 0, n - 1);
for (int i = 0; i < n; i++) {
for (auto &&need_on : turn_on[i]) tree.update<true>(need_on);
for (auto &&need_off : turn_off[i]) tree.update<false>(need_off);
// handle all the queries at i to the left
while ((!left_queries.empty()) && (left_queries.front().i == i)) {
queries.push_back(left_queries.front());
left_queries.pop_front();
}
const auto i_l = i - p[i].b;
const auto i_r = i - p[i].a;
while ((!queries.empty()) && (queries.front().i == i)) {
auto [l, r, _, id] = queries.front();
queries.pop_front();
auto [min_value, max_value] = tree.get(max(l, i_l), min(r, i_r));
if (min_value != INF) ans[id] = max(ans[id], p[i].h - min_value);
if (max_value != -INF) ans[id] = max(ans[id], max_value - p[i].h);
if (i < r) queries.push_back(point_query_t{.l = l, .r = r, .i = i + 1, .id = id});
}
}
}
void process_right_queries() {
// need to remake the turn on turn off arrays since we reverse direction now
for (int i = 0; i < n; i++) turn_on[i].clear();
for (int i = 0; i < n; i++) turn_off[i].clear();
for (int i = 0; i < n; i++) {
int l = i - p[i].b;
int r = i - p[i].a;
if (r >= 0) turn_on[r].push_back(i);
if (l > 0) turn_off[l - 1].push_back(i);
}
// query, try to pair with the right side of the array
sort(right_queries.begin(), right_queries.end(), [](const auto &A, const auto &B) { return A.i > B.i; });
queries.clear();
tree.build(1, 0, n - 1);
for (int i = n - 1; i >= 0; i--) {
for (auto &&need_on : turn_on[i]) tree.update<true>(need_on);
for (auto &&need_off : turn_off[i]) tree.update<false>(need_off);
// handle all the queries at i to the right
while ((!right_queries.empty()) && (right_queries.front().i == i)) {
queries.push_back(right_queries.front());
right_queries.pop_front();
}
const auto i_l = i + p[i].a;
const auto i_r = i + p[i].b;
while ((!queries.empty()) && (queries.front().i == i)) {
auto [l, r, _, id] = queries.front();
queries.pop_front();
auto [min_value, max_value] = tree.get(max(l, i_l), min(r, i_r));
if (min_value != INF) ans[id] = max(ans[id], p[i].h - min_value);
if (max_value != -INF) ans[id] = max(ans[id], max_value - p[i].h);
if (i > l) queries.push_back(point_query_t{.l = l, .r = r, .i = i - 1, .id = id});
}
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for (int i = 0; i < n; i++) {
auto &&[h, a, b] = p[i];
cin >> h >> a >> b;
h -= 5e8;
}
precalculate();
// read and handle query
// to avoid memory issue we can't just place down all the query, so need to store it in the form of (i, l, r, id):
// - query id is id
// - the range of the query is from l to r
// - the current element being considered is i
// we can keep pushing it until the end of the queue with increased i
cin >> q;
for (int i = 0; i < q; i++) {
static int l, r;
cin >> l >> r;
l--;
r--;
const int first_block = block_id(l);
const int last_block = block_id(r);
if (first_block + 1 < last_block) ans[i] = pre_result[first_block + 1][last_block - 1];
else ans[i] = -1;
if (first_block == last_block) {
right_queries.push_back(point_query_t{.l = l, .r = r, .i = r, .id = i});
} else {
left_queries.push_back(point_query_t{.l = l, .r = r, .i = r - r % BLOCK_SIZE, .id = i});
right_queries.push_back(point_query_t{.l = l, .r = r, .i = l - l % BLOCK_SIZE + BLOCK_SIZE - 1, .id = i});
}
}
process_left_queries();
process_right_queries();
for (int i = 0; i < q; i++) cout << ans[i] << '\n';
}
