Задача B. Гиперпространства

Автор:Михаил Дворкин (Городская олимпиада школьников Санкт-Петербурга по информатике 2006)   Ограничение времени:2 сек
Входной файл:hyper.in   Ограничение памяти:64 Мб
Выходной файл:hyper.out  

Условие

Недавно Миша узнал о существовании многомерных пространств. В n-мерном пространстве точка задается набором из n вещественных координат. Миша сразу же догадался как измерить расстояние между двумя точками — расстояние между точками (x1, x2, …, xn) и (y1, y2, …, yn) равно sqrt((x1 − y1)2 + (x2 − y2)2 + …  + (xn − yn)2).

Для начала он стал исследовать отрезки. Отрезок, соединяющий точки (x1, x2, …, xn) и (y1, y2, …, yn) — это множество точек с координатами (λ x1 + (1 − λ)y1, λ x2 + (1 − λ)y2, …, λ xn + (1 − λ)yn), где λ ∈ [0,1].

Миша называет точку с целочисленными координатами видимой, если на отрезке, соединяющем эту точку с началом координат (точкой, все координаты которой равны нулю), не лежит других целочисленных точек. Например, в двумерном пространстве точка (2, 1) является видимой, а точка (2, 2) — нет, во втором случае соответствующий отрезок содержит точку (1, 1).

Теперь Мишу заинтересовал вопрос — а в пространстве какой минимальной размерности существует видимая точка, расстояние от которой до начала координат равно sqrt(l). Также его интересует, а сколько видимых точек в пространстве этой размерности находятся на расстоянии sqrt(l) от начала координат. Помогите ему решить эту задачу.

Формат входного файла

Входной файл содержит целое число l.

Формат выходного файла

На первой строке выходного файла выведите n — минимальную размерность пространства, в которой существует искомая точка. На второй строке выведите n целых чисел — координаты любой такой точки. На третьей строке выведите количество таких точек в пространстве размерности n.

Ограничения

1 ≤ l ≤ 50,000.

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

Входной файл (hyper.in) Выходной файл (hyper.out)
1
8
5
1 2 1 1 1
160

0.143s 0.012s 13