Как известно, все дети в Берляндии любят играть с кубиками. У маленького Пети имеется n башен, состоящих из кубиков одинакового размера. Башня под номером i представляет собой ai кубиков, поставленных друг на друга. Неустойчивостью набора башен Петя называет величину, равную разности высот самой высокой и самой низкой башни. К примеру, если Петя построил из кубиков пять башен с высотами (8, 3, 2, 6, 3), то неустойчивость этого набора равна 6 (самая высокая башня имеет высоту 8, самая низкая — высоту 2).
Мальчик хочет, чтобы неустойчивость его набора башен была как можно меньше. Все, что он может сделать, это несколько раз проделать следующую операцию: взять верхний кубик с какой-то из башен и положить его сверху на какую-то другую башню из своего набора. Обратите внимание, что Петя никогда не будет класть кубик на ту же башню, с которой тот был снят, потому что считает это пустой тратой времени.
Прежде чем отправиться в школу, мальчик успеет произвести не более k таких операций. Петя не хочет опоздать на урок, поэтому вам придется помочь ему выполнить эту задачу.
Выходные данные
В первой строке выведите через пробел два целых неотрицательных числа s и m (m ≤ k). Первое из чисел — это величина минимально возможной неустойчивости, которую можно достичь, применив не более k операций, а второе — количество операций, необходимых для этого.
Затем в m строках выведите описание каждой из операций в виде двух целых положительных чисел i и j, каждое из которых лежит в пределах от 1 до n. Они обозначают, что Петя переложил верхний кубик с i-й башни на j-ю (i ≠ j). Обратите внимание, что в процессе выполнения операций высоты некоторых башен могут стать равны нулю.
Если существует несколько корректных последовательностей операций, при которых достигается минимально возможная неустойчивость, разрешается вывести любую из них.
Примечание
В первом примере осуществляется два перекладывания, со второй башни на третью и со второй на первую. После этого высоты башен становятся одинаковыми и равными 6.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 2
5 8 5
|
0 2
2 1
2 3
|
|
2
|
3 4
2 2 4
|
1 1
3 2
|
|
3
|
5 3
8 3 2 6 3
|
3 3
1 3
1 2
1 3
|