На этой социальной платформе есть $n$ пользователей. Маленькая S собрала множество чисел $\{c_1, \dots, c_m\}$ размера $m$. На основе этой информации возможную сеть подписок можно представить как ориентированный граф $G = (V, E)$, удовлетворяющий следующим условиям:

• Содержит $n$ пользователей, то есть множество вершин $V = \{1, 2, \dots, n\}$;
• Отсутствуют подписки на самого себя и дублирующиеся подписки, то есть граф $G$ не содержит петель и кратных ребер;
• Все отношения подписки являются строго односторонними, то есть для любого ориентированного ребра $(u, v) \in E$ выполняется $(v, u) \notin E$;
• Для каждого элемента $c_i$ из множества ($1 \le i \le m$) в графе $G$ существует по крайней мере одна вершина, чья исходящая степень (соответствует количеству подписок) или входящая степень (соответствует количеству подписчиков) в точности равна $c_i$.

Вам необходимо на основе информации, собранной маленькой S, восстановить сеть подписок с минимальным общим количеством подписок (то есть с минимальным количеством ребер в графе $G$).

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

Первая строка содержит неотрицательное целое число $o \in \{0, 1\}$, обозначающее параметр вывода.

Вторая строка содержит два положительных целых числа $n, m$ ($1 \le m < n \le 10^6$), обозначающих количество пользователей и размер множества, собранного маленькой S. Гарантируется, что если $o = 0$, то $n \le 2 \times 10^3$.

Третья строка содержит $m$ попарно различных положительных целых чисел $c_1, c_2, \dots, c_m$ ($1 \le c_i \le n - 1$), представляющих элементы множества, собранного маленькой S.

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

Выведите в первой строке положительное целое число $k$, обозначающее минимальное общее количество подписок во всех возможных сетях подписок.

Если $o = 0$, далее выведите $k$ строк, каждая из которых содержит два положительных целых числа $u, v$ ($1 \le u, v \le n$), означающих, что пользователь $u$ подписался на пользователя $v$, то есть $(u, v) \in E$.

Примеры

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

0
5 4
3 1 4 2

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

7
3 2
4 1
3 4
4 5
3 5
4 2
3 1