A5670 | 「THUPC 2023」老虎机

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

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

- $l$ 是一个正整数；
- $S$ 是一个非空字符串集合，其中所有的字符串均是长度为 $l$ 的 01 串；
- $\mathbf{p}$ 是一个长度为 $l$ 的实数序列 $p_0,p_1,\cdots,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,\cdots,c_{l-1}$，其中 $p_i = \frac{c_i}{10^4}$。
- 接下来 $n$ 行，第 $i$ 行一个长度为 $l$ 的 01 串 $s_i$，描述 $S$ 中的一个字符串。

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