Mergesort is a quick sorting algorithm invented by John Von Neumann in 1945. In the heart of the algorithm lies a procedure that combines two already sorted sequences into a new sorted sequence. In this task you need to write a program which does a similar thing.
Let and be sequences of integers sorted in ascending order, the sequence is called small sequence and large sequence. As it can be derived from these names, the sequence contains less or equal number of elements than sequence , and often the sequence is a lot shorter. The sequence is obtained by combining sequences and in such a way that first we sequentially take all the numbers from sequence and then, after them, sequentially take all the numbers from sequence . We use the notation to denote the element of sequence where is an integer in the interval from to total number of elements in sequence .
In the beginning, your program knows only the lengths of sequences and , but not the sequence elements themselves. The program must sort the sequence in ascending order using only the following interactive commands:
cmp X Y
is a command which compares and returns if is less than , if is greater than and if they are equal.reverse X Y
is a command which reverses a subsequence of sequence between the and element (inclusive). For example, if sequence is equal to then thereverse 2 4
command will alter it so it becomes .end
is a command that denotes the end of interaction and your program should call it when the sequence is sorted in ascending order.
The cost of command reverse X Y
is equal to the length of the reversed subsequence (in other
words, ), whereas the rest of the commands do not have a cost. Write a program
that will sort the sequence obtained by combining sorted sequences and as described above
using at most commands in total (including the command end
) and additionally, so
that the total cost of all reverse
commands is at most ).
Interaction
Before interacting, you must read two integers from the standard input, and - lengths of sequences and .
Afterwards, your program can give commands by outputting using standard output. Each
command must be output in its own line and has to be in the exact form of one of the three
commands described in the task. Regarding commands cmp
and reverse
, and have to
be integers less than or equal to , and regarding the command reverse, it additionally
must hold that is less than or equal to .
After command cmp
, your program must input one integer using the standard input - the
command result. After other commands, your program must not input anything. After outputting
the command end
, your program needs to flush the standard output and finish executing.
Please note that you need to flush stdout after each command, or interaction may halt. In C++, this can be done with fflush(stdout)
or cout << flush
(depending on whether you use printf
or cout
). In Java, this can be done with System.out.flush()
. In Python, you can use sys.stdout.flush()
.
Constraints
Subtask | Points | Constraints |
---|---|---|
1 | 30 | |
2 | 30 | |
3 | 40 | No additional constraints. |
Sample Interaction
>>>
denotes your output. Do not print this out.
2 3
>>> cmp 1 4
-1
>>> reverse 2 5
>>> cmp 2 3
0
>>> reverse 4 5
>>> reverse 2 5
>>> end
Sample Explanation
Output | Input | Sequence | Total Cost |
---|---|---|---|
cmp 2 3 | |||
reverse 2 5 | |||
cmp 2 3 | |||
reverse 4 5 | |||
reverse 2 5 | |||
end |
Comments