Ana and Barbu are playing a new game. They chose a one-dimensional array v, with n positive integer components, numbered from 0 to n-1. The first component of one-dimensional array (v[0]) is 0. The other components are non-zero positive integers.
They alternate in executing moves of the following kind on this one-dimensional array: they choose a position i (0 < i < n) and an integer value x (0 < x <= v[i]), and then v[i] drops by x, and v[i-1] increases by x.
Ana has the first move. The player that can't execute any more operations loses.

Line one of input file vector.in contains number n. The next line contains positive integers v[1], v[2], ..., v[N-1], each separated by a space.

Line one of input file vector.out will contain digit 1 if Ana has a sure winning strategy or digit 0 if she doesn't. If Ana has a sure winning strategy, line two will contain the two positive integers, i and x, separated by a single space, representing the first optimum move for Ana. If there is more than one solution, the solution with i minimum will be displayed. If there is more than one solution with i minimum, the solution with x minimum will be displayed.

• 1 <= n <= 2¹⁷
• v[0] = 0
• 0 < v[i] < 2³⁰, v[i] positive integer, for any i with 0 < i < N
• The supposition is that Ana and Barbu play perfectly.
• We say that Ana has a sure winning strategy under the conditions that if Ana plays perfect, no matter the move Barbu makes, he will lose.
  

vector.in	vector.out
3 1947 1986	1 1 1947

Time limit: 0.1 seconds/test

Tiberiu-Lucian Florea
University of Bucharest, Mathematics & IT Department
Contact:tiberiu.florea@gmail.com