Triangular Magic Cube Rotation

The triangular magic cube is formed by arranging 16 letters A–P into a triangle as follows:

   A
  BCD
 EFGHI
JKLMNOP

The cube can be manipulated with a set of rotation operations. There are three directions indicated by arrows: upper‐left (denoted by U), down‐left (denoted by D) and right (denoted by R). In each rotation operation you choose a line (or column) in that direction that contains exactly 1, 3, 5, or 7 letters. For example, the legal operations include U1, D7, R3, etc. A rotation operation moves all letters in the chosen line one step in the designated direction using cyclic shift (i.e. the last letter moves to the first position).

The robot accepts an operation sequence (a sequence of commands, each of the form Xn where X is one of {U, D, R} and n is one of {1,3,5,7}). It then repeats the given sequence exactly a^b times. Given the initial state, your task is to determine the final state of the cube after all rotations are executed.

Note on geometry: To simplify the simulation the positions of the letters are numbered 0 to 15 as follows:

Row1: index 0
Row2: indices 1,2,3
Row3: indices 4,5,6,7,8
Row4: indices 9,10,11,12,13,14,15

The rotations are defined by the following fixed cycles (the indices in the cube that are affected by a rotation). For each rotation command, the letters in the specified cycle are cyclically shifted by one step. The cycles for each legal move are defined as:

• Right (R) moves:
  • R1: [0]
  • R3: [1, 2, 3]
  • R5: [4, 5, 6, 7, 8]
  • R7: [9, 10, 11, 12, 13, 14, 15]
• Upper‐left (U) moves:
  • U1: [0]
  • U3: [3, 7, 10]
  • U5: [6, 1, 12, 5, 13]    *(This cycle is chosen so that applying U5 twice yields the sample transformation.)*
  • U7: [8, 4, 14, 11, 2, 15, 9]
• Down‐left (D) moves:
  • D1: [15]
  • D3: [13, 8, 3]
  • D5: [7, 2, 10, 12, 14]
  • D7: [5, 11, 15, 8, 2, 3, 7]

To simulate the robot, first determine the permutation that one full operation sequence produces. Then, since the robot repeats the sequence a^b times, compute the permutation raised to the power a^b. Since a^b may be huge, perform permutation exponentiation on each cycle by computing the shift modulo the cycle length (using fast modular exponentiation).

Finally, output the final state in the triangular format (each row on a new line). For example, if the final state array (indices 0 to 15) is [A, X, Y, Z, ..., P] then the output should be:

A
XYZ
ABCDE
ABCDEFG

inputFormat

The input consists of two lines. The first line contains a nonempty string representing the operation sequence. Each operation is given in the form Xn (without spaces) where X is one of U, D, or R and n is one of 1, 3, 5, or 7.

The second line contains two integers a and b (1 ≤ a ≤ 10⁹, 0 ≤ b ≤ 10⁹), indicating that the sequence is repeated a^b times.

outputFormat

Output the final state of the magic cube in four lines. The first line contains the single letter in row1; the second line contains three letters; the third line contains five letters; and the fourth line contains seven letters. Do not output extra spaces.

sample

R3
1 1

A
DBC
EFGHI
JKLMNOP

</p>