On this social platform, there are $n$ users. Xiao S has collected a set of $m$ numbers $\{c_1, \dots, c_m\}$. Based on this information, a possible follow network can be abstracted as a directed graph $G = (V, E)$ satisfying the following conditions:

• It contains $n$ users, i.e., the vertex set $V = \{1, 2, \dots, n\}$;
• There are no self-follows or duplicate follows, i.e., the graph $G$ contains no self-loops or multiple edges;
• All follow relationships are strictly one-way, i.e., for any directed edge $(u, v) \in E$, it holds that $(v, u) \notin E$;
• For every element $c_i$ ($1 \le i \le m$) in the set, there exists at least one vertex in graph $G$ whose out-degree (corresponding to follow count) or in-degree (corresponding to follower count) is exactly equal to $c_i$.

You need to reconstruct a follow network with the minimum total number of follows (i.e., the minimum number of edges in graph $G$) based on the information collected by Xiao S.

Input

The first line contains a non-negative integer $o \in \{0, 1\}$, representing the output parameter.

The second line contains two positive integers $n, m$ ($1 \le m < n \le 10^6$), representing the number of users and the size of the set collected by Xiao S. It is guaranteed that if $o = 0$, then $n \le 2 \times 10^3$.

The third line contains $m$ distinct positive integers $c_1, c_2, \dots, c_m$ ($1 \le c_i \le n - 1$), representing the elements in the set collected by Xiao S.

Output

Output one positive integer $k$ on a single line, representing the minimum total number of follows in all possible follow networks.

If $o = 0$, then output $k$ additional lines, each containing two positive integers $u, v$ ($1 \le u, v \le n$), representing that user $u$ follows user $v$, i.e., $(u, v) \in E$.

Examples

Input 1

0
5 4
3 1 4 2

Output 1

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