Дан массив $$$a_1, a_2, \ldots, a_n$$$, где $$$n \leq 8$$$ и $$$a_1 + a_2 + \cdots + a_n \leq 100$$$.
Постройте простой многоугольник$$$^{\text{∗}}$$$ с не более чем $$$333$$$ вершинами, который имеет ровно $$$$$$\frac{(a_1 + a_2 + \cdots + a_n)!}{a_1! a_2! \cdots a_n!}$$$$$$ различных триангуляций$$$^{\text{†}}$$$. Можно доказать, что такой многоугольник всегда существует.
$$$^{\text{∗}}$$$Простой многоугольник — это многоугольник, который не пересекает сам себя и не имеет дыр. Иными словами, две стороны многоугольника, не являющиеся соседними, не должны иметь общих точек, а соседние стороны должны иметь ровно одну общую точку — вершину между ними. Последовательные стороны могут быть параллельными.
$$$^{\text{†}}$$$Триангуляция многоугольника с $$$m$$$ вершинами — это набор из $$$m-3$$$ диагоналей, которые пересекаются только в вершинах. Диагональю называется отрезок, соединяющий две вершины внутри многоугольника и имеющий ровно две общие точки со сторонами многоугольника — соединяемые вершины.
Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$2 \leq n \leq 8$$$) — количество элементов в массиве.
Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 100$$$) — элементы массива.
Гарантируется, что $$$a_1 + a_2 + \cdots + a_n$$$ не превосходит $$$100$$$.
В первой строке выведите одно целое число $$$m$$$ ($$$3 \leq m \leq 333$$$) — количество вершин в многоугольнике.
В $$$i$$$-й из следующих $$$m$$$ строк выведите два целых числа $$$x_i$$$, $$$y_i$$$ ($$$-10^6 \leq x_i, y_i \leq 10^6$$$) — координаты $$$i$$$-й вершины многоугольника.
Многоугольник должен быть простым. Вершины могут быть даны в порядке по или против часовой стрелки.
31 1 2
8 0 0 2 1 4 2 6 1 3 5 4 7 0 5 1 2
24 1
5 -2 -2 -3 1 0 3 3 1 2 -2
В первом наборе входных данных требуемый многоугольник должен иметь $$$\tfrac{4!}{1! 1! 2!} = 12$$$ триангуляций. Ниже приведены все триангуляции приведенного многоугольника.
Во втором наборе входных данных требуемый многоугольник должен иметь $$$\tfrac{5!}{4! 1!} = 5$$$ триангуляций.
