У Алисы закончился очередной учебный год, и она составляет расписание на каникулы

У Алисы закончился очередной учебный год, и она составляет расписание на каникулы. Алиса планирует, что в ее каникулы состоится некоторое число событий, таких как посещение концертов, празднование дней рождений и так далее. Алиса называет ii-тый день каникул нескучным, если для него выполняется хотя бы одно из двух условий:

в ii-тый день состоится хотя бы одно событие;
хотя бы одно событие состоится в день с номером i−1i−1 и в день с номером i+1i+1.

Рассмотрим пример. Пусть в каникулах 10 дней и некоторые события произойдут в дни с номерами 2,3,5,9,102,3,5,9,10. Тогда нескучными будут все эти дни, а также день с номером 44, поскольку некоторые события произойдут в два соседних с ним дня.

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

Напишите программу, которая подберет дни для событий с открытой датой так, чтобы каникулы получились наиболее нескучными.
Формат входных данных

На вход в первой строке через пробел подается три целых числа nn, mm и kk — продолжительность каникул в днях, количество событий с открытой датой и количество событий с заданной датой соответственно; 1≤n≤1000001≤n≤100000; 1≤m≤1000001≤m≤100000; 0≤k≤1000000≤k≤100000.

Во второй строке через пробел записаны kk натуральных чисел d1,d2,⋯ ,dkd1​,d2​,⋯,dk​ — номера дней, в которые произойдут события с известной датой; 1≤di≤n1≤di​≤n. Числа могут повторяться и следовать в произвольном порядке. Если kk будет равно нулю, то вторая строка будет пустой.
Формат выходных данных

В первой строке выведите одно натуральное число ss— количество нескучных дней в каникулах. Во второй строке через пробел выведите mm натуральных чисел t1,⋯ ,tmt1​,⋯,tm​ — номера дней в которые Алиса должна запланировать события с открытой датой. Если допустимых ответов будет несколько, то можно вывести любой. Числа могут повторяться и следовать в произвольном порядке.
Методика проверки

Программа проверяется на 30 тестах.


Sample Input 1:

11 5 6
1 3 5 7 9 11

Sample Output 1:

11
1 1 1 1 1

__________________________
Sample Input 2:

11 2 0

Sample Output 2:

3
2 4

__________________________
Sample Input 3:

15 2 5
1 2 8 12 14

Sample Output 3:

11
4 6

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

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

В ответе к второму примеру нескучными будут дни с номерами 2,3,42,3,4. Улучшить ответ нельзя.

В ответе к третьему примеру нескучными будут 11 дней с номерами 1,2,3,4,5,6,7,8,12,13,141,2,3,4,5,6,7,8, 12,13,14. Улучшить этот ответ нельзя, хотя набор дней может быть другим, например, 4,104,10 или 6,106,10.

0