У Gildong есть квадратная доска из \(n\) строк и \(n\) столбцов квадратных клеток, каждая клетка содержит одну цифру (от \(0\) до \(9\)). Клетка на пересечении \(j\)-го столбца и \(i\)-й строки может быть описана как \((i, j)\), длины сторон каждой клетки равны \(1\). Gildong любит большие вещи, так что для каждой цифры \(d\) он хочет найти треугольник такой, что:
- Каждая вершина треугольника находится в центре клетки.
- Цифра на каждой вершине треугольнике равна \(d\).
- Хотя бы одна сторона треугольника параллельна одной из сторон доски. Вы можете считать, что сторона длины \(0\) параллельна обоим сторонам доски.
- Площадь треугольника максимальна.
Конечно, его не успокоят только эти треугольники. Для каждой цифры \(d\) он хочет изменить цифру у ровно одной клетки доски на \(d\), и затем найти искомый треугольник. Он меняет цифру этой клетки обратно после того, как он нашел треугольник. Найдите максимальную площадь треугольника, которую он может получить, для каждой цифры.
Обратите внимание, что он может ставить несколько вершин треугольника на одну и ту же клетку, и что треугольник может быть вырожденным; иначе говоря, площадь треугольника может быть равна \(0\). Также обратите внимание, что разрешается менять цифру \(d\) на \(d\).
Выходные данные
Для каждого набора входных данных, выведите строку из \(10\) целых чисел. \(i\)-е из них должно быть равно максимальной площади, которую может получить Gildong, для \(d = i-1\), умноженной на \(2\).
Примечание
В первом наборе входных данных для \(d=0\) вне зависимости от выбранной клетки треугольник с вершинами \((1, 1)\), \((1, 3)\) и \((3, 1)\) — это самый большой треугольник площади \(\cfrac{2 \cdot 2}{2} = 2\). Так как мы должны вывести ответ, умноженный на \(2\), ответ для \(d=0\) это \(4\).
Для \(d=1\) Gildong может поменять цифру у клетки \((1, 3)\) на \(1\), получив треугольник с вершинами в клетках с цифрой \(1\) с площадью \(2\).
Для \(d=2\) Gildong может поменять цифру ровно одной из следующих клеток на \(2\), чтобы получить треугольник с площадью \(\cfrac{1}{2}\): \((1, 1)\), \((1, 2)\), \((1, 3)\), \((3, 1)\), \((3, 2)\) и \((3, 3)\).
Для остальных цифр (от \(3\) до \(9\)) клетка, которую поменяет Gildong, будет единственной клеткой, содержащей эту цифру. Таким образом, треугольник всегда будет вырожденным и площади \(0\).
В третьем наборе входных данных для \(d=4\) обратите внимание, что треугольник будет больше чем ответ, если Gildong поменяет цифру у клетки \((1, 4)\), а затем выберет дополнительно клетки \((2, 1)\) и \((4, 3)\), но это некорректно, потому что это не удовлетворяет условию, что хотя бы одна сторона треугольника должна быть параллельна стороне доски.