Candy Factory

Time limit0.5sMemory limit1024 MB

Summary

Given two belts of candies, apply Q rotations, prefix swaps of length R, and gripper resizes, then print both belts' final contents.

Level: Medium7 of 10
Topics: Tree, Simulation, Implementation
Solved: No attempts yet

Problem

Anz really loves candy. So he invested all the money he had earned so far to build a candy factory.

In the packaging stage, the final step of the factory, candies of various kinds are handled with two conveyor belts and one gripper. Each conveyor belt has $N$ cells. The gripper picks up all candies from the first cell up to any chosen cell at once.

The possible operations are as follows. Initially, every cell of each conveyor belt holds one candy.

$S$ $S$ : Using the gripper, swap the candies between the two conveyor belts from the first cell up to the $R$ $R$ -th cell. $R$ $R$ is the current size of the gripper.
- In other words, swap the candy in cell 1 of belt 1 with the candy in cell 1 of belt 2, then swap the candies in cell 2, and so on, finally swapping the candies in cell $R$ .
$L$ $L$ $x$ $x$ : Move conveyor belt $x$ $x$ one cell to the left.
- Every candy except the one in the first cell moves from position $p$ to position $(p-1)$ . The candy in the first cell moves to position $N$ .
$R$ $R$ $x$ $x$ : Move conveyor belt $x$ $x$ one cell to the right.
- Every candy except the one in cell $N$ moves from position $p$ to position $(p+1)$ . The candy in cell $N$ moves to the first cell.
$I$ : Increase the gripper size by 1. The input never makes the gripper size greater than $N$ .
$D$ : Decrease the gripper size by 1. The input never makes the gripper size less than 1.

Input

The first line contains the size of the two conveyor belts $N$ , the initial gripper size $R$ , and the number of operations $Q$ .

The second line gives the candies on conveyor belt 1 from the leftmost cell to the rightmost cell, in order, with no spaces.

The third line gives the candies on conveyor belt 2 from the leftmost cell to the rightmost cell, in order, with no spaces.

Each candy is represented by an uppercase English letter.

The next $Q$ lines each give one operation to process.

Output

After all operations are processed, print the candies on conveyor belt 1 on the first line, in the same format as the input. Print the candies on conveyor belt 2 on the second line, in the same format.

Constraints

$1 \le N \le 500{,}000$
$1 \le R \le N$
$1 \le Q \le 500{,}000$
$1 \le x \le 2$

Examples1

Example 1

Input

5 2 5
ABCDE
FGHIJ
S
L 1
R 2
I
S

Expected output

JABEF
GCDHI