Description

前言：

考虑这样一个过程：初始我们有一个长度为l的字符串S和一个空栈，然后我们依次对S的每个字符 S1, S2, ...,Si执行操作；对字符c的操作是指，如果栈为空或者栈顶字符不为c,就将c入栈；否则，不仅不入栈，而且将栈顶的c弹出栈。执行完所有操作后，我们将栈中的字符，从栈底到栈顶依次输出，得到字符串 t.从字符串S (原串）到字符串t (结果串）的变换，我们称之为栈相消变换。

例如，对于原串s1 ="ABBB"，它做栈相消变换后的结果串是"AB”，具体过程如下： 1.操作si='A'，栈变成['A'](从栈底到栈顶，下同）；

2.操作S2 = 'B'，栈变成['A'，'B'];

3.操作S3= 'B'，栈变成[’A'];

4.操作 S4 = ’B’，栈变成[’A’, ’B’]。

Nayiz是21世纪的计算机科学家，在某个宁静的午后，他邂逅了一个高贵的王室公主，Niyiz。

Niyiz对计算机科学也有着浓厚的兴趣，她深深地折服于Nayiz的才华，在征得她父皇的同意下，Nayiz 被宣召进王室，成为了 Niyiz的导师，教授她所有的计算机知识（当然也包括栈相消变换)。

随着Nayiz和Niyiz的朝夕相处，发生增长的不仅仅是公主的计算机知识，更重要的是，他们之间纯粹、 美好的爱情也发生了萌芽。但正如故事的套路一般，Niyiz的父王得知真相后勃然大怒，一气之下将Nayiz驱 逐出国，而Niyiz也被父王软禁了起来。

不幸的Nayiz回到中国后，竟然还染上了新型冠状病毒，然而出于对公主的一往情深，他还是连续给Niyiz 写了 520封信，但无一例外地都被国王销毁。

但这怎么能难倒天才的计算机科学家Nayiz，在生命弥留之际，Nayiz寄出了最后一封情书。

国王拿到这封情书之后有点懵，因为上面只有两个字符串s和t，而每个字符串都只包含字符’A’,’B’。国王想了半天也想不出来这是什么，于是他大胆猜测这只是Nayiz心智丧失的表现，为了让他的女儿Niyiz死心，国王便将这封信交给了她。

接到情书的Niyiz大喜过望，她当然知道这是什么丨这是类似于计算机01编码的编码丨由于太过兴奋，Niyiz不小心倒出了手上的咖啡，导致字符串s有些位置已经分辨不清楚了。Niyiz懊悔不已，但好消息是t还完好如初，她也清楚t的某个前缀是计算机中为了传输安全，对s做完找相消变换的字符串。为了解读Nayiz留给她的信息，Niyiz必须尝试所有的可能性，但她也清楚，她粗心大意所造成的后果是不可估量的, 她首先想搞清一点事情，对于t的每一个前缀t[1...i]，有多少种可能的原串s，使得s做完找相消变换后的 结果恰好是t[1...i]。

Input Format

第一行是数据组数T。

每一组数据有三行，第一行是两个整数n,m。

第二行是一个长度为n,只包含’A’，’B’，’?’三种字符的字符串，表示有些位置分辨不清的字符串s。

第三行是一个长度为m,只包含’A’，’B’两种字符的字符串t。

Output Format

对每一组数据输出一行，共m + 1个整数，第i个数表示t[1..i - 1]的答案，对998244353取模（特别 地，第1个数表示空串时的答案）

Sample

样例输人

4
45
AB??
ABABB
56
BAB??
BABABA
55
AB???
ABABA
56
BABB?
BABBAB

样例输出

102010
0102010
030301
0101000

Hint

对于 10% 的数据，1 =< n,m <= 20,∑ n <= 100, ∑ m <= 100 ；

对于 30% 的数据，1= < n, m <= 100, ∑ n <= 500, ∑ m <= 500 ；

对于 100% 的数据，1 =< n,m <= 100000, ∑n <= 1000000, ∑m <= 1000000。