이 소셜 플랫폼에는 총 $n$명의 사용자가 있습니다. 소 S는 크기가 $m$인 숫자 집합 $\{c_1, \dots, c_m\}$을 수집했습니다. 이 정보를 바탕으로, 가능한 팔로우 네트워크를 다음 조건을 만족하는 유향 그래프 $G = (V, E)$로 추상화할 수 있습니다.

• $n$명의 사용자를 포함합니다. 즉, 정점 집합 $V = \{1, 2, \dots, n\}$입니다.
• 자기 자신을 팔로우하거나 중복 팔로우하는 경우가 없습니다. 즉, 그래프 $G$는 자기 루프(self-loop)와 다중 간선(multiple edge)을 포함하지 않습니다.
• 모든 팔로우 관계는 엄격한 단방향 팔로우입니다. 즉, 임의의 유향 간선 $(u, v) \in E$에 대하여 $(v, u) \notin E$를 만족합니다.
• 집합의 각 원소 $c_i (1 \le i \le m)$에 대하여, 그래프 $G$에는 출차수(팔로우 수) 또는 입차수(팔로워 수)가 정확히 $c_i$와 같은 정점이 적어도 하나 존재합니다.

소 S가 수집한 정보를 바탕으로, 총 팔로우 수(즉, 그래프 $G$의 간선 수)가 최소인 팔로우 네트워크를 복원해야 합니다.

입력

입력의 첫 번째 줄에는 출력 파라미터를 나타내는 음이 아닌 정수 $o \in \{0, 1\}$이 주어집니다.

입력의 두 번째 줄에는 사용자 수와 소 S가 수집한 집합의 크기를 나타내는 두 정수 $n, m (1 \le m < n \le 10^6)$이 주어집니다. $o = 0$인 경우 $n \le 2 \times 10^3$임이 보장됩니다.

입력의 세 번째 줄에는 소 S가 수집한 집합의 원소인 서로 다른 $m$개의 양의 정수 $c_1, c_2, \dots, c_m (1 \le c_i \le n - 1)$이 주어집니다.

출력

첫 번째 줄에 모든 가능한 팔로우 네트워크 중 총 팔로우 수의 최솟값 $k$를 출력합니다.

$o = 0$인 경우, 이어서 $k$줄을 출력하며, 각 줄에는 사용자 $u$가 사용자 $v$를 팔로우함을 나타내는 두 정수 $u, v (1 \le u, v \le n)$를 출력합니다. 즉, $(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