剑与暴击¶
参考时间限制：2 秒；内存限制：256 MiB。正式时限按目标环境标准程序的最慢用例中位数乘以 2，再向上取整至 0.5 秒。参见评测说明。
背景故事¶
你在游玩《+1 DMG Per Revive》时，获得了许多把剑。每把剑都能独立触发暴击，触发后提供自己的伤害倍率；多把剑同时触发时，这些倍率相乘。
现在，你要挑战死亡之塔。这里的战斗很依赖单次伤害峰值，而暴击倍率是决定峰值的重要因子。面对不同楼层，你列出了若干个目标倍率，想知道同一套剑的一次攻击达到每个目标的概率。
形式化问题描述¶
你拥有 \(n\) 把剑。第 \(i\) 把剑对应两个整数 \(p_i,m_i\) ：它以 \(p_i/10^6\) 的概率触发暴击。触发时贡献倍率 \(m_i\) ，未触发时贡献倍率 \(1\) .所有剑是否触发的事件相互独立。
一次攻击的总暴击倍率为所有剑贡献倍率的乘积。若没有剑触发，总倍率为 \(1\) .所有剑都会参与判定，不需要选择或装备其中一部分。
给定 \(q\) 个整数阈值 \(K_1,\ldots,K_q\) .对每个阈值，分别求一次攻击的总暴击倍率大于等于该阈值的概率。各询问使用同一套剑；它们询问各自的概率，不要求多个事件同时发生，也不改变后续询问的剑或概率。
令 \(P=998244353\) .将所求概率写成最简分数 \(A/B\) ，输出 \(AB^{-1}\bmod P\) 的最小非负余数。由于每把剑的概率分母均为 \(10^6\) ，最简分母一定与 \(P\) 互质，因此答案总有定义。
只对概率答案取模。倍率、阈值及它们之间的大小比较都按原整数含义处理。
输入格式¶
第一行一个整数 \(T\) ，表示独立测试组的数量。
每组测试依次包含：
- 第一行两个整数 \(n,q\) ，表示剑的数量和询问数量。
- 接下来 \(n\) 行，每行两个整数 \(p_i,m_i\) .
- 接下来 \(q\) 行，每行一个整数 \(K_j\) ，使用普通十进制记法给出。
输出格式¶
按测试组和询问的输入顺序，对每个询问输出一行模 \(P\) 的概率。
样例 1¶
输入¶
1
3 6
500000 2
250000 3
1000000 5
1
5
10
15
30
31
输出¶
1
1
374341633
748683265
873463809
0
样例 2¶
输入¶
1
2 3
500000 999999937
500000 999999929
999999866000004472
999999866000004473
999999866000004474
输出¶
748683265
748683265
0
样例 3¶
输入¶
2
2 2
0 1000000000
743921 1
1
2
3 2
1000000 1000000000
1000000 1000000000
1000000 1000000000
1
1000000000000000000
输出¶
1
0
1
1
样例解释¶
样例 1 中第三把剑必定触发。总倍率可能为 \(5,10,15,30\) .达到 \(10\) 倍需要前两把剑至少一把触发，概率为 \(5/8\) ；达到 \(15\) 倍需要第二把剑触发，概率为 \(1/4\) ；达到 \(30\) 倍需要前两把剑同时触发，概率为 \(1/8\) .
样例 2 中两把剑同时触发的倍率为 \(999999866000004473\) ，概率为 \(1/4\) .前两个阈值均需要两把剑同时触发；第三个阈值无法达到。
样例 3 的第一组总倍率恒为 \(1\) ；第二组三把剑必定触发，数学上的总倍率为 \(10^{27}\) ，两个询问的答案均为 \(1\) .求解时只需保留与阈值比较所需的信息，无须存储这个完整乘积。
数据范围与保证¶
对于 100% 的数据：
- \(1\le T\le8\) ，\(1\le n\le2000\) ，\(1\le q\le5600\) .
- \(0\le p_i\le10^6\) ，\(1\le m_i\le10^9\) ，\(1\le K_j\le10^{18}\) .
- 每组测试至少满足以下条件之一：\(n\le44\) ，或所有阈值均不超过 \(2\cdot10^7\) .
- 所有输入数据均为整数，均可用有符号 64 位整数保存。无需计算所有剑倍率的完整乘积；本题可以仅用 64 位整数运算精确求解。
为说明一个输入文件内的总规模，记第 \(t\) 组的剑数和询问数为 \(n_t,q_t\) .设 \(\mathcal A\) 为所有阈值均不超过 \(2\cdot10^7\) 的测试组集合，\(\mathcal B\) 为其余测试组集合，还保证一个输入文件内的询问总数 \(\sum_t q_t\le5600\) ，并保证：
本题的多询问规格、整数范围、数据分组与性能约束由 Codex（GPT-6）设计。
| 分值比例 | 额外条件 |
|---|---|
| 20% | 每组测试均满足 \(n\le18\) |
| 30% | 所有阈值均不超过 \(2\cdot10^7\) |
| 20% | 每组测试均满足 \(n\le34\) |
| 30% | 无额外条件 |
共 10 个测试点，每点占 10%；完整生成配方见测试说明。