Many organizers of math contests notice that their students are not really good in solving so-called two-step problems, which are the problems that can be solved by solving two weakly related sub-problems consecutively. In fact, it is easier to them to solve one-step problem which is much more complex than both sub-problems of the two-step problem. Now, you have got a book with the annotation on cover which says that this book holds an explanation of the mystery of that paradox. Unfortunately, the book is locked with a special lock, but there is a detailed instruction on how to open it.

The lock is made of two tapes with capital Latin letters printed on them. All letters on both tapes have identical width. The second tape is placed directly below the first, and they are aligned by left border. To have better understanding of this, you can think of these tapes as two strings of letters printed with monospaced font, one under another. The length of the second tape (string) is strictly less than the length of the first one. Using the lock mechanism, you can shift any tape left or right by one letter. This shift is cyclic, that is, after a shift to the left, string "ABRA" becomes "BRAA". To open the lock, you must shift the second tape so that the lexicographic order of resulting string will be the least possible. After that you must shift the first tape in such way that the beginning of the first string will match the whole second string. For example, let us assume that the first tape contains string "KADAABRA" and the second tape contains "ABRA". On the first step we should shift the second string by one letter to the right, so we get "AABR" (the lexicographically smallest shift of the string "ABRA"). After that we shift the first string by three letters to the left, resulting in string "AABRAKAD" which begins with "AABR". Additionally, the lock mechanism accepts combinations where any one letter in the second string differs from the corresponding letter in the first string. Thus, if the first string is "KADABRA" and the second is "AABR", it is acceptable to shift first string to get "DABRAKA", which begins with "DABR" that differs from "AABR" by one letter, and the lock will be opened.

Given the strings on the two tapes, find a way to open the lock. It is guaranteed that the solution exists.

The first line of input contains two integers N and M which indicate the number of letters on the first and second tapes, respectively (). The second line consists of N capital Latin letters — the string printed on the first tape. The third line consists of M capital Latin letters — the string printed on the second tape.

Output two lines. The first line should contain the resulting string on the second tape. The second line should contain the resulting string on the first tape. If several solutions are possible, output a solution which shifts the first tape the minimal number of times. If more than one solution still exists, output a solution where the first tape is being shifted to the left.

sample input	sample output
7 4 KADABRA ABRA	AABR DABRAKA