311088: CF1932C. LR-remainders

C. LR-remainderstime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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).

Input

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$.

Output

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.

ExampleInput

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

Output

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

Note

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.

题目大意：给定一个长度为n的数组a，一个正整数m，以及一个长度为n的命令字符串s。每个命令是字符'L'或字符'R'。按照s中的顺序处理所有n个命令。处理命令的步骤如下：

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

注意，每次操作后，数组a的长度减少1，在处理所有命令后，数组将变为空。

输入数据格式：

第一行包含一个整数t（1≤t≤10^4），表示输入的测试用例数。接下来是t个测试用例的描述。

每个测试用例包含三行：

第一行包含两个整数n和m（1≤n≤2×10^5, 1≤m≤10^4），分别表示数组a的初始长度和取余的值。

第二行包含n个整数a_1, a_2, …, a_n（1≤a_i≤10^4），表示数组a的元素。

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

保证所有测试用例中n的和不超过2×10^5。

输出数据格式：

对于每个测试用例，输出n个整数b_1, b_2, …, 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
```题目大意：给定一个长度为n的数组a，一个正整数m，以及一个长度为n的命令字符串s。每个命令是字符'L'或字符'R'。按照s中的顺序处理所有n个命令。处理命令的步骤如下： 1. 首先输出数组a所有元素乘积除以m的余数。 2. 如果命令是'L'，则从数组a中移除最左边的元素；如果命令是'R'，则移除最右边的元素。 注意，每次操作后，数组a的长度减少1，在处理所有命令后，数组将变为空。 输入数据格式： 第一行包含一个整数t（1≤t≤10^4），表示输入的测试用例数。接下来是t个测试用例的描述。 每个测试用例包含三行： 第一行包含两个整数n和m（1≤n≤2×10^5, 1≤m≤10^4），分别表示数组a的初始长度和取余的值。 第二行包含n个整数a_1, a_2, …, a_n（1≤a_i≤10^4），表示数组a的元素。 第三行包含一个由'L'和'R'组成的字符串s。 保证所有测试用例中n的和不超过2×10^5。 输出数据格式： 对于每个测试用例，输出n个整数b_1, b_2, …, 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 ```