3.2 Weird Wizard

Score: 20pts

Time Limit: 2.00 sec

In a faraway land, there exists a sacred array of magical stones, each with a special energy. A powerful wizard has given you a task: to gradually remove these stones one by one in a specific order, based on a series of commands. Each command tells you to remove a stone from either the left or right side of the array. Before each removal, you must calculate the remainder of the total magical energy of the remaining stones when divided by a special number m. The total magical energy is defined as the product of all the remaining stones' energies. Your goal is to follow the wizard's instructions, outputting the remainder of the product of the array's elements after each command. If the command is 'L', you remove the leftmost stone; if it's 'R', you remove the rightmost. Continue this process until all the stones are removed.

Constraints

t(1≤t≤10^4)

n and m(1≤n≤2⋅10^5,1≤m≤10^4)

a1,a2,…,an(1≤ai≤10^4)

n and m(1≤n≤2⋅10^5,1≤m≤10^4)

a1,a2,…,an(1≤ai≤10^4)

Input Format

The first line contains an integer t - the number of test cases in the input. Then descriptions of test cases follow.

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

The first line contains two integers n and m — the initial length of the array a and the value to take the remainder by.

The second line contains n integers a1,a2,…,an — the elements of the array a

The third line contains a strings 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⋅10^5

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

The first line contains two integers n and m — the initial length of the array a and the value to take the remainder by.

The second line contains n integers a1,a2,…,an — the elements of the array a

The third line contains a strings 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⋅10^5

Output Format

For each test case, output n integers b1,b2,…,bn , where bi 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.

Example 1

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

Explanation:

The example is self explanatory

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

Explanation:

The example is self explanatory