Задача: Билеты на Сапсан
Саша и Лиза — две самые обычные девочки, которые живут в Москве и очень любят Санкт-Петербург. На каникулы они запланировали обширную экскурсионную программу в северной столице, осталось только купить билеты. Девочки знают, что быстрее всего добраться до Санкт-Петербурга можно на скоростном поезде «Сапсан». В каждом вагоне есть N рядов, в каждом из которых по 4 места, которые нумеруются так:
Саша и Лиза выбрали вагон, в котором они планируют ехать. Оказалось, что в этом вагоне уже продано M билетов и известно, какие места уже заняты. Девочки решили купить билеты таким образом:
- если есть два места рядом, то они покупают их (например, 1 и 2 или 3 и 4)
- если двух мест рядом нет, то они пытаются купить места рядом через проход (например, 2 и 4)
- если нет и таких мест, то они покупают любые два свободных места.
Помогите Саше и Лизе определить, какие места им стоит купить. Гарантируется, что в выбранном вагоне есть как минимум два свободных места.
Входные данные
В первой строке входных данных содержатся числа N — количество рядов в вагоне (1 ≤ N ≤ 10
5) и M — количество проданных билетов (1 ≤ M ≤ 4N - 2). В следующей строке записаны M различных чисел — номера мест, на которые билеты уже проданы.
Выходные данные
Выведите два числа — номера мест, билеты на которые стоит купить девочкам. Если возможны несколько вариантов ответа, выведите любой из них.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
2 3
3 7 8 |
5 6 |
| 2 |
2 5
1 4 5 2 7 |
6 8 |
| 3 |
2 5
2 7 4 5 6 |
1 3 |
Ваш ответ: