A festival's raffle booth keeps its ticket stubs in a numbered array. Between draws, the booth operator issues one of two commands: reset the stubs to their original printed order, or run the shuffling machine once. The machine performs the classic back-to-front swap procedure: for i going from the last index down to index 1, it swaps whichever stub currently sits at position i with whichever stub currently sits at some position r (0 <= r <= i). Because true randomness can't be replayed for automated grading, every shuffle command in this problem supplies the exact sequence of r values the machine must use, one for each step from i = n-1 down to i = 1, in that order. After every command - whether a reset or a shuffle - print the resulting array of stub numbers on its own line. A reset always restores the array to its very first state (before any command ran), no matter how many shuffles happened in between.

Input format

Line 1: an integer n - the number of tickets. Line 2: n integers - the initial ticket numbers, in order. Line 3: an integer q - the number of commands. Each of the next q lines holds one command, either:

• RESET
• SHUFFLE r_1 r_2 ... r_{n-1} - where r_k is the swap-partner index used at the step where i = n - k (so r_1 is used when i = n-1, r_2 when i = n-2, and so on down to r_{n-1} when i = 1), and 0 <= r_k <= n - k always holds. When n = 1 the SHUFFLE line has no numbers after the keyword.

Output format

q lines: after each command, the resulting array on its own line, values separated by single spaces.

Constraints

• 1 <= n <= 1000
• 1 <= q <= 1000
• -10^6 <= each initial ticket number <= 10^6
• Every SHUFFLE line's r values satisfy the bound given above.

3
1 2 3
2
SHUFFLE 0 0
RESET

2 3 1
1 2 3

1
5
1
SHUFFLE

5