你给八重神子宫司大人刷了三个月的圣遗物。不出意外的，你的圣遗物一如既往的烂，副词条不是小生命就是防御力。

你想起了行秋的极品暴击头，神里的极品攻击沙，胡桃的极品大攻击羽毛。刷圣遗物带给了你很多的悲伤，但是你仍然想要找一套圣遗物，使得在这套圣遗物下八重神子宫司大人的期望输出能够最大化。

Fig 1. 一些寄品圣遗物.

在游戏设定中，每位角色最多可以佩戴 $L$ 个位置的圣遗物，每个位置只能佩戴至多一个圣遗物。角色有基础暴击率 $A$ 和基础暴击伤害 $B$。假设佩戴的所有圣遗物提供暴击率之和为 $a$，暴击伤害之和为 $b$，则你的输出仅仅和 $(A+a)(B+b)$ 相关(这里我们简化了设定，实际游戏当中期望伤害和攻击力，元素精通，敌人防御力等许多元素相关)。该值越高，你的输出越高。

你在第 $i$ 个位置刷了 $n_i$ 个圣遗物，第 $i$ 个位置的第 $j$ 个圣遗物的暴击率为 $a_{i,j}$，暴击伤害为 $b_{i,j}$。你想要知道，在角色基础暴击率为 $A$，基础暴击伤害为 $B$ 的前提条件下，通过配置圣遗物能够达到的最大的 $(A+a)(B+b)$ 的值。由于你有着众多的角色，你需要回答多组询问。

在单次大招上伤害百万的前提下你并不关心几百的伤害差距，因此你不需要给出最优解的精确的数字。你只需要返回一个足够接近最优解的方案即可。

Input

本题有多组测试数据。

第一行两个数字 $tid,T$，分别表示测试包编号和表示测试数据组数。对于样例则有 $tid = 0$。

对于每组测试数据:

第一行一个数字 $L$，表示圣遗物位置的个数。

接下来 $L$ 行，每两行形容在某一个位置上你刷出来的所有圣遗物。

对于每个位置，第一行一个正整数 $n_i$。

接下来一行 $2 \times n_i$ 个浮点数，第 $2 \times j-1$ 和 $2 \times j$ 个数字分别表示 $a_{i,j},b_{i,j}$ 的值。

接下来一个数字 $Q$。

接下来 $Q$ 行，一行两个浮点数 $A,B$，表示一次询问。

输入保证浮点数在小数点后最多保留两位数字。

Ouptput

对于每次询问，一行 $L$ 个数字，第 $i$ 个数字 $a_i$ 表示在第 $i$ 个位置上你选择的圣遗物恰好是输入的第 $i$ 组的第 $a_i$ 个圣遗物，这里我们认为圣遗物编号从 1 开始。

你的答案被认为是正确的当且仅当:

• 假定你给出的方案中 $(A+a)(B+b)$ 的值为 $x$, 参考解给出的值为 $y$, 最优解给出的值为 $z$。
• 你的答案被认为是正确的当且仅当 $|x-y| \le 2500$。
• 我们保证 $|y-z| \le 2500$，因此我们保证 $z - x \le 2500$ 时候，你的答案一定被判断为正确。

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

Notes 1

在第一个类的圣遗物之中，由于第一个圣遗物双爆属性都没有第二个好，因此最优方案中必定会选择第二个圣遗物。在第二个圣遗物选择第一个的时候，暴击加成为 4，爆伤加成为 8; 在第二个圣遗物选择第二个的时候，暴击加成为 6，爆伤加成为 6

在第一个询问的时候，两种方案得到的乘积分别是 $(4+1) \times (8+1) = 45$ 和 $(6+1) \times (6+1) = 49$，因此我们选择第二种。

在第二个询问的时候，两种方案得到的乘积分别是 $(4+5) \times (8+1) = 81$ 和 $(6+5) \times (6+1) = 77$，因此我们选择第一种。

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

Scoring

Subtask $1$ ($15\%$): $L \le 5, n \le 3$。保证 $a_{i,j},b_{i,j}$ 为整数，且在范围内均匀随机生成。

Subtask $2$ ($20\%$): $L \le 30$。保证 $a_{i,j},b_{i,j}$ 为整数，且在范围内均匀随机生成。

Subtask $3$ ($15\%$): $L \le 500$。保证 $a_{i,j},b_{i,j}$ 为整数，且在范围内均匀随机生成。

Subtask $4$ ($15\%$): 保证 $a_{i,j} + b_{i,j} = 100$。

Subtask $5$ ($35\%$): 无特殊限制。

对于所有测试数据，满足 $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,1 \le A,B \le 10^7$。数据保证浮点数 $a_i,b_i$ 保留至最多小数点后两位。

\end{problem}