C. Cyclic Song
time limit per test
5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Eugene is inventing a new type of musical piece which has a few interesting properties.

A valid song of Type $$$N$$$ has the following properties:

  • The song only contains the notes $$$A$$$ and $$$B$$$, all of equal length.
  • The song will be repeated indefinitely. For example, if the song is $$$AAB$$$, then a musician will play $$$AABAABAABAABAAB...$$$ until Eugene falls asleep, which is once in a blue moon. This constitutes a performance.
  • If we consider all the substrings of length $$$N$$$ of the performance, the performance will contain all $$$2^N$$$ possible strings of length $$$N$$$.
  • The representation of the song is as short as possible.

Here are some examples of valid and invalid songs:

  • $$$AB$$$ is a valid song of Type 1. It contains all substrings of length 1 ($$$A$$$ and $$$B$$$) and it is as short as possible.
  • $$$ABAB$$$ is not a valid song of Type 1, because a shorter representation ($$$AB$$$) exists.
  • $$$ABA$$$ is not a valid song of Type 2, because it is missing the substring $$$BB$$$.

Eugene would like you to create a special song of type $$$N$$$. He will specify two substrings $$$S$$$ and $$$T$$$ of length $$$N$$$. During a performance, the time between a performance of $$$S$$$ and the next performance of $$$T$$$ should be minimized. The performance of $$$S$$$ and $$$T$$$ can possibly overlap.

Formally, let $$$X$$$ be the set of indices at which a substring equal to $$$S$$$ begins, and let $$$Y$$$ be the set of indices at which a substring equal to $$$T$$$ begins. Then we want to minimize $$$\min\{y-x:x\in X\text{ and }y\in Y\text{ and }y\ge x\}$$$.

For example, for $$$N = 3$$$, $$$S=AAB$$$, and $$$S=ABA$$$, then $$$AABABBBA$$$ makes Eugene happy (because $$$AAB$$$ appears at position 1 and $$$ABA$$$ appears at position 2, so the time between their performances is only 1), but $$$AABBBABA$$$ makes Eugene sad (because $$$AAB$$$ appears at position 1, but $$$ABA$$$ appears at position 6, so the time between their performances is 5, which is not minimal)

Eugene will be very happy if you can help him write a special song of Type $$$N$$$ which minimizes the time from a performance of $$$S$$$ to a performance of $$$T$$$.

Input

The first line contains an integer $$$N$$$ ($$$2 \leq N \leq 20$$$), the type of the song.

The second line contains the string $$$S$$$, the first special substring that Eugene wants to see.

The third line contains the string $$$T$$$, the second special substring that Eugene wants to see.

It is guaranteed that $$$|S|=|T|=N$$$.

Output

Output a single line, a valid song of Type $$$N$$$ that makes Eugene happy. If there are multiple such songs that make Eugene happy, output any of them. If Eugene cannot be happy, then output "SAD" (without quotation marks).

Examples
Input
3
AAB
ABA
Output
AABABBBA
Input
3
ABA
AAB
Output
ABAAABBB