Problem E. Enforcing nine

Author:М. Спорышев   Time limit:4 sec
Input file:Standard input   Memory limit:512 Mb
Output file:Standard output  

Statement

There is an array of integers ai. You can choose any single element and replace any single decimal digit of it with any other one. Cost of such replacement is equal to absolute value of the difference between digits.

Your program must find such a replacement of single digit in a single element that the decimal representation of the sum of all elements will contain at least one digit 9, or determine that it does not exist. The cost of chosen replacement must be minimal possible.

Leading zeroes are not eligible for replacement.

Input format

Input contains integer N — array size, followed by N integers ai.

Output format

Output three integers: element number, number of digit to be replaced and the digit to replace with.

Elements and digits are numbered starting with 0. Digits are numbered right to left.

It is guaranteed that sum of elements of the input array does not contain digit 9.

If required replacement does not exist, output  − 1. If there are several solutions, output any of them.

Constraints

1 ≤ N ≤ 100000

|ai| ≤ 109

ai ≠ 0

Sample tests

No. Standard input Standard output
1
1
1
0 0 9
2
3
11 1 31
0 1 6
3
2
-8 8
-1

0.069s 0.008s 13