Descriere

Context

Un mod de a produce noi soluții candidat în cadrul unui algoritm genetic este prin încrucișare (crossover). La nivelul cromozomilor codificați ca șiruri binare, încrucișarea constă în interschimbarea unui segment de biți din primul cromozom cu segmentul corespunzător din al doilea. Noii cromozomi obținuți vor avea elemente în comun cu ambii "părinți", deci ne așteptăm ca și soluțiile codificate de aceștia să se asemene într-un fel cu soluțiile asociate cromozomilor inițiali.

Cerință

Fiind dați doi cromozomi, fiecare având o lungime de \(l\) biți, realizați încrucișarea cu un singur punct de rupere. Cu alte cuvinte, dacă cei doi cromozomi sunt \[ \begin{align*} C_1 &= x_0 \; x_1 \; \dots \; x_{i-1} \; x_{i} \; x_{i+1} \; \dots \; x_{l-2} \; y_{l-1} \\ C_2 &= y_0 \; y_1 \; \dots \; y_{i-1} \; y_{i} \; y_{i+1} \; \dots \; y_{l-2} \; y_{l-1} \end{align*} \] cromozomii rezultați în urma încrucișării, pentru punctul de rupere \(i\), vor fi: \[ \begin{align*} C_1' &= x_0 \; x_1 \; \dots \; x_{i-1} \; y_{i} \; y_{i+1} \; \dots \; y_{l-2} \; y_{l-1} \\ C_2' &= y_0 \; y_1 \; \dots \; y_{i-1} \; x_{i} \; x_{i+1} \; \dots \; x_{l-2} \; x_{l-1} \end{align*} \]

Date de intrare

Se citește de la tastatură numărul natural \(l\), reprezentând lungimea cromozomilor cu care lucrăm. Pe următoarele două linii se vor citi două șiruri binare \(x_0\) și \(x_1\) de lungime \(l\), reprezentând cei doi cromozomi pe care vrem să-i încrucișăm. Pe ultima linie se află un număr întreg \(0 \leq i \leq l - 1\), de la care se va face încrucișarea cromozomilor.

Date de ieșire

Afișați cei doi cromozomi obținuți după recombinare, codificați ca șiruri binare, fiecare pe câte un rând separat.

Restricții și precizări

• \(1 \leq l \leq 100\)
• \(0 \leq i \leq l - 1\)

Exemplul 1

Input

5
10101
11000
2

Output

10000
11101

Explicație

Punctul de rupere este \(i = 2\), deci interschimbăm segmentul \(101\) din primul cromozom cu segmentul \(000\) din al doilea cromozom.

Exemplul 2

Input

4
0100
0111
3

Output

0101
0110

Explicație

Deoarece \(i = 3 = l - 1\), trebuie să interschimbăm doar ultimul bit al celor doi cromozomi.

Exemplul 3

Input

10
1101010000
1101101101
0

Output

1101101101
1101010000

Explicație

Deoarece \(i = 0\), trebuie să interschimbăm complet cei doi cromozomi între ei. O astfel de interschimbare nu modifică în vreun fel populația noastră de cromozomi, dar nu este o problemă dacă (algeând aleator punctul de rupere) întâmpinăm și această situație.