Работая с перестановками чисел от $$$ 1 $$$ до $$$ n $$$, программист Вася заметил, что некоторые из них обладают интересными свойствами. Например, в перестановках «3 1 2» и «3 2 1» первый элемент равен сумме всех других элементов. В перестановке «1 2 3 4 5» уже конкатенация (приписывание одного числа к другому) двух первых элементов равна сумме оставшихся ($$$ 12 = 3 + 4 + 5 $$$).
Вася задался вопросом: а для любого ли $$$ n $$$ можно найти такую перестановку чисел $$$ 1..n $$$, что первый элемент, либо конкатенация двух первых, будет равна сумме оставшихся?
Напишите программу, которая по данному числу $$$ n $$$ определит, какие элементы нужно поставить в начало перестановки, чтобы либо первый элемент, либо конкатенация двух первых, дали сумму всех оставшихся. Если таких элементов нет, то программа должна сообщить об отсутствии решения.
В единственной строке содержится число $$$ n $$$ ($$$ 1 \leq n \leq 10^{9} $$$) – количество элементов в перестановке.
В единственной строке выведите $$$ 0 $$$, если решения не существует. Если существует один элемент, который равен сумме оставшихся, то выведите через пробел два числа: «1» и найденный элемент. Если существуют два элемента, конкатенация которых дает число, равное сумме оставшихся элементов, то выведите «2», а затем два числа разделённые пробелом – два элемента в том порядке, в котором их нужно приписывать друг к другу.
3
1 3
5
2 1 2
2
0
