Даже маленькому Джону нужны деньги, чтобы купить дом. Но он недавно потерял работу; как же он теперь заработает деньги? Конечно, играя в игру, которая дает ему деньги в качестве награды! Ну, может быть, не в те игры, о которых вы думаете. На плоскости есть \(n+m\) различных точек \((a_1,0), (a_2,0), \ldots, (a_{n},0), (b_1,2), (b_2,2), \ldots, (b_{m},2)\). Изначально ваш счет равен \(0\). Чтобы увеличить свой счет, вы можете выполнить следующую операцию:
- Выберите три различные точки, которые не лежат на одной прямой.
- Увеличьте свой счет на площадь треугольника, образованного этими тремя точками.
- Затем удалите три точки с плоскости.
Пример игры, где операция выполняется дважды. Пусть \(k_{\max}\) — максимальное количество операций, которое можно выполнить. Например, если нельзя выполнить эту операцию ни разу, то \(k_\max\) равно \(0\). Кроме того, определим \(f(k)\) как максимальный возможный счет, который можно получить, выполнив операцию ровно \(k\) раз. Здесь \(f(k)\) определено для всех целых чисел \(k\), таких что \(0 \le k \le k_{\max}\).
Найдите значение \(k_{\max}\) и найдите значения \(f(x)\) для всех целых чисел \(x=1,2,\ldots,k_{\max}\) независимо.
Выходные данные
Для каждого набора входных данных, учитывая, что максимальное количество операций равно \(k_{\max}\), вы должны вывести не более двух строк:
- Первая строка содержит значение \(k_{\max}\);
- Вторая строка содержит \(k_{\max}\) целых числа, обозначающих \(f(1),f(2),\ldots,f(k_{\max})\). Вы можете опустить эту строку, если \(k_{\max}\) равно \(0\).
Обратите внимание, что в условиях этой задачи можно показать, что все значения \(f(x)\) являются целыми числами, не превышающими \(10^{16}\).
Примечание
В первом наборе входных данных есть \(1+3=4\) точки \((0,0),(0,2),(1,2),(-1,2)\).
Можно показать, что вы не можете выполнить две или более операций. Значение \(k_{\max}\) равно \(1\), и вас просят только о значении \(f(1)\).
Вы можете выбрать \((0,0)\), \((-1,2)\) и \((1,2)\) в качестве трех вершин треугольника. После этого ваш счет увеличивается на площадь треугольника, которая равна \(2\). Затем три точки удаляются с плоскости. Можно показать, что максимальное значение вашего счета после выполнения одной операции равно \(2\). Следовательно, значение \(f(1)\) равно \(2\).
В пятом наборе входных данных есть \(8+2=10\) точек.
Можно показать, что вы не можете выполнить три или более операций. Значение \(k_{\max}\) равно \(2\), и вас просят о значениях \(f(1)\) и \(f(2)\).
Чтобы максимизировать счет с помощью только одной операции, вы можете выбрать три точки \((198\,872\,582,0)\), \((-1\,000\,000\,000,2)\) и \((1\,000\,000\,000,2)\). Затем три точки удаляются с плоскости. Можно показать, что максимальное значение вашего счета после выполнения одной операции равно \(2\,000\,000\,000\). Следовательно, значение \(f(1)\) равно \(2\,000\,000\,000\).
Чтобы максимизировать счет с помощью ровно двух операций, вы можете выбрать следующую последовательность операций.
- Выберите три точки \((-509\,489\,796,0)\), \((553\,177\,666,0)\) и \((-1\,000\,000\,000,2)\). Три точки удаляются.
- Выберите три точки \((-400\,714\,529,0)\), \((564\,040\,265,0)\) и \((1\,000\,000\,000,2)\). Три точки удаляются.
Тогда счет после двух операций становится \(2\,027\,422\,256\). Можно показать, что максимальное значение вашего счета после выполнения ровно двух операций равно \(2\,027\,422\,256\). Следовательно, значение \(f(2)\) равно \(2\,027\,422\,256\).