Лимит времени 2000/4000/4000/4000 мс. Лимит памяти 65000/65000/65000/65000 Кб.
Patriarchal game
Пафнутий и Полина стояли у входа в «ручеёк», образованный парами студентка-студент. Им предстояло начать игру, которую ведущий объявил «тим-билдингом эпохи Петра».
Правила знакомы с детства: водящие «протекают» по ручейку под сцепленными и поднятыми руками пар-берегов. Каждый из них должен прихватить с собой «камушек» противоположного пола и образовать с ним новую пару в конце ручья. А оставшиеся без пары шли к началу и становились новыми водящими.
А профессор Пупырчиков, собиравший материал для исследования «Хороводные игры как индикатор лидерских качеств», с помощью цифрового фотоаппарата и хитроумной программы протоколировал ход игры. Участники обозначались кодами, состоящими из буквы F (девушки) или M (юноши) и числа, не превышающего 1000. Пафнутий и Полина имели коды F0 и M0, остальным участникам коды были присвоены в соответствии с их начальной расстановкой, нумерация – от начала ручья. Файл, формируемый программой, состоял из кодов входящих в ручеёк участников. Гарантируется, что в последней зафиксированной паре ни Пафнутия, ни Полины не было.
Разработайте программу, которая по записям Пупырчикова определяет, с кем оказались Пафнутий и Полина в конце игры.
Входные данные. В первой строке два натуральных числа, не превышающих 1000: P - количество пар в ручейке (не считая Пафнутия и Полины), - и N≥4, количество кодов в протоколе Пупырчикова. Далее следуют N строк, в каждой из которых код очередного входящего в ручей участника. Гарантируется, что последовательность участников на входе соответствует последовательности появления их бывших партнёров на выходе, т.е. первые два значения – это M0 и F0, далее M и F чередуются.
Выходные данные. Коды партнёрши Пафнутия и партнёра Полины на момент окончания протокола в одной строке через пробел.
Пример. Предположим, в ручейке, помимо Пафнутия и Полины, было 4 пары. "Ручеёк" выглядел так:
M1 M2 M3 M4
F1 F2 F3 F4.
Пафнутий выбрал F3, ручеёк стал таким:
M1 M2 M4 M0
F1 F2 F4 F3,
а оставшийся без пары M3 пошёл к началу ручейка. Тем временем в ручеёк вошла F0 (Полина) и выбрала M1, встала с ним в конце ручейка, а F1 направилась к началу ручейка... можно мы на этом остановимся? Входные данные в этом случае выглядели бы так:
4 4
M0
F0
M3
F1
А выходные должны быть такие:
F3 M1
Для отправки решений необходимо выполнить вход.
|