I. Mercenaries
time limit per test
5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

In the magical land of Byteland, there are $$$n$$$ cities arranged in a line, numbered from $$$1$$$ to $$$n$$$ from left to right, and $$$n-1$$$ roads between them. Each road connects two neighboring cities. Due to the hilly terrain, each road can only be traveled from a city with a smaller number to a city with a larger number. In other words, these passages are one-way.

In each city, there lives a mercenary. These mercenaries can be described by two numbers representing their strength and their knowledge of magic. The mercenary living in the $$$i$$$-th city is described by the values $$$s_i$$$ and $$$m_i$$$.

There is a shop at each road. Each shop offers a certain list of items, and each item is described by its bonus to strength and bonus to knowledge of magic. These bonuses indicate how much should be added to the respective hero's statistics. More precisely, for the $$$i$$$-th shop (i.e., the one on the road connecting the $$$i$$$-th and $$$(i+1)$$$-st city), we know the list of pairs $$$(s'_{i, 1}, m'_{i, 1}), (s'_{i, 2}, m'_{i, 2}), \ldots, (s'_{i, r_i}, m'_{i, r_i})$$$, representing the bonuses of the items offered in that shop. A mercenary traveling along a road can buy at most one item at each shop he passes. There is no limit to how many items a mercenary can use at the same time—all bonuses from his items are added to his own statistics and accumulate.

Cities can be attacked by monsters. In the $$$i$$$-th attack scenario, the monster is described by the number of the city it attacks (denoted as $$$v_i$$$) and the values $$$a_i$$$, $$$b_i$$$, and $$$c_i$$$. They indicate that the mercenary from the $$$j$$$-th city will defeat the monster if $$$a_i \cdot S_j + b_i \cdot M_j \geq c_i$$$, where the values $$$S_j$$$ and $$$M_j$$$ are the strength and knowledge of magic of the mercenary, taking into account the bonuses he obtains by buying items on the way from his city to the city attacked by the monster. In particular, this means that $$$j \leq v_i$$$ must hold. Here, we allow $$$j = v_i$$$—then the mercenary will not have the opportunity to acquire any items. Otherwise, he will buy at most one item at each shop he passes on the way from the $$$j$$$-th to the $$$v_i$$$-th city.

Your task, as an advisor to the king of Byteland, is to prepare plans of action for all monster attack scenarios. More precisely, for each attack option $$$i$$$, you must find the largest city number $$$j$$$ such that $$$j \leq v_i$$$ and the mercenary from the $$$j$$$-th city would be able to choose the purchased items in a way that allows him to defeat the monster. Note that the attack scenarios considered are only theoretical, and the mercenaries do not move or acquire any items.

Input

The first line of the standard input contains a single integer $$$n$$$ ($$$2 \leq n \leq 200\,000$$$), indicating the number of cities. The next $$$2n-1$$$ lines describe the cities and shops on the roads between them.

For each $$$i$$$ satisfying $$$1 \leq i \leq n$$$, the $$$(2i-1)$$$-th of these lines contains two integers $$$s_i$$$ and $$$m_i$$$ ($$$0 \leq s_i,m_i \leq 10^9$$$), indicating the strength and knowledge of magic of the mercenary living in the $$$i$$$-th city.

For each $$$i$$$ satisfying $$$1 \leq i \leq n-1$$$, the $$$(2i)$$$-th of these lines starts with a single integer $$$r_i$$$ ($$$1 \leq r_i \leq 500\,000$$$), indicating the number of items offered in the shop located on the road connecting the $$$i$$$-th and $$$(i+1)$$$-st city. Then, in the same line, there is a sequence of $$$2r_i$$$ integers $$$s'_{i, 1}, m'_{i, 1}, s'_{i, 2}, m'_{i, 2}, \ldots, s'_{i, r_i}, m'_{i, r_i}$$$ ($$$0 \leq s'_{i, j}, m'_{i, j} \leq 5\,000$$$), indicating the bonuses to strength and knowledge of magic of the successive items offered in that shop. The sum of all values of $$$r_i$$$ does not exceed $$$500\,000$$$.

The next line contains a single integer $$$q$$$ ($$$1 \leq q \leq 200\,000$$$), indicating the number of monster attack scenarios.

Each of the subsequent $$$q$$$ lines contains a description of an attack scenario. The $$$i$$$-th of these lines contains four integers $$$v_i$$$, $$$a_i$$$, $$$b_i$$$, and $$$c_i$$$ ($$$1 \leq v_i \leq n;\; 0 \leq a_i,b_i \leq 10^9;\; a_i+b_i \geq 1;\; 1 \leq c_i \leq 10^{18}$$$), as described in the problem statement.

Output

The output should consist of $$$q$$$ lines: the $$$i$$$-th of them should contain a single integer, indicating the largest city number from which the mercenary would be able to defeat the monster in the $$$i$$$-th attack scenario, or $$$-1$$$ if no mercenary would be able to do so.

Example
Input
3
1 1
2 1 2 1 2
3 2
5 1 5 4 3 3 4 5 1 1 2
4 5
12
1 1 1 1
2 1 1 1
3 1 1 1
3 1 1 9
3 2 2 20
3 1 2 18
3 1 2 19
3 1 2 20
3 0 1 8
2 1 0 4
2 1 0 3
2 1 0 2
Output
1
2
3
3
2
2
1
-1
1
-1
2
2
Note

In the first shop, two items are sold, described by the same pairs $$$(1, 2)$$$ and $$$(1, 2)$$$. In the second shop, five items are sold, described by the pairs $$$(1, 5)$$$, $$$(4, 3)$$$, $$$(3, 4)$$$, $$$(5, 1)$$$, and $$$(1, 2)$$$.

In the first three attack scenarios, the monster attacks the first, second, and third city, respectively. In all of these scenarios, the mercenary already present in that city would be able to defeat the monster.

Let's consider the sixth, seventh, and eighth attack scenarios. In each of them, the monster attacks the third city with the same parameters $$$a_i$$$ and $$$b_i$$$. In the sixth scenario, when $$$c_i = 18$$$, the monster could be defeated by the mercenary from the second city if he chose the item described by the pair $$$(1, 5)$$$. Then his strength would be $$$3+1=4$$$, and his knowledge of magic would be $$$2+5=7$$$, resulting in $$$1 \cdot 4 + 2 \cdot 7 = 18 \geq 18$$$. In the seventh scenario, when $$$c_i=19$$$, only the mercenary from the first city could defeat the monster. By purchasing the items described by the pairs $$$(1, 2)$$$ and $$$(1, 5)$$$, his strength would be $$$1+1+1=3$$$, and his knowledge of magic would be $$$1+2+5=8$$$, resulting in $$$1 \cdot 3 + 2 \cdot 8 = 19 \geq 19$$$. In the eighth scenario, when $$$c_i=20$$$, no mercenary would be able to defeat the monster. Note that in the sixth scenario ($$$c_i=18$$$), the first mercenary would also be able to defeat the monster, but we are interested in the largest city number, so the answer is $$$2$$$.