graph

Given two positive integers $$$n, m$$$, qwqkawaii has a sequence of positive integers $$$c_1, c_2, \dots, c_m$$$ of length $$$m$$$, satisfying that each $$$c_i$$$ is less than $$$n$$$ and all $$$c_i$$$ are distinct.

qwqkawaii wants to construct a directed graph $$$G$$$ with $$$n$$$ vertices, where $$$G$$$ has no self-loops, multiple edges, or bidirectional edges. Moreover, for each $$$1 \le i \le m$$$, there exists a vertex in $$$G$$$ such that either its out-degree is $$$c_i$$$ or its in-degree is $$$c_i$$$.

qwqkawaii wants to know the minimum number of edges required for a graph $$$G$$$ to meet such requirements, and when $$$n$$$ is relatively small, provide a specific construction of $$$G$$$. More precisely, qwqkawaii will give a parameter $$$opt \in \{0, 1\}$$$. When $$$opt = 0$$$, qwqkawaii needs to know the minimum number of edges of graph $$$G$$$ and a corresponding $$$G$$$ that meets the minimum number of edges. When $$$opt = 1$$$, qwqkawaii only needs to know the minimum number of edges of graph $$$G$$$.

Input

The first line contains an integer $$$opt\ (opt \in \{0, 1\})$$$, representing the type of the query.

The second line contains two positive integers $$$n$$$ and $$$m$$$ ($$$1 \le m \lt n \le 10^6$$$), representing the number of vertices of graph $$$G$$$ and the sequence length, respectively. When $$$opt = 0$$$, it is guaranteed that $$$n \le 2 \times 10^3$$$.

The third line contains $$$m$$$ positive integers $$$c_1, \dots, c_m$$$ ($$$1 \le c_i \le n - 1$$$). It is guaranteed that all $$$c_i$$$ are distinct.

Output

If $$$opt = 0:$$$

First, output a line with a positive integer $$$x$$$, representing the minimum number of edges in $$$G$$$.
Next, for the next $$$x$$$ lines, output two positive integers $$$u$$$ and $$$v$$$ for each line, representing that vertex $$$u$$$ is connected to vertex $$$v$$$ with a directed edge. Please ensure that $$$1 \le u, v \le n$$$.

If $$$opt = 1:$$$

Output a positive integer $$$x$$$, representing the minimum number of edges in $$$G$$$.

Example

Input

0
5 4
3 1 4 2

Output

Note

For the example case, the graph $$$G$$$ has 7 edges. The out-degree of vertex 4 is 3, the in-degree of vertex 2 is 1, the out-degree of vertex 3 is 4, and the in-degree of vertex 1 is 2. One can prove that 7 is the minimum number of edges for graph $$$G$$$.