C. LR-余数

每个测试的时间限制：2 秒
内存限制：256 兆字节

给定一个长度为 $n$ 的数组 $a$、一个正整数 $m$ 和一个长度为 $n$ 的指令字符串。
每个指令是字符 'L' 或 'R'。

按字符串 $s$ 中给出的顺序处理所有 $n$ 条指令。处理一条指令的过程如下：

1. 首先，输出数组 $a$ 中所有元素的乘积除以 $m$ 的余数。
2. 然后，如果指令是 'L'，则移除数组 $a$ 中最左边的元素；如果指令是 'R'，则移除数组 $a$ 中最右边的元素。

注意：在每一步之后，数组 $a$ 的长度减少 $1$，并且处理完所有指令后，数组将为空。

编写一个程序，按照字符串 $s$ 中的顺序（从左到右）处理所有指令。

输入

第一行包含一个整数 $t$（$1 \le t \le 10^4$）—— 输入中测试用例的数量。
接下来是 $t$ 个测试用例的描述。

每个测试用例由三行给出：

• 第一行包含两个整数 $n$ 和 $m$（$1 \le n \le 2 \cdot 10^5$，$1 \le m \le 10^4$）—— 数组 $a$ 的初始长度和取余的模数。
• 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^4$）—— 数组 $a$ 的元素。
• 第三行包含一个由 $n$ 个字符 'L' 和 'R' 组成的字符串 $s$。

保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

输出

对于每个测试用例，输出 $n$ 个整数 $b_1, b_2, \dots, b_n$，其中 $b_i$ 是在执行第 $i$ 条指令开始时，当前状态数组 $a$ 的所有元素的乘积除以 $m$ 的余数。

示例

输入

4
4 6
3 1 4 2
LRRL
5 1
1 1 1 1 1
LLLLL
6 8
1 2 3 4 5 6
RLLLRR
1 10000
10000
R

输出

0 2 4 1 
0 0 0 0 0 
0 0 0 4 4 4 
0 

示例解释

在第一个测试用例中：

• $3 \cdot 1 \cdot 4 \cdot 2 \mod 6 = 24 \mod 6 = 0$；
• $s_1 = L$，所以移除第一个元素，得到数组 $[1,4,2]$；
• $1 \cdot 4 \cdot 2 \mod 6 = 8 \mod 6 = 2$；
• $s_2 = R$，所以移除最后一个元素，得到数组 $[1,4]$；
• $1 \cdot 4 \mod 6 = 4 \mod 6 = 4$；
• $s_3 = R$，所以移除最后一个元素，得到数组 $[1]$；
• $1 \mod 6 = 1$；
• $s_4 = L$，所以移除第一个元素，得到空数组。