You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
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 Format
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 Format
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.

## Examples
```input
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.

Now solve the problem and return the code.