## COCI '06 Contest 2 #3 Kolone

View as PDF

Points: 7
Time limit: 0.6s
Memory limit: 32M

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

When moving, ants form rows so that each ant except the first is behind another ant. It is not widely known what happens when two rows of ants moving in opposite directions run into each other in a passage too narrow for both rows to pass through. One theory says that, in that situation, ants will jump over each other.

From the moment the rows meet, each second every ant jumps over (or gets jumped over, as they agree upon) the ant in front of himself so that the two ants swap places, but only if the other ant is moving in the opposite direction. Find the order of the ants after seconds.

#### Input Specification

The first line contains two integers and , the numbers of ants in the first and second rows, respectively.

The next two rows contain the orders of ants in the first and second row (first to last). Each ant is uniquely determined by an uppercase letter of the English alphabet (this letter is unique between both rows).

The last line of input contains the integer .

#### Output Specification

Output the order of the ants after seconds on a single line. Our viewpoint is such that the first row of ants comes from our left side and the other one from our right side.

#### Sample Input 1

3 3
ABC
DEF
0

#### Sample Output 1

CBADEF

#### Sample Input 2

3 3
ABC
DEF
2

#### Sample Output 1

CDBEAF

#### Sample Input 2

3 4
JLA
CRUO
3

#### Sample Output 2

CARLUJO