社交网络
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

> 讨论完令人头疼的科研与审稿,茶话会的话题逐渐转向了日常的社交。小 T 兴致勃勃地分享了他的一个有趣发现:在某一常用的社交平台上,用户彼此间的关注关系恰好都是严格的**单向关注**,即不存在两名用户互相关注的情况。 > > 这个奇妙的现象立刻引起了大家的讨论。小 S 顺势提取了该网络的部分统计数据,收集到了每位用户的关注数与粉丝数。遗憾的是,她在传阅数据的过程中不小心弄丢了一部分,最后只留下了一个由若干正整数构成的集合。小 S 发现,对于集合中的每一个元素,总能找到至少一个用户,其关注数或粉丝数恰好等于该元素。 > > 由于平台完整的关注结构对外保密,具体的社交关系网已无从知晓。为了验证这些残存数据的合理性,大家纷纷拿起了纸笔,尝试着还原出符合条件的网络。为了增添几分趣味与竞技性,大家甚至就此展开了一场小小的比赛,看谁能构造出总关注数最少的社交网络。

在这一社交平台上,共有 $$$n$$$ 位用户。小 S 收集到了一个大小为 $$$m$$$ 的数字集合 $$$\{c_1, \dots, c_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$$$ 边数最小)的关注网络。

Input

输入的第一行包含一个非负整数 $$$o \in \{0, 1\}$$$,表示输出的参数。

输入的第二行包含两个正整数 $$$n, m \ (1 \le m \lt 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 收集到的集合中的元素。

Output

输出一行一个正整数 $$$k$$$,表示所有可能的关注网络中总关注数的最小值。

若 $$$o = 0$$$,则接下来输出 $$$k$$$ 行,每行包含两个正整数 $$$u, v \ (1 \le u, v \le n)$$$,表示用户 $$$u$$$ 关注了用户 $$$v$$$,即 $$$(u, v) \in E$$$。

Example

Input
0
5 4
3 1 4 2
Output
7
3 2
4 1
3 4
4 5
3 5
4 2
3 1

Note

对于样例,图 $$$G$$$ 一共有 $$$7$$$ 条边,其中顶点 $$$4$$$ 的出度是 $$$3$$$,顶点 $$$2$$$ 的入度是 $$$1$$$,顶点 $$$3$$$ 的出度是 $$$4$$$,顶点 $$$1$$$ 的入度是 $$$2$$$。可以证明 $$$7$$$ 是图 $$$G$$$ 的最少边数。