A. 送给世界的礼物
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
魔女宁宁决定送给世界一个礼物，但是她只有 $$$k$$$ 个盒子，第 $$$i$$$ 个盒子上有一个字符串 $$$T_i$$$，同时她有 1 个糖果串 $$$S$$$，从左到右排成一行，每个糖果用一个小写字母表示，她会将糖果串分成 $$$k$$$ 份，并放入每个盒子。她按照如下步骤去放：
  1. 首先宁宁走到第一个盒子前，选择 $$$S$$$ 串的一个前缀（可以为空）$$$P_1$$$，$$$P_1$$$ 是第一个盒子 $$$T_1$$$ 的子串。
  2. 将 $$$P_1$$$ 从 $$$S$$$ 中截断取出，放入第一个盒子。此时 $$$S$$$ 不再保留前缀 $$$P_1$$$
  3. 宁宁走到第二个盒子前，选择 $$$S$$$ 串的一个前缀（可以为空）$$$P_2$$$，$$$P_2$$$ 是第二个盒子 $$$T_2$$$ 的子串。
  4. 将 $$$P_2$$$ 从 $$$S$$$ 中截断取出，放入第二个盒子。此时 $$$S$$$ 不再保留前缀 $$$P_2$$$
  5. 重复上述步骤，按照顺序走完第 $$$3,4,5...k$$$ 个盒子，每次取出的一个前缀 $$$P_i$$$（可以为空），必须是第 $$$i$$$ 个盒子 $$$T_i$$$ 的子串, 并且取完后 $$$S$$$ 不会保留前缀 $$$P_i$$$。
  6. 宁宁走完第 $$$k$$$ 个盒子时，恰好把原本的糖果串放完。
  7. 将糖果放在盒子里之后，宁宁会每个盒子上贴一个数字 $$$b_i$$$，表示放入第 $$$i$$$ 个盒子的糖果串长度。

子串的定义：一个字符串删除任意长度（可以为0）的前缀、后缀之后剩下的字符串。空串是任意字符串的子串。

显然会有很多方式进行选择，魔女宁宁想知道，最后盒子上的数字序列，字典序最小的是哪一种？

形式化的，你需要使得数列 $$$b_1,b_2,b_3...b_k$$$ 字典序最小。注意 $$$b_i \ge 0$$$，也就是说，盒子里可以是空的

例如：

存在四个盒子：$$$ababc$$$ ，$$$ggoppo$$$，$$$fft$$$, $$$wwwwk$$$ 。

糖果串为：$$$baboppowk$$$。

走到第一个盒子时，取出 $$$bab$$$，此时 $$$S$$$ 剩余 $$$oppowk$$$；

走到第二个盒子时，取出$$$oppo$$$，此时 $$$S$$$ 剩余 $$$wk$$$；

第三个时，只能取出空串，此时 $$$S$$$ 剩余 $$$wk$$$；

第四个时，取出 $$$wk$$$，恰好取完，此时 $$$S$$$ 为空；

那么可以将糖果串分为 ： $$$bab-oppo-$$$空$$$-wk$$$ 三段(四份)。显然他们是对应四个盒子的子串。

最后的盒子上标上的数字为: $$$3,4,0,2$$$

Input

第一行一个数字 $$$T$$$ ，表示测试组数。

每一个测试组由以下输入组成：

  1. 第一行输入两个整数 $$$k,n$$$ ，$$$k \le 10, n \le 5 \times 10^4$$$
  2. 第二行包括 $$$k$$$ 个字符串 $$$T_1, T_2....T_k$$$ ，表示每个盒子上的字符串, $$$|T| \le 1 \times 10 ^ 5$$$
  3. 第三行包括一个字符串 $$$S$$$，表示糖果串。

保证字符串只存在小写字母，输入的总字符串长度 $$$ \le 2 \times 10 ^ 6$$$

Output

输出 $$$T$$$ 行，每行 $$$k$$$ 个非负整数 $$$b_1,b_2,b_3,\ldots ,b_k$$$ ,用空格隔开，行尾没有多余空格。

你需要保证数列$$$b_1,b_2,b_3,\ldots ,b_k$$$字典序最小。数据保证每个测试组都有解。

Example
Input
5
3 19
iamdata juststructure notstring
datastructurestring
3 8
iiiiii llove yesxtu
ilovextu
3 3
not aurora st
nst
3 15
kids mother people
kidmotherpeople
3 6
bbbb bbbccc dddd
bbbcdd
Output
4 9 6
1 4 3
1 0 2
3 6 6
0 4 2