Vidhi went to a magic show last week where she was astounded by a magic trick performed by the great Mandwarf, the brown. His trick was as follows :

Ask a volunteer from the audience to write down a list L of N integers.


Ask another volunteer from the audience to provide three integers A, B, C


Ask another volunteer from the audience to provide N length string called S where each letter is either 'R', 'A' or 'M'


Close his eyes for a split second and give the output of The Ancient Algorithm on this input.

We all know that The Ancient Algorithm is as follows :

for i from 1 to N do

if i^th letter of S is 'R'
    reverse L[i...N]
else if i^th letter of S is 'A'
    add A to all numbers of L[i..N].
else if i^th letter of S is 'M'
    multiply B to all numbers of L[i..N].

for all number in L[i..N], module them by C.

announce L[i] out loud

end

Vidhi's boyfriend got jealous when he saw her getting impressed by Mandwarf, the brown's wisdom. He wants to learn the trick to gain her undivided admiration. How about you help him?

Constraints:
1 ≤ T ≤ 100
1 ≤ N ≤ 1000
0 ≤ L[i] ≤ 10^18
0 ≤ A,B ≤ 10^18
2 ≤ C ≤ 10^18

Input
First line contains a single integer T, denoting the number of test cases. Then follow T test case scenarios. Each test case begins with an integer N, the size of the list L. Then in next line, you'd find N space separated integers - the list L itself. In next line, there'd be three space separated integers A, B, C followed by string S in the next line.

Output
For each test case you've to output N space separated integers - the numbers announced by Mandwarf, the brown.

Example

Input:
2
3
1 1 1
2 3 1000
ARM
4
1 2 3 4
0 1 1000
AMAM

Output:
3 3 9
1 2 3 4

见题面

见题面