You have been farming artifacts for Lady Yae Miko for three months. Unsurprisingly, your artifacts are as terrible as ever, with substats being either flat HP or defense.

You recall Xingqiu's perfect crit rate circlet, Ayaka's perfect attack sands, and Hu Tao's perfect attack feather. Farming artifacts has brought you much sorrow, but you still want to find a set of artifacts that maximizes the expected output of Lady Yae Miko.

Fig 1. Some "trash" artifacts.

In the game's mechanics, each character can equip artifacts in at most $L$ slots, with at most one artifact per slot. The character has a base crit rate $A$ and a base crit damage $B$. Assuming the sum of crit rate provided by all equipped artifacts is $a$ and the sum of crit damage is $b$, your output is solely related to $(A+a)(B+b)$ (here we have simplified the settings; in the actual game, expected damage is related to many factors such as attack, elemental mastery, and enemy defense). The higher this value, the higher your output.

You have farmed $n_i$ artifacts for the $i$-th slot, where the $j$-th artifact in the $i$-th slot has a crit rate of $a_{i,j}$ and a crit damage of $b_{i,j}$. You want to know, given the character's base crit rate $A$ and base crit damage $B$, the maximum value of $(A+a)(B+b)$ that can be achieved by configuring the artifacts. Since you have many characters, you need to answer multiple queries.

Given that the damage of a single ultimate can reach millions, you do not care about a difference of a few hundred in damage. Therefore, you do not need to provide the exact optimal solution. You only need to return a configuration that is sufficiently close to the optimal solution.

Input

This problem contains multiple test cases.

The first line contains two numbers $tid$ and $T$, representing the test package ID and the number of test cases, respectively. For the sample, $tid = 0$.

For each test case:

The first line contains a number $L$, representing the number of artifact slots.

The next $L$ lines describe all the artifacts you have farmed for each slot.

For each slot, the first line contains a positive integer $n_i$.

The next line contains $2 \times n_i$ floating-point numbers, where the $(2 \times j-1)$-th and $(2 \times j)$-th numbers represent the values of $a_{i,j}$ and $b_{i,j}$, respectively.

The next line contains a number $Q$.

The next $Q$ lines each contain two floating-point numbers $A$ and $B$, representing a query.

The input guarantees that floating-point numbers have at most two decimal places.

Output

For each query, output $L$ numbers on a single line. The $i$-th number $a_i$ indicates that the artifact you chose for the $i$-th slot is the $a_i$-th artifact from the $i$-th group in the input. Artifacts are indexed starting from 1.

Your answer is considered correct if and only if:

• Let $x$ be the value of $(A+a)(B+b)$ in your proposed configuration, $y$ be the value given by the reference solution, and $z$ be the value of the optimal solution.
• Your answer is considered correct if and only if $|x-y| \le 2500$.
• We guarantee that $|y-z| \le 2500$, so we ensure that when $z - x \le 2500$, your answer will definitely be judged as correct.

Examples

Input 1

0 1
2
2
1 2 3 4
2
1 4 3 2
2
1 1
5 1

Output 1

2 2 
2 1

Note 1

Among the artifacts of the first type, since the first artifact is not better than the second in either crit stat, the optimal solution will definitely choose the second artifact. When the second artifact slot chooses the first one, the crit rate bonus is 4 and the crit damage bonus is 8; when the second artifact slot chooses the second one, the crit rate bonus is 6 and the crit damage bonus is 6.

For the first query, the products obtained by the two schemes are $(4+1) \times (8+1) = 45$ and $(6+1) \times (6+1) = 49$, so we choose the second one.

For the second query, the products obtained by the two schemes are $(4+5) \times (8+1) = 81$ and $(6+5) \times (6+1) = 77$, so we choose the first one.

Input 2

0 1
4
2
1 2 3 4
2
1 4 3 2
2
1 10 5 1
2
1 5 10 1
5
1 1
5 1
10 1
10 2
100 3

Output 2

2 2 1 2 
2 1 1 2 
2 1 1 2 
2 1 1 2 
2 1 1 1

Subtasks

Subtask $1$ ($15\%$): $L \le 5, n \le 3$. $a_{i,j}, b_{i,j}$ are guaranteed to be integers and generated uniformly at random within the range.

Subtask $2$ ($20\%$): $L \le 30$. $a_{i,j}, b_{i,j}$ are guaranteed to be integers and generated uniformly at random within the range.

Subtask $3$ ($15\%$): $L \le 500$. $a_{i,j}, b_{i,j}$ are guaranteed to be integers and generated uniformly at random within the range.

Subtask $4$ ($15\%$): Guaranteed that $a_{i,j} + b_{i,j} = 100$.

Subtask $5$ ($35\%$): No special restrictions.

For all test cases, $1 \le T \le 100$, $1 \le \sum L \le 50000$, $1 \le n, Q \le 10$, $0 < a_{i,j}, b_{i,j} \le 100$, and $1 \le A, B \le 10^7$. The data guarantees that floating-point numbers $a_i, b_i$ are provided with at most two decimal places.