#include <iostream>
#include <vector>
#include <algorithm>
// Sử dụng 'using' cho kiểu dữ liệu long long, là một cách làm tốt hơn #define.
using ll = long long;
using namespace std;
// --- Hằng số với tên gọi rõ ràng ---
const int MAX_N = 1000005; // Kích thước tối đa cho các mảng
const int SEG_TREE_SIZE = MAX_N * 4; // Kích thước cây phân đoạn
const ll INF = 4e18; // Giá trị lớn tượng trưng cho vô cực, đủ lớn để tránh tràn số
// --- Các cấu trúc dữ liệu với tên rõ ràng ---
// Lưu trữ thông tin cho mỗi item
struct Item {
ll height, min_dist, max_dist;
};
// Lưu trữ thông tin cho mỗi truy vấn
struct Query {
int l, r, id;
};
// --- Biến toàn cục ---
int num_items, num_queries;
Item items[MAX_N];
Query queries[MAX_N];
ll results[MAX_N];
// Mảng vector để xử lý sự kiện trong thuật toán Sweep-line
// start_events[i] chứa các item 'bắt đầu' có hiệu lực tại vị trí i
// end_events[i] chứa các item 'kết thúc' hiệu lực tại vị trí i
vector<int> start_events[MAX_N];
vector<int> end_events[MAX_N];
// --- Cây phân đoạn (Segment Tree) ---
// Cây phân đoạn được thiết kế đặc biệt để giải quyết bài toán này.
// Mỗi nút trong cây lưu trữ:
// 1. min_h_tree: giá trị min(h_i) trong đoạn [l, r] của nút.
// 2. max_diff_tree: giá trị max(h_j - h_i) đã tìm được trong đoạn [l, r].
// 3. lazy_tree: giá trị h_j được truyền xuống một cách lười biếng.
ll min_h_tree[SEG_TREE_SIZE];
ll max_diff_tree[SEG_TREE_SIZE];
ll lazy_tree[SEG_TREE_SIZE];
// Hàm so sánh để sắp xếp các truy vấn theo điểm cuối bên phải (r)
bool compare_queries(const Query& A, const Query& B) {
return A.r < B.r;
}
// Đẩy giá trị lazy xuống các nút con
void push_down(int id) {
if (lazy_tree[id] != -INF) {
// Cập nhật kết quả của nút hiện tại dựa trên giá trị lazy
// Đây là bước cốt lõi: max_diff = max(max_diff, h_j - min(h_i))
max_diff_tree[id] = max(max_diff_tree[id], lazy_tree[id] - min_h_tree[id]);
// Truyền giá trị lazy xuống các nút con
int lc = id << 1, rc = lc | 1;
lazy_tree[lc] = max(lazy_tree[lc], lazy_tree[id]);
lazy_tree[rc] = max(lazy_tree[rc], lazy_tree[id]);
// Đặt lại giá trị lazy của nút hiện tại
lazy_tree[id] = -INF;
}
}
// Xây dựng cây phân đoạn
void build_tree(int id, int l, int r) {
lazy_tree[id] = -INF;
min_h_tree[id] = INF; // Khởi tạo min là vô cực
max_diff_tree[id] = -INF; // Khởi tạo max_diff là âm vô cực
if (l == r) return;
int mid = (l + r) >> 1;
build_tree(id << 1, l, mid);
build_tree(id << 1 | 1, mid + 1, r);
}
// Cập nhật điểm: thay đổi giá trị chiều cao của một item tại vị trí `pos`
void update_point_height(int id, int l, int r, int pos, ll value) {
push_down(id);
if (l == r) {
min_h_tree[id] = value;
return;
}
int mid = (l + r) >> 1;
if (pos <= mid) {
push_down(id << 1 | 1); // Đẩy lazy của nút anh em trước khi cập nhật
update_point_height(id << 1, l, mid, pos, value);
} else {
push_down(id << 1); // Đẩy lazy của nút anh em
update_point_height(id << 1 | 1, mid + 1, r, pos, value);
}
min_h_tree[id] = min(min_h_tree[id << 1], min_h_tree[id << 1 | 1]);
max_diff_tree[id] = max(max_diff_tree[id << 1], max_diff_tree[id << 1 | 1]);
}
// Cập nhật đoạn: áp dụng giá trị h_j (val) cho tất cả các item i trong đoạn [x, y]
void update_range_lazy(int id, int l, int r, int x, int y, ll val) {
push_down(id);
if (y < l || r < x) return;
if (x <= l && r <= y) {
lazy_tree[id] = max(lazy_tree[id], val);
push_down(id);
return;
}
int mid = (l + r) >> 1;
update_range_lazy(id << 1, l, mid, x, y, val);
update_range_lazy(id << 1 | 1, mid + 1, r, x, y, val);
min_h_tree[id] = min(min_h_tree[id << 1], min_h_tree[id << 1 | 1]);
max_diff_tree[id] = max(max_diff_tree[id << 1], max_diff_tree[id << 1 | 1]);
}
// Truy vấn đoạn: lấy giá trị max_diff_tree lớn nhất trong đoạn [x, y]
ll query_max_diff(int id, int l, int r, int x, int y) {
push_down(id);
if (y < l || r < x) return -INF;
if (x <= l && r <= y) return max_diff_tree[id];
int mid = (l + r) >> 1;
return max(
query_max_diff(id << 1, l, mid, x, y),
query_max_diff(id << 1 | 1, mid + 1, r, x, y)
);
}
// Hàm chính thực hiện thuật toán Sweep-line
void run_sweep_line() {
build_tree(1, 1, num_items);
int sweep_pos = 0;
for (int i = 1; i <= num_queries; i++) {
int L = queries[i].l, R = queries[i].r, idx = queries[i].id;
// Di chuyển đường quét đến điểm cuối `R` của truy vấn hiện tại
while (sweep_pos < R) {
sweep_pos++;
// Xử lý các item bắt đầu có hiệu lực tại sweep_pos
for (int p : start_events[sweep_pos]) {
update_point_height(1, 1, num_items, p, items[p].height);
}
// Xử lý các item kết thúc hiệu lực tại sweep_pos bằng cách đặt chiều cao của chúng là vô cực
for (int p : end_events[sweep_pos]) {
update_point_height(1, 1, num_items, p, INF);
}
// Item tại `sweep_pos` giờ là `j`. Tìm các `i` thỏa mãn `l_j <= j-i <= r_j`
// Tức là `j - r_j <= i <= j - l_j`
ll lo = max(1LL, (ll)sweep_pos - items[sweep_pos].max_dist);
ll hi = max(1LL, (ll)sweep_pos - items[sweep_pos].min_dist);
if (lo <= hi) {
// Áp dụng chiều cao của item j (items[sweep_pos].height) cho tất cả các i trong đoạn [lo, hi]
update_range_lazy(1, 1, num_items, lo, hi, items[sweep_pos].height);
}
}
// Trả lời truy vấn cho đoạn [L, R]
results[idx] = max(results[idx], query_max_diff(1, 1, num_items, L, R));
}
}
signed main() {
// Tăng tốc độ nhập xuất
ios::sync_with_stdio(false);
cin.tie(NULL);
cin >> num_items;
for (int i = 1; i <= num_items; i++) {
cin >> items[i].height >> items[i].min_dist >> items[i].max_dist;
if (i + items[i].min_dist <= num_items) {
start_events[i + items[i].min_dist].push_back(i);
}
if (i + items[i].max_dist + 1 <= num_items) {
end_events[i + items[i].max_dist + 1].push_back(i);
}
}
cin >> num_queries;
for (int i = 1; i <= num_queries; i++) {
cin >> queries[i].l >> queries[i].r;
queries[i].id = i;
}
sort(queries + 1, queries + 1 + num_queries, compare_queries);
for (int i = 1; i <= num_queries; i++) results[i] = -1;
// --- Lần chạy thứ nhất: Tìm max(h_j - h_i) ---
run_sweep_line();
// --- Chuẩn bị cho lần chạy thứ hai ---
// Để tìm max(h_i - h_j), ta biến đổi h' = C - h và tìm max(h'_j - h'_i)
// max(h'_j - h'_i) = max((C - h_j) - (C - h_i)) = max(h_i - h_j)
for (int i = 1; i <= num_items; i++) {
items[i].height = INF - items[i].height;
// Xóa các vector sự kiện để chuẩn bị cho lần chạy thứ hai
start_events[i].clear();
end_events[i].clear();
}
// Cần thêm vector `end_events` cho vị trí > num_items
for (int i = num_items + 1; i < MAX_N; ++i) end_events[i].clear();
// Tạo lại các sự kiện với chiều cao đã biến đổi
for (int i = 1; i <= num_items; i++) {
if (i + items[i].min_dist <= num_items) {
start_events[i + items[i].min_dist].push_back(i);
}
if (i + items[i].max_dist + 1 <= num_items) {
end_events[i + items[i].max_dist + 1].push_back(i);
}
}
// --- Lần chạy thứ hai: Tìm max(h_i - h_j) ---
run_sweep_line();
// In kết quả cuối cùng
for (int i = 1; i <= num_queries; i++) {
cout << results[i] << "\n";
}
return 0;
}
