Consider a sequence of N different numbers. The operation "MOVE X Y" moves all the numbers in front of X (including X) and then inserts them in front of Y without changing order.
Given an initial sequence and a target sequence, generate a series of operations that can convert the initial sequence into the target sequence. Moreover, after each move, print the current position of the number 1. For example, if the initial sequence is 1 2 3 4 5, and the target sequence is 1 4 3 2 5, a possible series of operations could be
MOVE 2 4
2
MOVE 2 5
3
MOVE 3 2
1
(The solution is not unique. The answer is considered correct as long as the operations can generate the target sequence. But, in each input, total moves will not exceed 10001.)
There are several inputs. We simplified this problem. First, there is a positive integer N which determines how many numbers in the target sequence and the initial sequence is from 1 to N. Next, there are N integers for the target sequence. In the target sequence, each integer is unique and is between 1 and N. At the end of file, N is zero.
test case 1: N <= 10
test case 2: N <= 100
test case 3: N <= 1000
test case 4: N <= 10000
For each output, first, please print the input target sequence in one line and each number is separated by one space. Second, print how many moves in your total operation in one line without spaces. If it is impossible moving to the target, please print -1. Then, for each move, print "MOVE X Y" mentioned in problem description in one line and after "MOVE" there is only one space and between two numbers is only one space, too. Finally, print the position of 1 in each move in one line without spaces.