G. Новые дороги
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В Берляндии есть n городов, каждый из которых имеет свой уникальный номер — целое число от 1 до n, причём столица имеет номер 1. В Берляндии в настоящий момент совсем плохо с дорогами — их нет.

По этой причине было решено построить n - 1 дорогу так, чтобы между каждой парой городов существовал ровно один путь по дорогам.

В плане на постройку дорог было указано t чисел a1, a2, ..., at, где t равно расстоянию от столицы до самого удаленного города, если добираться до него только по новым дорогам, а ai равно количеству городов, которые должны находиться на расстоянии i от столицы. Под расстоянием понимается количество дорог, которые нужно преодолеть на пути от одного города до другого.

Также было решено, что среди всех городов, исключая столицу, должно быть ровно k городов, к которым примыкает ровно одна дорога. Такие города являются тупиковыми и не могут быть экономически привлекательными. При подсчете таких городов столица не учитывается независимо от количества примыкающих дорог к ней.

Перед вами стоит задача предложить план постройки дорог, удовлетворяющий всем описанным условиям, либо сообщить, что это невозможно.

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

В первой строке следуют три целых положительных числа n, t и k (2 ≤ n ≤ 2·105, 1 ≤ t, k < n) — расстояние до максимально удалённого города от столицы и количество городов, которые должны быть тупиковыми (столица в этом количестве не учитывается).

Во второй строке следует последовательность из t целых чисел a1, a2, ..., at (1 ≤ ai < n), где i-е число равно количеству городов, которые должны находиться на расстоянии i от столицы. Гарантируется, что сумма всех значений ai равна n - 1.

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

Если построить дороги, удовлетворяющие всем условиям, невозможно, выведите -1.

В противном случае, выведите в первую строку одно целое число n — количество городов в Берляндии. В следующей n - 1 строке выведите по два целых числа — номера городов, которые соединяет очередная дорога. Каждая дорога должна быть выведена ровно один раз. Порядок вывода дорог и соединяемых дорогой городов неважен.

Если решений несколько, выведите любое. Помните, что столица имеет номер 1.

Примеры
Входные данные
7 3 3
2 3 1
Выходные данные
7
1 3
2 1
2 6
2 4
7 4
3 5
Входные данные
14 5 6
4 4 2 2 1
Выходные данные
14
3 1
1 4
11 6
1 2
10 13
6 10
10 12
14 12
8 4
5 1
3 7
2 6
5 9
Входные данные
3 1 1
2
Выходные данные
-1