You are selling electric telephones, and manufactures your wares on a conveyor belt, which has items on it.
When your conveyor belt shifts right once, the rightmost item is removed and re-added to the left. When your conveyor belt shifts left once, the leftmost item is removed and is re-added to the right.
After watching your conveyor belt rotate for hours in this manner, you wants to know the minimum number of shifts it will take for his conveyor belt to start from a given position and end at a different position.
Input Specification
The first line will consist of one integer,
, representing the length of the conveyor belt.
The second line will have a string of length , consisting of only lower case letters, representing the starting position of the conveyor belt.
The third line will have a string of length , consisting of only lower case letters, representing the ending position of the conveyor belt.
Output Specification
Your program should output the minimum number of shifts that it will take to transform the starting position of the conveyor belt to match the end position.
If it is possible for the conveyor belt to be shifted to match the end position, the output of the program should be two characters. The first should be the direction that the conveyor belt must move in (L representing left, and R representing right - if it takes the same number of shifts in either direction to reach the end position output L), and the second should be the number of shifts that must be performed.
If it is impossible to shift the conveyor belt to match the end position, output -1.
Sample Input 1
6
abcdef
cdefab
Sample Output 1
L2
Explanation of Sample Output 1
If the conveyor belt is rotated two times to the left from its starting position, it will match the end position.
Comments