Problem: Lord Tirek is a centaur and the main antagonist in the season four finale episodes in the series "My Little Pony: Friendship Is Magic". In "Twilight's Kingdom" (Part 1), Tirek escapes from Tartarus and drains magic from ponies to grow stronger.

<image>

The core skill of Tirek is called Absorb Mana. It takes all mana from a magic creature and gives them to the caster.

Now to simplify the problem, assume you have n ponies (numbered from 1 to n). Each pony has three attributes:

  * si : amount of mana that the pony has at time 0; 
  * mi : maximum mana that the pony can have; 
  * ri : mana regeneration per unit time. 



Lord Tirek will do m instructions, each of them can be described with three integers: ti, li, ri. The instruction means that at time ti, Tirek will use Absorb Mana on ponies with numbers from li to ri (both borders inclusive). We'll give you all the m instructions in order, count how much mana Tirek absorbs for each instruction.

Input

The first line contains an integer n (1 ≤ n ≤ 105) — the number of ponies. Each of the next n lines contains three integers si, mi, ri (0 ≤ si ≤ mi ≤ 105; 0 ≤ ri ≤ 105), describing a pony. 

The next line contains an integer m (1 ≤ m ≤ 105) — the number of instructions. Each of the next m lines contains three integers ti, li, ri (0 ≤ ti ≤ 109; 1 ≤ li ≤ ri ≤ n), describing an instruction of Lord Tirek. The instructions are given in strictly increasing order of ti (all ti are distinct).

Output

For each instruction, output a single line which contains a single integer, the total mana absorbed in this instruction.

Examples

Input

5
0 10 1
0 12 1
0 20 1
0 12 1
0 10 1
2
5 1 5
19 1 5


Output

25
58

Note

Every pony starts with zero mana. For the first instruction, each pony has 5 mana, so you get 25 mana in total and each pony has 0 mana after the first instruction.

For the second instruction, pony 3 has 14 mana and other ponies have mana equal to their mi.

Solution (in JAVA):

Solution:
import java.io.*;
import java.util.*;
import java.math.BigInteger.*;
import static java.lang.Math.*;
import static java.math.BigInteger.*;
import static java.util.Arrays.*;
import java.util.logging.Level;
import java.util.logging.Logger;


// https://netbeans.org/kb/73/java/editor-codereference_ru.html#display
//<editor-fold defaultstate="collapsed" desc="Main">
public class Main {
    private void run() {
        Locale.setDefault(Locale.US);
        boolean oj = true;
        try {
            oj = System.getProperty("MYLOCAL") == null;
        } catch (Exception e) {
        }
        
        if (oj) {
            sc = new FastScanner(new InputStreamReader(System.in));
            out = new PrintWriter(new OutputStreamWriter(System.out));
        } else {
            try {
                sc = new FastScanner(new FileReader("input.txt"));
                out = new PrintWriter(new FileWriter("output.txt"));
            } catch (IOException e) {
                MLE();
            }
        }
        Solver s = new Solver();
        s.sc = sc;
        s.out = out;
        s.solve();
        if( !oj ){
            err.println("Time: " + (System.currentTimeMillis() - timeBegin) / 1e3);
            {
                //System.gc();
                long a = Runtime.getRuntime().maxMemory()>>20;
                long b = Runtime.getRuntime().totalMemory()>>20;
                long c = Runtime.getRuntime().freeMemory()>>20;
                err.printf( "Mem: %d/%d %d\n", c, b, a );
            }
        }
        out.flush();
    }
    
    private void show(int[] arr) {
        for (int v : arr) {
            err.print(" " + v);
        }
        err.println();
    }
    
    public static void MLE() {
        int[][] arr = new int[1024 * 1024][];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = new int[1024 * 1024];
        }
    }
    
    public static void main(String[] args) {
        new Main().run();
    }
    
    long timeBegin = System.currentTimeMillis();
    FastScanner sc;
    PrintWriter out;
    PrintStream err = System.err;
}
//</editor-fold>

//<editor-fold defaultstate="collapsed" desc="FastScanner">
class FastScanner {
    
    BufferedReader br;
    StringTokenizer st;
    
    FastScanner(InputStreamReader reader) {
        br = new BufferedReader(reader);
        st = new StringTokenizer("");
    }
    
    String next() {
        while (!st.hasMoreElements()) {
            try {
                st = new StringTokenizer(br.readLine());
            } catch (IOException ex) {
                Main.MLE();
            }
        }
        return st.nextToken();
    }
    
    int nextInt() {
        return Integer.parseInt(next());
    }
    
    long nextLong() {
        return Long.parseLong(next());
    }
}
//</editor-fold>


class Seg implements Comparable<Seg>{
    int l, r, time;
    Seg( int l, int r, int time ){
        this.l = l;
        this.r = r;
        this.time = time;
    }

    @Override
    public int compareTo(Seg b) {
        return Integer.compare(l, b.l);
    }

    @Override
    public String toString() {
        return String.format("(%d %d)", l, r);
    }
    
    
    
}

final class Pony{
    long base, max, race, delta;
}

class Solver {

    FastScanner sc;
    PrintWriter out;
    PrintStream err = System.err;

    final int inf = Integer.MAX_VALUE/2;
    int n;
    Pony[] pony;
    TreeSet<Seg> ts;
    Pony[][] treePony;
    long[][] prefSumMax, sufSumRace;
    

