给定一个长度为 $$$n$$$ 的数组 $$$a$$$、一个正整数 $$$m$$$ 和一个长度为 $$$n$$$ 的命令字符串。每个命令要么是字符“L”,要么是字符“R”。
按照字符串 $$$s$$$ 中写入的顺序处理所有 $$$n$$$ 命令。处理命令的过程如下:
- 首先,输出数组 $$$a$$$ 所有元素的乘积除以 $$$m$$$ 的余数。
- 然后,如果命令是“L”,则从数组$$$a$$$中删除最左边的元素,如果命令是“R”,则从数组$$$a$$$中删除最右边的元素。
注意,每次移动后,数组$$$a$$$的长度会减少$$$1$$$,处理完所有命令后,它将为空。
编写一个程序,按照字符串 $$$s$$$ 中写入的顺序(从左到右)处理所有命令。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 输入中测试用例的数量。然后是 $$$t$$$ 测试用例的描述。
输入的每个测试用例由三行给出。
第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n \le 2\cdot10^5, 1 \le m \le 10^4$$$) — 数组 $$$a$$$ 的初始长度和取余数的值。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^4$$$) — 数组 $$$a$$$ 的元素。
第三行包含一个字符串 $$$s$$$,由 $$$n$$$ 字符“L”和“R”组成。
保证一次测试中所有测试用例的$$$n$$$值之和不超过$$$2\cdot10^5$$$。
输出
对于每个测试用例,输出 $$$n$$$ 整数 $$$b_1, b_2, \dots, b_n$$$,其中 $$$b_i$$$ 是在执行第 $$$i$$$ 命令开始时将数组 $$$a$$$ 当前状态的所有元素的乘积除以 $$$m$$$ 的余数。
示例
输入 #1
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
输出 #1
0 2 4 1 0 0 0 0 0 0 0 0 4 4 4 0
注意
在示例的第一个测试用例中:
- $$$3 \cdot 1 \cdot 4 \cdot 2 \bmod 6 = 24 \bmod 6 = 0$$$;
- $$$s_1 = \text{L}$$$,所以我们删除第一个元素并得到数组 $$$[1, 4, 2]$$$;
- $$$1 \cdot 4 \cdot 2 \bmod 6 = 8 \bmod 6 = 2$$$;
- $$$s_2 = \text{R}$$$,所以我们删除最后一个元素并得到数组$$$[1, 4]$$$;
- $$$1 \cdot 4 \bmod 6 = 4 \bmod 6 = 4$$$;
- $$$s_3 = \text{R}$$$,所以我们删除最后一个元素并得到数组$$$[1]$$$;
- $$$1 \bmod 6 = 1$$$;
- $$$s_4 = \text{L}$$$,因此我们删除第一个元素并得到一个空数组。