The Second Rhythm Game of Goinmul

Karuna, a national rhythm game team member and a key figure in the World Cup semifinals, started a new rhythm game to dominate the genre.

The song Karuna plays consists of several notes. Each note must be hit exactly $T_i$ seconds after the song starts, and hitting it gives a score $A_i$ and energy $B_i$. The final score is the sum of the scores from all notes. $A_i$ may be negative, but Karuna ignores that and always hits every note at the exact time.

The game also has a fever system. The fever gauge starts at 0. Each time a note is hit, the gauge rises by the energy from that note. However, if the fever gauge exceeds $X$, it is capped at $X$.

When the fever gauge reaches $X$, Karuna can activate fever time at any moment. Fever time lasts exactly $Y$ seconds, and notes processed during fever time score double. Notes processed at the moment fever time starts or ends also score double. The fever gauge does not rise during fever time, and it resets to 0 right after fever time ends.

The game has several difficulty levels. Each level has its own maximum fever gauge $X$ and fever time length $Y$. For each level, find the maximum score Karuna can obtain.

The first line contains the number of notes $N$.

Each of the next $N$ lines contains the time $T_i$, score $A_i$, and energy $B_i$ of a note. All $T_i$ are guaranteed to be distinct.

The next line contains the number of difficulty levels $Q$.

Each of the next $Q$ lines contains the maximum fever gauge $X_i$ and fever time length $Y_i$ of a level.

Print $Q$ lines. The $i$-th line contains the maximum score Karuna can obtain at the $i$-th difficulty level.

• $1 \leq N \leq 1,000,000$
• $1 \leq Q \leq 10$
• $0 \leq T_i, B_i \leq 10^9$
• $-10^9 \leq A_i \leq 10^9$
• $1 \leq X_i, Y_i \leq 10^9$
• All numbers in the input are integers.