{"raw_statement":[{"iden":"statement","content":"Eugene is inventing a new type of musical piece which has a few interesting properties.\n\nA valid song of Type $N$ has the following properties:\n\nHere are some examples of valid and invalid songs:\n\nEugene 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.\n\nFormally, 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 \" and \"y in Y \" and \"y >= x}$.\n\nFor example, for $N = 3$, $S = A A B$, and $S = A B A$, then $A A B A B B B A$ makes Eugene happy (because $A A B$ appears at position 1 and $A B A$ appears at position 2, so the time between their performances is only 1), but $A A B B B A B A$ makes Eugene sad (because $A A B$ appears at position 1, but $A B A$ appears at position 6, so the time between their performances is 5, which is not minimal)\n\nEugene 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$.\n\nThe first line contains an integer $N$ ($2 <= N <= 20$), the type of the song.\n\nThe second line contains the string $S$, the first special substring that Eugene wants to see. \n\nThe third line contains the string $T$, the second special substring that Eugene wants to see.\n\nIt is guaranteed that $| S | = | T | = N$. \n\nOutput 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).\n\n"},{"iden":"input","content":"The first line contains an integer $N$ ($2 <= N <= 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$. "},{"iden":"output","content":"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)."},{"iden":"examples","content":"Input3AABABAOutputAABABBBAInput3ABAAABOutputABAAABBB"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ N \\in \\mathbb{Z} $ with $ 2 \\leq N \\leq 20 $.  \nLet $ S, T \\in \\Sigma^N $ be two fixed strings over an alphabet $ \\Sigma $ (assumed to be binary or finite, context-dependent).  \n\nLet $ X \\subseteq \\mathbb{Z}_{\\geq 1} $ be the set of starting indices of occurrences of $ S $ in a song $ W \\in \\Sigma^* $.  \nLet $ Y \\subseteq \\mathbb{Z}_{\\geq 1} $ be the set of starting indices of occurrences of $ T $ in $ W $.  \n\n**Constraints**  \n1. The song $ W $ must be a finite string over $ \\Sigma $ such that it contains at least one occurrence of $ S $ and at least one occurrence of $ T $.  \n2. For any $ x \\in X $, $ y \\in Y $, we require $ y \\geq x $ to compute the delay $ y - x $.  \n\n**Objective**  \nMinimize $ \\min \\{ y - x \\mid x \\in X, y \\in Y, y \\geq x \\} $ over all possible songs $ W $ of Type $ N $.  \nOutput any such $ W $ achieving the minimal delay. If no such $ W $ exists, output \"SAD\".","simple_statement":"Given two strings S and T of length N, find the shortest possible string that contains both S and T as substrings, such that the first occurrence of T starts as early as possible after the first occurrence of S. Output any such string, or \"SAD\" if impossible.","has_page_source":false}