В Берляндии есть n городов, каждый из которых имеет свой уникальный номер — целое число от 1 до n, причём столица имеет номер 1. В Берляндии в настоящий момент совсем плохо с дорогами — их нет.
По этой причине было решено построить n - 1 дорогу так, чтобы между каждой парой городов существовал ровно один путь по дорогам.
В плане на постройку дорог было указано t чисел a1, a2, ..., at, где t равно расстоянию от столицы до самого удаленного города, если добираться до него только по новым дорогам, а ai равно количеству городов, которые должны находиться на расстоянии i от столицы. Под расстоянием понимается количество дорог, которые нужно преодолеть на пути от одного города до другого.
Также было решено, что среди всех городов, исключая столицу, должно быть ровно k городов, к которым примыкает ровно одна дорога. Такие города являются тупиковыми и не могут быть экономически привлекательными. При подсчете таких городов столица не учитывается независимо от количества примыкающих дорог к ней.
Перед вами стоит задача предложить план постройки дорог, удовлетворяющий всем описанным условиям, либо сообщить, что это невозможно.
Выходные данные
Если построить дороги, удовлетворяющие всем условиям, невозможно, выведите -1.
В противном случае, выведите в первую строку одно целое число n — количество городов в Берляндии. В следующей n - 1 строке выведите по два целых числа — номера городов, которые соединяет очередная дорога. Каждая дорога должна быть выведена ровно один раз. Порядок вывода дорог и соединяемых дорогой городов неважен.
Если решений несколько, выведите любое. Помните, что столица имеет номер 1.