Ants

Interview

Time limit1sMemory limit128 MB

Summary

Simulate two colliding groups of ants swapping adjacent opposite-direction ants each second and output the arrangement after T seconds.

Level: Medium4 of 10
Topics: Simulation, Array
Solved: No attempts yet

Problem

Two groups of ants meet on a narrow path while moving in opposite directions.

The first group moves from left to right, and the second group moves from right to left. At the moment they meet, the order on the path is the reversed first group followed by the second group.

After each second, an ant swaps places with the ant directly in front of it if that ant is moving in the opposite direction. All jumps during the same second happen simultaneously.

For example, if the first group is ABC and the second group is DEF, the initial order is CBADEF. After 1 second, A and D swap, producing CBDAEF; after 2 seconds, the order becomes CDBEAF.

Find the order of the ants after T seconds.

Input

The first line contains N1, the number of ants in the first group, and N2, the number of ants in the second group.

The next two lines contain the order of the ants in the first and second groups. Each ant is represented by one uppercase English letter, and no letter appears more than once across both groups.

The last line contains the integer T. (0 <= T <= 50)

Output

Print the order of the ants after T seconds.

Examples3

Example 1
Input
```
3 3
ABC
DEF
0
```
Expected output
```
CBADEF
```
Example 2
Input
```
3 3
ABC
DEF
2
```
Expected output
```
CDBEAF
```
Example 3
Input
```
3 4
JLA
CRUO
3
```
Expected output
```
CARLUJO
```