Задача E. Enforcing nine

Автор:М. Спорышев   Ограничение времени:4 сек
Входной файл:Стандартный вход   Ограничение памяти:512 Мб
Выходной файл:Стандартный выход  

Условие

Дан массив целых чисел ai. Вы можете выбрать в нем один элемент и заменить в нем одну любую десятичную цифру на любую другую. Стоимость такого изменения равна модулю разницы новой и старой цифры.

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

Лидирующие нулевые цифры менять нельзя.

Формат входных данных

Входные данные содержат целое число N — размер массива, за которым следует N целых чисел ai.

Формат выходных данных

Выведите три целых числа: номер элемента, номер цифры, которую нужно заменить, и цифру, на которую делать замену.

Элементы и цифры нумеруются начиная с 0. Цифры нумеруются справа налево.

Гарантируется, что в сумме элементов исходного массива не содержится цифры 9.

Если требуемого изменения не существует, вывести 1. Если решений несколько, вывести любое из них.

Ограничения

1 ≤ N ≤ 100000

|ai| ≤ 109

ai ≠ 0

Примеры тестов

Стандартный вход Стандартный выход
1
1
1
0 0 9
2
3
11 1 31
0 1 6
3
2
-8 8
-1

0.115s 0.020s 15