Задача Y. Предпоследнее дело Холмса ≡

Условие

С тяжелым сердцем приступаю я к последним строкам этих воспоминаний, повествующих о необыкновенных талантах моего друга Шерлока Холмса. Его трагическая гибель в Рейхенбахском водопаде до сих пор не дает мне покоя. По совету миссис Хадсон я постарался перенести события тех дней на бумагу. К сожалению, при публикации в "Стрэнде", редакторы не включили один эпизод из моей рукописи, посчитав его незначительным. Но на мой взгляд, Холмс в этом расследовании проявил недюжинные аналитические способности, заслуживающие того, чтобы с ними познакомилась широкая публика.

Эта история произошла в поезде, когда мы уже мчались по континенту, радуясь, что ускользнули от Мориарти. В Европе пассажирское сообщение совершенно не похоже на наше. Начать с того, что в вагоне было ровно n одноместных купе. Мы с Шерлоком заняли два соседних и всю ночь проспали, не просыпаясь. Утром меня разбудил шум в коридоре. Когда я вышел, мой друг вкратце рассказал, что случилось.

 — Убийство, Ватсон! Кто-то зарезал беднягу из последнего купе, пока тот спал. Тело обнаружил проводник. Я уже осмотрел место преступления — никаких следов.

 — Возможно, вам поможет моя информация, а может и нет...  — в наш разговор с континентальной бесцеремонностью вмешался проводник.  — Пассажиры об этом не знают, но когда открывается дверь любого купе, у меня на пульте загорается лампочка, ну, знаете, некоторым пожилым джентльменам иногда нужна помощь, чтобы добраться до уборной. Так вот, ночью, борясь со сном, я записывал на листочке, в каком порядке зажигались лампочки. Эх, если бы я еще помнил точное время, когда они включались!

Мы склонились над листом с числами. Я тоскливо созерцал аккуратную запись, сделанную синими чернилами: 1 2 8 1 8 2, не в силах понять, как её можно использовать в расследовании. Внезапно Холмс радостно потер руки.

 — Смотрите, друг мой! В вагоне всего восемь купе. Мы с вами ехали в третьем и четвертом и ночью не выходили. Постараемся представить, как развивались события. Вот открывается дверь первого купе и пассажир №1 выходит в коридор. Далее открывается дверь второго купе и пассажир №2 тоже выходит в коридор. Наконец, открывается дверь последнего купе, убийца заходит в купе жертвы и закрывает за собой дверь. Это либо №1, либо №2 — в коридоре сейчас только они. Но далее опять открывается дверь первого купе — это пассажир №1 возвращается назад. Потом опять открывается дверь последнего купе и убийца возвращается к себе. Нужно навестить второе купе, у меня есть вопросы к его обитателю!

 — А может быть, они действовали сообща?

 — Все возможно, милый доктор! Но пока наш главный подозреваемый — пассажир №2 и он может быть опасен! У Вас пистолет с собой?

Формат входных данных

Первая строка входного файла содержит два натуральных числа, записанных через пробел: n — количество купе в вагоне и m — количество чисел на листочке проводника. Во второй строке через пробел расположено m натуральных чисел k_i. Гарантируется, что каждое число присутствует во второй строке четное число раз (пассажир мог выходить в коридор и возвращаться неоднократно). Гарантируется, что число n присутствует во второй строке ровно два раза.

Формат выходных данных

Выведите через пробел в порядке возрастания все номера купе, пассажиры которых по логике Холмса являются главными подозреваемыми. Гарантируется, что хотя бы один пассажир был в коридоре в момент первого открытия двери последнего купе. Гарантируется, что хотя бы один пассажир вернулся к себе после второго открытия двери последнего купе.

Ограничения

4 ≤ n, m ≤ 10⁵

1 ≤ k_i ≤ n

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

Пояснение к примерам

Первый пример разобран в тексте задачи.

Во втором примере пассажир №3 не находился в коридоре в момент проникновения в последнее купе, а пассажиры №4 и №5 вышли из своих купе уже после этого. Основные подозреваемые — пассажиры №1 и №2, любой из них мог совершить преступление.

Примеры тестов

8 6
1 2 8 1 8 2

2

8 16
1 2 3 2 3 2 8 4 5 8 3 1 2 3 5 4

1 2