All Tracks Algorithms Greedy Algorithms Basics of Greedy Algorithms Problem

The Ancient Algorithm
Tag(s):

Easy

Problem
Editorial
Analytics

In an alternate universe, while fighting Ebony Maw, Doctor Strange pulled his ace card and asked the help of alternate universe Doctor Strange to stopped Maw dead in his tracks. His trick was as follows:

  • Asked one of his alternate selves to write a list L of N integers.

  • Asked another of his alternate selves to provide three integers A, B, C and

  • Asked a third one 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 One’s secret Algorithm on this input.

 

We know that The Ancient Algorithm is as follows:

for i from 1 to N do

    if the ith letter of S is 'R'

        reverse L[i...N]

    else if the ith letter of S is 'A'

        add A to all numbers of L[i..N].

    else if the ith 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

 

Defeated Ebony Maw got furious when was beaten by Doctor Strange. He wants to learn the trick to gain the respect of the Black Order again. How about you help him?

Input

The 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 the 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.

Constraints:

  • 1 ≤ T ≤ 100
  • 1 ≤ N ≤ 1000
  • 0 ≤ L[i] ≤ 1018
  • 0 ≤ AB ≤ 1018
  • 2 ≤ C ≤ 1018
SAMPLE INPUT
2
3
1 1 1
2 3 1000
ARM
4
1 2 3 4
0 1 1000
AMAM
SAMPLE OUTPUT
3 3 9 
1 2 3 4 
Time Limit: 2.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

School of Engineering, CUSAT

Challenge Name

ALGO XTREME

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications

?