Working with permutations of numbers from $$$ 1 $$$ to $$$ n $$$, programmer Vasya noticed that some of them have interesting properties. For example, in the permutations "3 1 2" and "3 2 1", the first element is equal to the sum of all other elements. In the permutation "1 2 3 4 5" already the concatenation (attribution of one number to another) of the first two elements is equal to the sum of the remaining ($$$ 12 = 3 + 4 + 5 $$$). Vasya wondered: is it possible for any $$$ n $$$ to find such a permutation of the numbers $$$ 1..n $$$ that the first element, or the concatenation of the first two, will be equal to the sum of the remaining ones?
Write a program that, based on a given number $$$ n $$$, finds which elements need to be put at the beginning of the permutation so that either the first element or the concatenation of the first two will give the sum of all the remaining ones. If there are no such elements, then the program should report the absence of a solution.
The single string contains the number $$$ n $$$ ($$$ 1 \leq n \leq 10^{9} $$$) – the number of elements in the permutation.
In a single string print $$$ 0 $$$ if there is no solution. If there is one element that is equal to the sum of the remaining ones, then print two numbers separated by a space: "1" and the found element. If there are two elements, whose concatenation gives a number equal to the sum of the remaining elements, print "2", and then two numbers separated by a space – two elements in the order in which they need to be attributed to each other.
3
1 3
5
2 1 2
2
0
