Задача №111511. Билеты на Сапсан

Летнее дз

Саша и Лиза — две самые обычные девочки, которые живут в Москве и очень любят Санкт-Петербург. На каникулы они запланировали обширную экскурсионную программу в северной столице, осталось только купить билеты. Девочки знают, что быстрее всего добраться до Санкт-Петербурга можно на скоростном поезде «Сапсан». В каждом вагоне есть N рядов, в каждом из которых по 4 места, которые нумеруются так:

1 2 4 3
5 6 8 7
9 10 12 11
13 14 16 15
17 18 20 19
21 22 24 23
.

.

.
.

.

.
.

.

.
.

.

.

Саша и Лиза выбрали вагон, в котором они планируют ехать. Оказалось, что в этом вагоне уже продано M билетов и известно, какие места уже заняты. Девочки решили купить билеты таким образом:

  • если есть два места рядом, то они покупают их (например, 1 и 2 или 3 и 4)
  • если двух мест рядом нет, то они пытаются купить места рядом через проход (например, 2 и 4)
  • если нет и таких мест, то они покупают любые два свободных места.
  • Помогите Саше и Лизе определить, какие места им стоит купить. Гарантируется, что в выбранном вагоне есть как минимум два свободных места.

Входные данные

В первой строке входных данных содержатся числа N — количество рядов в вагоне (1 ≤ N ≤ 105) и M — количество проданных билетов (1 ≤ M ≤ 4N - 2). В следующей строке записаны M различных чисел — номера мест, на которые билеты уже проданы.

Выходные данные

Выведите два числа — номера мест, билеты на которые стоит купить девочкам. Если возможны несколько вариантов ответа, выведите любой из них.

Примеры
Входные данные
2 3
3 7 8
Выходные данные
5 6
Входные данные
2 5
1 4 5 2 7
Выходные данные
6 8
Входные данные
2 5
2 7 4 5 6
Выходные данные
1 3
Сдать: для сдачи задач необходимо войти в систему