Problem Description

对于一个长度为$n$的字符串$S$,我们可以定义$S^i$为将字符串$S$的第$i$位至第$n$位依次翻转所得到的字符串。

例如：对于一个字符串$abcde$,我们定义$S^3$为$abedc$。

现在给定字符串$T$，你需要对于$1-n$的每个$i$，求出$T$在$S^i$的出现次数。

Input

第一行输入一行一个正整数$Q[1\leq Q\leq 10]$,代表数据的组数。

对于每组数据，第一行输入一行两个正整数$n,m[1\leq n,m\leq 10^5]$,代表字符串$S$和$T$的长度。

接下来两行分别读入两行小写字符串，分别为$S$串和$T$串，数据保证所有$S$串的总长不超过$10^6$，所有$T$串的总长也不超过$10^6$。

Output

对于每组数据，输出$n$行$n$个整数，第$i$行代表$T$在$S^i$中出现的次数。

2
5 2
aabab
ab
4 4
aaba
aaba

1
2
2
1
2
0
1
0
1