Рабочее место участника

Первым компьютером можно считать аналитическую машину, спроектированную Чарльзом Бэббиджем в середине 19 века. Машина Бэббиджа состояла из арифметического устройства, которое могло выполнять четыре арифметические операции, сравнение чисел и вычисление квадратного корня, и памяти для 1000 40-разрядных десятичных чисел. Программа и вспомогательные данные хранились на перфокартах, а для вывода использовался принтер.

Вам нужно создать программу для этой машины. Программа должна находить `K`-й элемент в возрастающей последовательности, образованной слиянием двух других возрастающих последовательностей чисел. Первая последовательность содержит `N` чисел, а вторая — `M` чисел. Среди этих `N+M` чисел нет одинаковых. Программа должна находить `K`-й элемент за минимальное количество сравнений в худшем случае. Хотя длина программы не важна, но она не должна превышать `10^5` строк. В программе может использоваться два вида команд (каждая команда программы размещается на отдельной перфокарте):

C `i\ j\ l\ g`

Сравнить `i`-й элемент первой последовательности (`1\ ≤\ i\ ≤\ N`) и `j`-й элемент второй последовательности (`1\ ≤\ j\ ≤\ M`). Если `i`-й элемент меньше, чем `j`-й, то перейти на команду с номером `l`, иначе перейти на команду с номером `g`.

R `p\ i`

Вывести `i`-й элемент из `p`-й последовательности (он должен являться `K`-м элементом в последовательности, образовавшейся при слиянии) и завершить выполнение программы.

Вы должны написать программу, генерирующую программу для аналитической машины для заданных `N`, `M` и `K`.

Первая строка ввода содержит три целых числа `N`, `M` и `K` (`1\ ≤\ N,\ M\ ≤\ 10000`, `1\ ≤\ K\ ≤\ N\ +\ M`), разделенных пробелом — длины последовательностей и номер элемента.

Вывести в первой строке одно целое число `P` – длину сгенерированной программы. Далее должно следовать `P` строк с командами в указанном выше формате.

20 11 31

3
C 20 11 2 3
R 2 11
R 1 20