    long simpleQuery( int l, int r, long time ){
        long ans = 0;
        for (int i = l; i <= r; i++) {
            ans += min( pony[i].base + pony[i].race * time, 
                pony[i].max );
        }
        return ans;
    }
    
    long query( int l, int r, int time, int v, int tl, int tr ){
        if( l > r )
            return 0;
        if( l == tl && r == tr ){
            int pos = posOfFloorElement( treePony[v], time );
            long ans = 0;
            if( pos != -1 )
                ans += prefSumMax[v][pos];
            if( pos+1 < sufSumRace[v].length )
                ans += sufSumRace[v][pos+1] * (long)time;
//            err.printf( "%d %d %d:   %d\n", l, r, time, ans );
            return ans;
        }
        else{
            int tm = (tl + tr) / 2;
            return
                query(           l, min(r,tm), time, 2*v  , tl  , tm ) + 
                query( max(l,tm+1),         r, time, 2*v+1, tm+1, tr );
        }
    }
    
    void build( int v, int tl, int tr ){
        int sz = tr - tl + 1;
        treePony[v] = new Pony[sz];
        prefSumMax[v] = new     long[sz];
        sufSumRace[v] = new     long[sz];
        if( tl == tr ){
            treePony[v][0] = pony[tl];
            prefSumMax[v][0] = pony[tl].max;
            sufSumRace[v][0] = pony[tl].race;
        }
        else{
            int tm = (tl + tr) / 2;
            build( 2*v  , tl  , tm );
            build( 2*v+1, tm+1, tr );
            
            //for( int i = tl; i <= tr; ++i ) treePony[v][i - tl] = pony[i];
            //sort( treePony[v], (a,b) -> Long.compare(a.delta,b.delta) );
            
            treePony[v] = merge(treePony[2*v],treePony[2*v+1]);
            
            for (int i = 0; i < sz; i++){
                prefSumMax[v][i] = treePony[v][i].max;
                sufSumRace[v][i] = treePony[v][i].race;
            }
            for (int i = 1; i < sz; i++) 
                prefSumMax[v][i] += prefSumMax[v][i-1];
            for (int i = sz-2; 0 <= i; i--)
                sufSumRace[v][i] += sufSumRace[v][i+1];
        }
    }
    
    Pony[] merge( Pony[] a, Pony[] b ){
        Pony[] c = new Pony[a.length + b.length];
        int sz = 0, ib = 0;
        for( Pony p : a ){
            while( ib < b.length && b[ib].delta <= p.delta )
                c[sz++] = b[ib++];
            c[sz++] = p;
        }
        while( ib < b.length )
            c[sz++] = b[ib++];
        return c;
    }
    
    void solve(){
        n = sc.nextInt();
        pony = new Pony[n];
        for (int i = 0; i < n; i++) {
            pony[i] = new Pony();
            pony[i].base = sc.nextInt();
            pony[i].max = sc.nextInt();
            pony[i].race = sc.nextInt();
            pony[i].delta = pony[i].race==0? inf : 
                (pony[i].max + pony[i].race - 1) / pony[i].race;
        }
        
        treePony = new Pony[4*n][];
        prefSumMax = new long[4*n][];
        sufSumRace = new long[4*n][];
        build(1, 0, n-1);
        
        //
        int cntQ = sc.nextInt();
        ts = new TreeSet<>();
        for (int iter = 0; iter < cntQ; iter++) {
            //err.println("q: " + iter);
            int qt = sc.nextInt();
            Seg qSeg = new Seg(sc.nextInt()-1, sc.nextInt()-1,qt);
            ArrayList<Seg> arr = new ArrayList<>();
            arr.add(new Seg(-inf, qSeg.l-1,0));
            Seg seg;
            seg = ts.lower(qSeg);
            if( seg != null && qSeg.l <= seg.r ){
                ts.remove(seg);
                if( seg.l <= qSeg.l-1 )
                    ts.add(new Seg(seg.l, qSeg.l-1, seg.time));
                if( qSeg.r+1 <= seg.r )
                    ts.add(new Seg(qSeg.r+1, seg.r, seg.time));
                arr.add(new Seg(qSeg.l, min(seg.r,qSeg.r), seg.time));
            }
            for( ; ; ){
                seg = ts.ceiling(qSeg);
                if( seg == null || qSeg.r < seg.l ) 
                    break;
                ts.remove(seg);
                if( qSeg.r+1 <= seg.r )
                    ts.add(new Seg(qSeg.r+1, seg.r,seg.time));
                arr.add(new Seg(seg.l, min(seg.r,qSeg.r), seg.time));
            }
            ts.add(qSeg);
            arr.add(new Seg(qSeg.r+1,inf, 0));
            
            
            long ans = 0;
            for (int i = 1; i < arr.size(); i++) {
                int l, r;
                Seg prSeg = arr.get(i-1);
                seg = arr.get(i);
                l = prSeg.r + 1;
                r = seg.l - 1;
                if( l <= r ){
                    ans += simpleQuery(l,r,qt);
                }
                if( i != arr.size() - 1 ){
                    ans += query(seg.l,seg.r, qt-seg.time,  1,0,n-1);
                }
            }
            out.println(ans);
        }
        /**/
    }

    int posOfFloorElement( Pony[] pony, int time) {
        int l = -1, r = pony.length - 1;
        while( l < r ){
            int m = (l + r + 1) >> 1;
            if( pony[m].delta <= time )
                l = m;
            else
                r = m - 1;
        }
        return l;
    }

}