Расшифровка ДНК

Это интерактивная задача.

При проведении раскопок на территории Республики Татарстан были обнаружены останки неизвестного древнего животного, обитавшего в окрестностях современной Казани миллионы лет назад. Как и у всех живых организмов, молекула его ДНК представляет собой последовательность из n нуклеотидов, однако число встречающихся в ней различных нуклеотидов может отличаться от современных организмов.

Для изучения находки был создан специальный прибор, который может просканировать последовательный участок нуклеотидов в ДНК и вычислить, сколько различных видов нуклеотидов содержится на нём. К сожалению, молекула ДНК может выдержать не более q операций сканирования, после чего разрушается.

Исследователи хотят с помощью этого прибора найти k — количество различных нуклеотидов в ДНК, и определить позиции, в которых в ДНК находятся одинаковые нуклеотиды. Ученые хотят закодировать последовательность нуклеотидов в молекуле последовательностью целых положительных чисел a1, a2, . . . , an (1 ⩽ ai ⩽ k), таких что одинаковые числа кодируют одинаковые нуклеотиды, а различные числа — различные нуклеотиды.

Требуется написать программу, которая, взаимодействуя с программой жюри, определит количество различных нуклеотидов в последовательности, а также числовую последовательность, кодирующую последовательность нуклеотидов в молекуле ДНК.

В первом примере n = 2, за один запрос можно определить, равны ли первый и второй нуклеотид друг другу.

В втором примере n = 3, результат первого запроса показывает, что первые два нуклеотида одинаковые, результат второго запроса позволяет сделать вывод о том, что третий нуклеотид от них отличается. В этом случае допустимы два варианта ответа: 1 1 2 и 2 2 1.

В точности соблюдайте формат выходных данных. После каждого вывода обязательно выводите один перевод строки и сбрасывайте буфер вывода — для этого используйте flush(output) на языке Паскаль или Delphi, fflush(stdout) или cout.flush() в C/C++, sys.stdout.flush() на языке Python, System.out.flush() на языке Java.