题目描述

小 I 经营着一个电玩城，最近引进的新型老虎机深受欢迎。

作为经营者，小 I 首先需要设定老虎机的状态。老虎机的状态为一个三元组 $(l,S,\mathbf{p})$，其中

• $l$ 是一个正整数；
• $S$ 是一个非空字符串集合，其中所有的字符串均是长度为 $l$ 的 01 串；
• $\mathbf{p}$ 是一个长度为 $l$ 的实数序列 $p_0,p_1,\dots,p_{l-1}$，其中对于任意 $0 \le i \le l - 1$，$0 < p_i \le 1$。

设定好状态后即可开始游戏。每一轮游戏的流程如下：

• 玩家首先获得老虎机的状态 $(l,S,\mathbf{p})$。
• 老虎机内部选择一个串 $s \in S$ 作为答案串，玩家需要通过与老虎机进行若干次交互得到答案串。
  • 每一次交互中，玩家投入一个游戏币并拉下老虎机的拉杆，然后老虎机的界面中会出现一个长度为 $l$ 的信息串 $t$。对于 $0 \le i \le l - 1$，$t_i$ 有 $p_i$ 的概率为 $s_i$，有 $(1-p_i)$ 的概率为 ?。
  • 交互过程中生成信息串进行的所有随机过程两两独立。
• 当玩家可以根据老虎机的状态和交互得到的若干信息串唯一确定答案串后，即可将答案串输入老虎机并结束游戏、获得奖励。

小 I 设定好了一个状态，但还不知道设定多少奖励。为了让奖励和难度匹配，小 I 想知道：对于 $S$ 中的每个串 $t$，在玩家以最优策略游玩（即一旦可以唯一确定答案串就结束游戏）的情况下，若答案串为 $t$，玩家期望需要投入多少游戏币。

由于小 I 不喜欢实数，你需要将答案对 $998244353$ 取模。

输入格式

本题有多组测试数据。 第一行一个整数 $T$ 表示测试数据组数，接下来依次输入每组测试数据。

对于每组测试数据，

• 第一行两个整数 $l,n$，表示字符串长度和 $S$ 的大小。
• 第二行 $l$ 个整数 $c_0,c_1,\dots,c_{l-1}$，其中 $p_i = \frac{c_i}{10^4}$。
• 接下来 $n$ 行，第 $i$ 行一个长度为 $l$ 的 01 串 $s_i$，描述 $S$ 中的一个字符串。

输出格式

对于每组测试数据输出 $n$ 行，第 $i$ 行表示答案串为 $s_i$ 时，在最优策略下玩家期望投入多少游戏币，对 $998244353$ 取模，容易证明在题目限制下这个值总是在模意义下存在。

4
1 2
5000
0
1
2 3
1 10000
00
01
10
1 1
1
1
3 4
8888 7777 5555
000
010
101
110

2
2
10000
1
10000
0
209031157
194428714
835313860
674719626

提示

【样例解释 #1】

• 对于第一组测试数据，每一次交互有 $\frac{5000}{10000} = \frac{1}{2}$ 的概率知道答案串是 $0$ 还是 $1$，有 $\frac{1}{2}$ 的概率不能获得信息，因此期望游戏币数为 $\sum_{i=1}^{+\infty} \frac{i}{2^i} = 2$。
• 对于第二组测试数据，每一次交互都可以得到字符串的第二位，有 $\frac{1}{10000}$ 的概率得到字符串的第一位。第二个字符串为答案串时可以通过字符串的第二位唯一确定，而其他两个字符串为答案串时必须要得到字符串的第一位。
• 对于第三组测试数据，由于 $|S| = 1$，所以不需要任何交互就可以确定答案串。
• 对于第四组测试数据，我有一个绝妙的解释，可这里空间太小写不下。

【数据范围】

对于所有测试数据，$1 \le T \le 10$，$1 \le l \le 15$，$1 \le n \le 2^l$，$1 \le c_i \le 10^4$，$s_1,\dots,s_n$ 为两两不同的长度为 $l$ 的 01 串。

【后记】

“喂喂喂，未成年人不准进入电玩城！什么？你们说你们要进去学算法竞赛？谁信你的鬼话！”

【题目来源】

来自 2023 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2023）决赛。

题解等资源可在 https://github.com/THUSAAC/THUPC2023 查看。