Formula One

Formula One (also known as Formula 1 or F1) is the highest class of international racing for open-wheel single-seater formula racing cars sanctioned by the Federation Internationale de l’Automobile (FIA). Matthew is a die-hard fan of F1 and an outstanding programmer. As he watched an F1 race with $N$ cars, he found some strange patterns. Mainly, he observed that the distance traveled by the i-th car up to the moment of time $T$ is equal to $T^2 \cdot a_i + T \cdot b_i + c_i$, where $a_i$, $b_i$ and $c_i$ are some constants.

Matthew decided to implement an interactive scoreboard, where someone can see what car occupies a certain position at a certain moment. Strictly speaking, there are $Q$ queries ($P, T$), which ask for the index of the car occupying the $P$-th position at the moment $T$. The position of a car is related to the distance it traveled, more distance meaning a better place (the first car traveled the most, the second car traveled the second most, and so on). If two cars travel the same distance, the lower index one is ahead.

As Matthew is busy watching the races, he asks you to implement the scoreboard for him.

Input data

The input contains on the first line an integer N, the number of cars taking part in the race.

On each of the following $N$ lines there are $3$ integers separated by a space: $a_i$, $b_i$ and $c_i$.

The next line of the input contains an integer $Q$, the number of queries you need to answer.

On each of the following $Q$ lines, there are $2$ integers separated by a space: $P$ and $T$

Output data

The output will contain $Q$ lines, containing the answer for each query.

Constraints and clarifications

• $1 \leq P \leq N \leq 2 \ 000$
• $0 \leq T, a_i, b_i, c_i \leq 10^6$
• $1 \leq Q \leq 2 \cdot 10^5$
• For tests worth 20 points, $1 \leq N \leq 10$
• For tests worth 30 more points, $1 \leq Q \leq 5 \cdot 10^4$

Example 1

stdin

5
5 7 1
4 7 2
3 3 3
7 6 9
10 2 3
10
1 0
3 1
4 2
5 3
1 4
5 656300
2 632744
3 549544
5 60828
2 67803

stdout

4
1
2
3
5
3
4
1
3
4