All Tracks Algorithms Greedy Algorithms Basics of Greedy Algorithms Problem

The Ancient Algorithm
No tags

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



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?


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.


For each test case, you've to output N space separated integers.


  • 1 ≤ T ≤ 100
  • 1 ≤ N ≤ 1000
  • 0 ≤ L[i] ≤ 1018
  • 0 ≤ AB ≤ 1018
  • 2 ≤ C ≤ 1018
1 1 1
2 3 1000
1 2 3 4
0 1 1000
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

Best Submission

Similar Problems


This Problem was Asked in

Initializing Code Editor...
View All Notifications