406233: GYM102319 C Cyclic Song
Description
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$$$.
InputThe 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$$$.
OutputOutput 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).
ExamplesInput3Output
AAB
ABA
AABABBBAInput
3Output
ABA
AAB
ABAAABBB