Problem Description

There is a triangular magic cube. Initially, the triangle is filled row by row with the 16 letters from $\tt{A}$ to $\tt{P}$. The magic cube can perform a "rotation" operation in one of the three directions indicated by the arrows in the figure below.

There are three valid "rotation" directions: upper left (red arrow), lower left (blue arrow), and straight right (green arrow), denoted as $\tt U$, $\tt D$, and $\tt R$ respectively.

Each "rotation" operation selects a row (or column) containing one, three, five, or seven letters, denoted as 1, 3, 5, 7. Combining different directions and rows (or columns) yields twelve valid "rotation" operations, such as U1, D7, R3.

The "rotation" operation shifts all letters in the selected row/column cyclically one position in the direction of the arrow, with the first letter becoming the second, the second becoming the third, and so on, with the last letter becoming the first. For example:

If the triangular magic cube is written in the form of a "letter triangle", the initial state is:

   A
  BCD
 EFGHI
JKLMNOP

If two U5 rotations are performed on the initial state, the result will be:

   A
  GCD
 EMNHI
JKLBFOP

Now, you have a magic cube rotation robot that can input a sequence of operations and then repeat this sequence $a^b$ times ($a$ raised to the power of $b$, i.e., $a$ multiplied by itself $b$ times). However, having the robot rotate the magic cube is too time-consuming. Can you predict the state of the magic cube after the robot's actions are completed, starting from the initial state?

Input Format

The first line of input is a string representing a sequence of operations.

The second line of input contains two integers $a$ and $b$, indicating that the robot will repeat the operation sequence $a^b$ times.

Output Format

Output 16 characters representing the state of the magic cube after the operation sequence is repeated, outputting all letters row by row, for example, the initial state outputs ABCDEFGHIJKLMNOP.

Sample Input and Output

Sample Input #1

U3R5D7
5 2

Sample Output #1

EJLDHACBFKGIMNOP

Sample Input #2

U3U5U7
105 3

Sample Output #2

ABCDEFGHIJKLMNOP

Sample Input #3

R3R5R7U3U5U7D3D5D7D7
2 128

Sample Output #3

KBPDECGHIJFLMNOA

Notes

For 50% of the test cases, $b=1$.

For 100% of the test cases, $1 \leq a, b \leq 10^3$. The number of "rotation" operations in the operation sequence does not exceed 100.

This problem originally had a maximum score of $20\text{pts}$.

见题面 Input 部分

见题面 Output 部分