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

Для того, чтобы освещать площадку ночью, на ней надо установить несколько прожекторов. К счастью, у фирмы как раз в наличие есть три регулируемых прожектора, а на территории площадки обнаружились три высоких столба. Было решено на каждый столб повесить по прожектору и отрегулировать их так, чтобы каждый прожектор освещал ровно одну из трёх сторон забора: один прожектор должен освещать одну сторону забора, другой — другую, третий — третью. Никакой прожектор не должен освещать ни миллиметра “чужой” стены.

Конечно, прожекторы должны освещать не только забор, но вообще всю территорию площадки, поэтому возникла проблема: надо определить, какой прожектор на какую сторону забора направить. Зная ваши высокие навыки в решении подобных задач, фирма обратилась к вам за помощью. Напишите программу, которая будет решать эту задачу.

Естественно, каждый прожектор освещает не только стену, но и всю соответствующую часть двора — треугольник с вершиной в месте, где находится столб, на котором висит прожектор, и основанием, совпадающим с соответствующей стороной забора. Будем считать, что стороны этого треугольника тоже освещены прожектором. Тенью от столбов пренебрегайте.

Миша часто ездит в маршрутках. Миша законопослушный, поэтому он всегда покупает билет. Каждый билет в маршрутке имеет номер — \(2N\)-значное десятичное число, возможно, с ведущими нулями. После покупки билета Миша всегда проверяет, счастливый ли достался ему билет. Счастливым Миша считает такой билет, у которого сумма первых \(N\) цифр номера равна сумме последних \(N\) цифр. Если билет оказывается несчастливым, Миша ищет расстояние до ближайшего счастливого, т.е. минимальное число \(x\) такое, что если к номеру билета, полученного Мишей, прибавить или отнять \(x\) (при этом, разумеется, полученный номер должен быть корректным номером билета, т.е. должен быть не меньше нуля и не больше \(10^{2N}-1\)), то получившийся номер должен быть номером счастливого билета.

Билеты, у которых это расстояние максимально среди всех возможных, Миша называет совершенно несчастливыми. Мише очень интересно, сколько всего существует совершенно несчастливых билетов и какие номера у этих билетов. Но так как Миша плохо учился в школе, он не знает, как решать такую задачу, поэтому он обратился за помощью к вашему другу, специалисту по маршруткам. Он же перенаправил Мишу к вам.

Мальчик Влад недавно побывал в Японии и привёз оттуда новую жевательную резинку. Вернувшись в университет после поездки, на первой же паре Влад раздал жвачку всем своим \((N-1)\) однокурсникам и взял одну себе. Дождавшись момента, когда лектор отвернулся к доске, на счёт “три-четыре” все \(N\) студентов дружно начали надувать пузыри. Известно, что \(i\)-й студент надувает пузырь до максимально возможного размера за время \(t_i\), после чего пузырь мгновенно лопается, и студент начинает надувать пузырь заново с той же скоростью.

Всё это время преподаватель настолько увлечён тонкостями квантового математического анализа, что не слышит ничего происходящего в аудитории. И только когда все \(N\) пузырей лопнут одновременно, преподаватель услышит шум и обернётся. И уж тогда студентам достанется, а больше всех тому, кто принёс на пару \(N\) жевательных резинок.

Определите, сколько времени студенты смогут наслаждаться надуванием пузырей, не замечаемые преподавателем.

Например, если \(N=2\), \(t_1=2\), \(t_2=3\), то будет происходить следующее:

Первый студент надувает пузырь с момента времени \(t=0\) до момента времени \(t=2\), потом пузырь лопается, и он надувает пузырь заново — с момента времени \(t=2\) до момента времени \(t=4\), а потом ещё раз — с момента времени \(t=4\) до \(t=6\).

Второй студент надувает пузырь с \(t=0\) до \(t=3\) и ещё раз с \(t=3\) до \(t=6\).

В момент \(t=6\) пузыри лопаются одновременно у обоих студентов, преподаватель оборачивается и говорит: “Всё, Влад! Ты меня достал!”.

У мальчика Васи есть \(N\) шоколадок (возможно, разного веса). Вася пригласил к себе в гости \(K\) своих друзей и хочет подарить им шоколадки. Чтобы никому из друзей не было обидно, Вася решил раздать шоколадки так, чтобы каждому другу досталось одно и то же количество шоколада (т.е. суммарный вес шоколадок, доставшихся каждому другу, должен быть одинаковым). Вася может раздать все свои шоколадки, может раздать лишь часть, но, поскольку он — очень гостеприимный мальчик, он не хочет оставлять друзей совсем без шоколада (т.е. сумма весов шоколадок, доставшихся каждому другу, должна быть строго положительной). Все шоколадки красиво упакованы, т.е. делить их на части нельзя.

Определите, сколько у Васи есть способов раздать шоколад своим друзьям. Два способа считайте различными тогда и только тогда, когда существует шоколадка, которая в одном способе досталась некоторому другу, а в другом — другому другу или вовсе не была отдана друзьям.