CF1932C.LR-remainders

You are given an array $a$ of length $n$, a positive integer $m$, and a string of commands of length $n$. Each command is either the character 'L' or the character 'R'.

Process all $n$ commands in the order they are written in the string $s$. Processing a command is done as follows:

• First, output the remainder of the product of all elements of the array $a$ when divided by $m$.
• Then, if the command is 'L', remove the leftmost element from the array $a$, if the command is 'R', remove the rightmost element from the array $a$.

Note that after each move, the length of the array $a$ decreases by $1$, and after processing all commands, it will be empty.

Write a program that will process all commands in the order they are written in the string $s$ (from left to right).

给你一个长度为 $n$ 的数组 $a$、一个正整数 $m$，以及一个长度为 $n$ 的命令字符串。每个命令字符为 'L' 或 'R'。

按字符串 $s$ 中从左到右的顺序依次处理全部 $n$ 个命令。处理每个命令的操作如下：

• 首先，输出数组 $a$ 中所有元素乘积对 $m$ 取模所得的余数；
• 然后，若该命令为 'L'，则从数组 $a$ 中移除最左侧的元素；若该命令为 'R'，则从数组 $a$ 中移除最右侧的元素。

注意：每次操作后，数组 $a$ 的长度减少 $1$；当所有命令处理完毕后，数组 $a$ 将为空。

请编写一个程序，按字符串 $s$ 中从左到右的顺序处理全部命令。

The first line contains an integer $t$ ($1 \le t \le 10^4$) — the number of test cases in the input. Then descriptions of $t$ test cases follow.

Each test case of the input is given by three lines.

The first line contains two integers $n$ and $m$ ($1 \le n \le 2\cdot10^5, 1 \le m \le 10^4$) — the initial length of the array $a$ and the value to take the remainder by.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^4$) — the elements of the array $a$.

The third line contains a string $s$ consisting of $n$ characters 'L' and 'R'.

It is guaranteed that the sum of the values of $n$ for all test cases in a test does not exceed $2\cdot10^5$.

第一行包含一个整数 $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$ 的元素。

第三行包含一个由 $n$ 个字符 'L' 和 'R' 组成的字符串 $s$。

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

For each test case, output $n$ integers $b_1, b_2, \dots, b_n$, where $b_i$ is the remainder when dividing the product of all elements of the current state of the array $a$ by $m$ at the beginning of the execution of the $i$-th command.

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

In the first test case of the example:

• $3 \cdot 1 \cdot 4 \cdot 2 \bmod 6 = 24 \bmod 6 = 0$;
• $s_1 = \text{L}$, so we remove the first element and get the array $[1, 4, 2]$;
• $1 \cdot 4 \cdot 2 \bmod 6 = 8 \bmod 6 = 2$;
• $s_2 = \text{R}$, so we remove the last element and get the array $[1, 4]$;
• $1 \cdot 4 \bmod 6 = 4 \bmod 6 = 4$;
• $s_3 = \text{R}$, so we remove the last element and get the array $[1]$;
• $1 \bmod 6 = 1$;
• $s_4 = \text{L}$, so we remove the first element and get an empty array.

在示例的第一个测试用例中：

• $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}$，因此我们移除第一个元素，得到一个空数组。