Задача F. Ехидный барин ≡

Условие

При проведении крестьянской реформы 1861 года и в соответствии с её «Общим положением о вышедших из крепостной зависимости», помещики обязаны были предоставить в пользование крестьянам полевой надел. Особенностью реформы было то, что земли надела предоставлялись не лично конкретному крестьянину, а в коллективное пользование сельским обществам, которые уже могли распределять их между хозяйствами по своему усмотрению.

Сельскому обществу надлежит распределить между хозяйствами полевой надел в форме квадрата со стороной n. По прихоти барина от двух противоположных углов квадрата следует отрезать два квадрата меньших размеров, чтобы их суммарная площадь равнялась площади оставшейся части, а всего получилось три земельных участка. Помогите крестьянам выполнить задание сумасбродного помещика.

Формат входных данных

Единственная строка входных данных содержит натуральное числа n. Гарантируется четность n.

Формат выходных данных

Выведите в первой строке натуральное число a — количество подходящих решений. В следующих a строках через пробел в порядке возрастания выведите два натуральных числа: стороны подходящих квадратных участков меньших размеров. Гарантируется, что входные данные предусматривают по крайней мере одно решение в натуральных числах. Пары выводите в порядке возрастания первого их двух чисел.

Ограничения

10 ≤ n ≤ 10⁵

Пояснение к примерам

В первом примере дано n = 10. Смотри рисунок: единственное подходящее решение — отрезать от одного угла квадрат площадью 49, а от другого площадью 1. Тогда суммарная площадь двух квадратов равна 50 и равна площади оставшейся части. Решение, при котором отрезаются квадраты площадью 25 не подходит — большой квадрат разделится на четыре части, а не на три.

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

10

1
1 7

50

2
5 35
17 31