В одном далеком мире, в славном городе Эрбовле открыли новый банк. В банке есть \(m\) сотрудников, работающих с клиентами, и один главный бухгалтер.

Для решения своих проблем в банк приходят гномы. Известно, что \(i\)-й гном приходит в банк через \(t_i\) минут после открытия банка. Сначала ему нужно провести \(a_i\) минут у одного из \(m\) сотрудников, а потом еще \(b_i\) минут в офисе главного бухгалтера.

Разумеется несколько гномов не могут одновременно находиться у одного сотрудника или в офисе главного бухгалтера, поэтому к сотрудникам и к главному бухгалтеру формируются очереди.

Очередь к сотрудникам общая, при этом гном из очереди идет к первому освободившемуся сотруднику. Если в банк одновременно приходят два гнома, то первым в очередь к сотрудникам встает тот, чей номер меньше. Если гном начал обслуживаться у сотрудника в момент \(x\), то он освобождается в момент \(x+a_i\), в этот момент другой гном может начать обслуживаться у этого же сотрудника. Гном, пришедший в банк в момент \(t\), может начать обслуживаться у сотрудника в любой момент, начиная с \(t\).

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

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

Андрей очень любит играть в Космический покер.

В космическом покере вместо карт используются фишки трех цветов. Казино определяет два числа \(A\) и \(C\) - коэффициенты для вычисления ставок. Затем игрок по определенным правилам ставит фишки трех цветов: красного, зеленого и синего. Выигрыш игрока вычисляется по формуле:
A * (\(r^2\) + \(g^2\) + \(b^2\)) + C * min{\(r\), \(g\), \(b\)}, где \(r\), \(g\), \(b\) - количество фишек красного, зеленого и синего соответственно.

Правила, по которым делаются ставки, очень сложны, но сейчас перед Андреем стоит следующая задача. На поле уже есть \(r\) красных, \(g\) зеленых и \(b\) синих фишек. Прежде чем будет определен его выигрыш, он может добавить на поле ровно одну фишку любого цвета. Помогите ему выбрать цвет фишки, которую следует добавить на поле, чтобы максимизировать выигрыш.

Алан любит вскрывать шифры и кодовые замки. На этот раз ему попался необычайно сложный замок, найти ключ к которому Алану не удалось, поэтому он решил перебрать все возможные комбинации, чтобы узнать ключ.

Замок представляет собой \(n\) кнопок, пронумерованных целыми числами от 1 до \(n\). Замок открывается только тогда, когда какие-то последовательные \(n\) нажатий на кнопки образуют некоторую секретную перестановку. Кнопки замка следует нажимать по очереди, нажать одновременно две или более кнопки нельзя.

Более формально: предположим, что Алан нажал на кнопки \(k\) раз. Пусть \(a_i\) (\(1 \le i \le k\)) - номер кнопки, которую Алан нажал \(i\) по счету, а \(b_1, b_2, \ldots, b_n\) - секретная перестановка. Тогда замок открывается, если существует такое число \(x\) (\(1 \le x \le k - n + 1\)), что \(b_1 = a_x\), \(b_2 = a_{x+1}\),..., \(b_n = a_{x+n-1}\).

Алан хочет придумать такую универсальную последовательность нажатий, что при нажатии кнопок в такой последовательности замок откроется для любой секретной перестановки. Также Алан хочет, чтобы эта последовательность не была слишком длинной, а именно, ее длина не превышала \(2n!\), где \(n! = 1 \cdot 2 \cdot \ldots \cdot n\). Например, для \(n = 3\) длина последовательности не должна превышать 12.

Помогите Алану найти такую последовательность.

В Байтландии вспыхнула эпидемия опасной болезни. Известно, что возбудителями болезни являются \(n\) различных болезнетворных бактерий.

Для правильного лечения пациента врачам необходимо знать, чем именно была вызвана его болезнь. Для этого пациент сдает \(m\) анализов: каждый анализ проверяет наличие или отсутствие некоторых видов бактерий. Анализ дает положительный результат, если в крови у человека есть хотя бы один из проверяемых этим анализом возбудителей болезни.

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

Королевство Флатландия имеет вид бесконечной двумерной плоскости. В королевстве находится \(n\) замков. Для более удобного составления карт в Флатландии была введена Декартова система координат. Известно, что \(i\)-й замок находится в точке с координатами \((x_i+0.5, y_i+0.5)\), где \(x_i\), \(y_i\) - целые числа. Местоположения всех замков попарно различны.

На старости лет король решил разделить на карте королевство между своими сыновьями прямыми, параллельными осям координат. Если прямая параллельна оси \(Ox\), то \(y\) координата у всех точек на прямой должна быть целым числом, иначе \(x\) координата у всех точек должна быть целым числом. В обоих случаях соответствующие целые координаты по модулю не должны превышать \(2 \cdot 10^9\). При этом Его величество хочет, что бы после разделения королевства любые два замка оказались бы в различных частях.

Помогите королю разделить королевство, используя не более чем \(n-1\) прямую. У любой пары прямых должно быть не более одной общей точки.