你给八重神子宫司大人刷了三个月的圣遗物。不出意外的,你的圣遗物一如既往的烂,副词条不是小生命就是防御力。
你想起了行秋的极品暴击头,神里的极品攻击沙,胡桃的极品大攻击羽毛。刷圣遗物带给了你很多的悲伤,但是你仍然想要找一套圣遗物,使得在这套圣遗物下八重神子宫司大人的期望输出能够最大化。
Fig 1. 一些寄品圣遗物.
在游戏设定中,每位角色最多可以佩戴 L 个位置的圣遗物,每个位置只能佩戴至多一个圣遗物。角色有基础暴击率 A 和基础暴击伤害 B。假设佩戴的所有圣遗物提供暴击率之和为 a,暴击伤害之和为 b,则你的输出仅仅和 (A+a)(B+b) 相关(这里我们简化了设定,实际游戏当中期望伤害和攻击力,元素精通,敌人防御力等许多元素相关)。该值越高,你的输出越高。
你在第 i 个位置刷了 ni 个圣遗物,第 i 个位置的第 j 个圣遗物的暴击率为 ai,j,暴击伤害为 bi,j。你想要知道,在角色基础暴击率为 A,基础暴击伤害为 B 的前提条件下,通过配置圣遗物能够达到的最大的 (A+a)(B+b) 的值。由于你有着众多的角色,你需要回答多组询问。
在单次大招上伤害百万的前提下你并不关心几百的伤害差距,因此你不需要给出最优解的精确的数字。你只需要返回一个足够接近最优解的方案即可。
Input
本题有多组测试数据。
第一行两个数字 tid,T,分别表示测试包编号和表示测试数据组数。对于样例则有 tid=0。
对于每组测试数据:
第一行一个数字 L,表示圣遗物位置的个数。
接下来 L 行,每两行形容在某一个位置上你刷出来的所有圣遗物。
对于每个位置,第一行一个正整数 ni。
接下来一行 2×ni 个浮点数,第 2×j−1 和 2×j 个数字分别表示 ai,j,bi,j 的值。
接下来一个数字 Q。
接下来 Q 行,一行两个浮点数 A,B,表示一次询问。
输入保证浮点数在小数点后最多保留两位数字。
Ouptput
对于每次询问,一行 L 个数字,第 i 个数字 ai 表示在第 i 个位置上你选择的圣遗物恰好是输入的第 i 组的第 ai 个圣遗物,这里我们认为圣遗物编号从 1 开始。
你的答案被认为是正确的当且仅当:
- 假定你给出的方案中 (A+a)(B+b) 的值为 x, 参考解给出的值为 y, 最优解给出的值为 z。
- 你的答案被认为是正确的当且仅当 |x−y|≤2500。
- 我们保证 |y−z|≤2500,因此我们保证 z−x≤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)×(8+1)=45 和 (6+1)×(6+1)=49,因此我们选择第二种。
在第二个询问的时候,两种方案得到的乘积分别是 (4+5)×(8+1)=81 和 (6+5)×(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≤5,n≤3。保证 ai,j,bi,j 为整数,且在范围内均匀随机生成。
Subtask 2 (20%): L≤30。保证 ai,j,bi,j 为整数,且在范围内均匀随机生成。
Subtask 3 (15%): L≤500。保证 ai,j,bi,j 为整数,且在范围内均匀随机生成。
Subtask 4 (15%): 保证 ai,j+bi,j=100。
Subtask 5 (35%): 无特殊限制。
对于所有测试数据,满足 1≤T≤100,1≤∑L≤50000,1≤n,Q≤10,0<ai,j,bi,j≤100,1≤A,B≤107。数据保证浮点数 ai,bi 保留至最多小数点后两位。
\end{problem}