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

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

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

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

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

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

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

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

对于每组测试数据，

• 第一行两个整数 $l,n$，表示字符串长度和  $S$ 的大小。
• 第二行 $l$ 个整数 c₀,c1,…,cl−1，其中 pi=ci / 10^4。
• 接下来 $n$ 行，第 $i$ 行一个长度为 $l$ 的 01 串 s_i，描述 $S$ 中的一个字符串。

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

动态规划