#pragma GCC optimize "Ofast,unroll-loops,omit-frame-pointer,inline"
#include <algorithm>
#include <iostream>
#include <vector>
#include <cstdio>
using namespace std;
using ll = long long;
const int oo = 1000*1000*1000;
const int NB_MAX_ANTENNES = 200*1000 + 42;
struct Antenne
{
int pos;
int hauteur;
int distMin, distMax;
};
int nbAntennes;
Antenne antennes[NB_MAX_ANTENNES];
/*
* Arbre binaire
*/
const int NB_FEUILLES = 1<<18;
const int NB_NOEUDS = 2*NB_FEUILLES;
pair<int, int> valeurs[NB_NOEUDS]; // {min, max}
void setValeur (const int pos, const int nouvelleValeur)
{
int iNoeud = NB_FEUILLES + pos;
if (nouvelleValeur == -1) {
valeurs[iNoeud] = make_pair(+oo, -oo);
}
else {
valeurs[iNoeud] = make_pair(nouvelleValeur, nouvelleValeur);
}
for (iNoeud/=2; iNoeud>=1; iNoeud/=2) {
valeurs[iNoeud].first = min(valeurs[iNoeud*2].first, valeurs[iNoeud*2+1].first);
valeurs[iNoeud].second = max(valeurs[iNoeud*2].second, valeurs[iNoeud*2+1].second);
}
}
pair<int, int> getMinmax (const int debut, const int fin,
const int iNoeud=1, const int debutActuel=0, const int finActuelle=NB_FEUILLES)
{
if (debutActuel >= debut && finActuelle <= fin) {
return valeurs[iNoeud];
}
if (debutActuel >= fin || finActuelle <= debut) {
return make_pair(+oo, -oo);
}
const int milieuActuel = (debutActuel + finActuelle) / 2;
const pair<int, int> res1 = getMinmax(debut, fin, iNoeud*2, debutActuel, milieuActuel);
const pair<int, int> res2 = getMinmax(debut, fin, iNoeud*2+1, milieuActuel, finActuelle);
return make_pair( min(res1.first, res2.first), max(res1.second, res2.second) );
}
/*
* Main
*/
vector<pair<int, int>> evenements[NB_MAX_ANTENNES]; // {pos, 2*iAntenne+estDebut}
int calcRequete (const int debutRequete, const int finRequete)
{
int res = -1;
for (int iAntenne=0; iAntenne<nbAntennes; iAntenne++) {
const Antenne &antenne = antennes[iAntenne];
// Traiter les événements
for (const pair<int, int> &evenement : evenements[iAntenne]) {
const Antenne &ant = antennes[evenement.second / 2];
if (evenement.second % 2 == 1) { // Début
setValeur(ant.pos, ant.hauteur);
}
else {
setValeur(ant.pos, -1);
}
}
if (debutRequete <= iAntenne && iAntenne < finRequete) {
// Trouver le max pour l'antenne actuelle
const int debut = max(antenne.pos + antenne.distMin, debutRequete);
const int fin = min(antenne.pos + antenne.distMax + 1, finRequete);
if (debut >= nbAntennes) {
continue;
}
const pair<int, int> minmax = getMinmax(debut, fin);
const int score1 = minmax.second - antenne.hauteur;
const int score2 = antenne.hauteur - minmax.first;
res = max( max(score1, score2), res );
}
}
return res;
}
int main ()
{
scanf("%d", &nbAntennes);
for (int i=0; i<nbAntennes; i++) {
antennes[i].pos = i;
scanf("%d %d %d", &antennes[i].hauteur, &antennes[i].distMin, &antennes[i].distMax);
setValeur(i, -1);
}
int nbRequetes;
scanf("%d", &nbRequetes);
if (nbAntennes <= 2000) {
struct Point
{
int debut, fin;
bool estRequete;
int info; // iRequete ou score
bool operator< (const Point &autre)
{
if (fin != autre.fin) {
return fin < autre.fin;
}
if (debut != autre.debut) {
return debut > autre.debut;
}
return !estRequete;
}
};
vector<Point> points;
int resRequetes[200*1000];
for (int iRequete=0; iRequete<nbRequetes; iRequete++) {
int debutRequete, finRequete;
scanf("%d %d", &debutRequete, &finRequete);
debutRequete--, finRequete--; // FIN INCLUSE
points.push_back(Point{debutRequete, finRequete, true, iRequete});
}
for (int a=0; a<nbAntennes; a++) {
for (int b=a+1; b<nbAntennes; b++) {
if (a < b-antennes[b].distMax || a > b-antennes[b].distMin) {
continue;
}
if (b > a+antennes[a].distMax || b < a+antennes[a].distMin) {
continue;
}
points.push_back(Point{a, b, false, abs(antennes[a].hauteur - antennes[b].hauteur)});
}
}
sort(points.begin(), points.end());
for (const Point &point : points) {
if (point.estRequete) {
resRequetes[point.info] = getMinmax(point.debut, nbAntennes).second;
if (resRequetes[point.info] == -oo) {
resRequetes[point.info] = -1;
}
}
else {
if (point.info > valeurs[NB_FEUILLES+point.debut].second) {
setValeur(point.debut, point.info);
}
}
}
for (int iRequete=0; iRequete<nbRequetes; iRequete++) {
printf("%d\n", resRequetes[iRequete]);
}
}
else {
for (int i=0; i<nbAntennes; i++) {
const Antenne &ant = antennes[i];
evenements[ max(ant.pos - ant.distMax, 0) ].push_back(make_pair(ant.pos, 2*i+1));
evenements[ max(ant.pos - ant.distMin + 1, 0) ].push_back(make_pair(ant.pos, 2*i));
}
for (int iRequete=0; iRequete<nbRequetes; iRequete++) {
int debutRequete, finRequete;
scanf("%d %d", &debutRequete, &finRequete);
debutRequete--;
printf("%d\n", calcRequete(debutRequete, finRequete));
}
}
}
