406233: GYM102319 C Cyclic Song

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$$$.

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 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).

3
AAB
ABA

AABABBBA

3
ABA
AAB

ABAAABBB