Задача A. Разделение королевства ≡

Условие

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

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

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

Формат входного файла

В первой строке задано целое число n (1 ≤ n ≤ 100 000) — количество замков в королевстве. В следующих n строках записано по два числа x_i и y_i (−10⁹ ≤ x_i ≤ 10⁹, −10⁹ ≤ y_i ≤ 10⁹) — целые части координат замков.

Формат выходного файла

В первой строке выходного файла выведите количество используемых прямых. В следующих строчках выведите сами прямые, по одной в каждой строке. Если прямая параллельна оси Ox, то выведите символ y, а затем через пробел y координату всех точек на этой прямой, иначе выведите символ x, а затем через пробел x координату всех точек на этой прямой.

Примеры тестов

4
0 2
0 3
1 2
1 3

2
x 1
y 3

Задача B. Осенний парк ≡

Условие

Воскресенье, утро. Пора на олимпиаду. Вениамин взял пачку чистой бумаги, ручку, пару бутербродов — что еще понадобится? — и открыл картографический сайт чтобы посмотреть, куда и как ему добираться. Какая удача! На пути есть прекрасный парк, а Вениамин как раз любит гулять по паркам. Парк представляет собой прямоугольное поле, разбитое на квадратные клеточки, в каждой из которых либо газон с дорожками, либо какое-то препятствие (заросли кустарника, деревья, а то и вовсе какой-нибудь огороженный памятник).

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

Вход в парк и выход из него — это некоторые выделенные различные клетки в парке, выходить за пределы парка запрещается, передвигаться можно только между соседними по ребру клетками. Вениамин должен гулять на две секунды дольше оптимального времени прохода от входа к выходу, поэтому он может в качестве промежуточной точки пути оказаться на входе или выходе. Поскольку ответ на задачу может быть довольно большим, от вас требуется остаток от деления количества путей на 10⁹ + 9.

Формат входного файла

В первой строке входного файла заданы два числа h и w: размеры парка. Следующие h~строк содержат по w~символов в каждой. Символ "." означает, что в соответствующей клетке дорожка или газон, по которому можно ходить. Символ "#" означает препятствие. Символы "E" и "X" означают вход в парк и выход из него соответственно.

Ограничения: 1 ≤ h ≤ 500, 1 ≤ w ≤ 500, символы "E" и "X" встречаются во входном файле ровно по одному разу. Обратите внимание, что вход и выход не обязательно находятся на границе парка: например, клеткой входа может быть расположенный в парке вестибюль метро, из которого Вениамин собирается выходить на своем пути.

Формат выходного файла

В выходной файл выведите одно число: количество путей, которые длиннее кратчайшего ровно на две секунды. Если парк устроен так, что невозможно добраться от входа до выхода, то выведите ноль.

Примеры тестов

6 9
.........
..######X
..#......
.E..####.
..##...#.
.....#...

15

Задача C. Банк ≡

Условие

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

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

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

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

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

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

Формат входного файла

В первой строке заданы два целых числа n и m (1 ≤ n ≤ 100 000, 1 ≤ m ≤ 10) — число гномов и сотрудников, соответственно. Далее, в n строках задано по три целых числа t_i, a_i и b_i (1 ≤ t_i, a_i, b_i ≤ 10⁹) — время прихода i-го гнома, сколько минут i-й гном должен провести у сотрудника банка и сколько минут он должен провести в офисе главного бухгалтера. Известно, что гномы заданы в порядке прихода в банк, то есть для любой пары i < j выполняется t_i ≤ t_j,

Формат выходного файла

Выведите n целых чисел, i-е число должно быть равно числу минут после открытия, когда i-й гном покинет банк.

Примеры тестов

4 2
1 3 3
1 2 2
2 2 1
2 1 4

8
5
9
13

Задача D. Взлом шифра ≡

Условие

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

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

Более формально: предположим, что Алан нажал на кнопки k раз. Пусть a_i (1 ≤ i ≤ k) — номер кнопки, которую Алан нажал i по счету, а b₁, b₂, …, b_n — секретная перестановка. Тогда замок открывается, если существует такое число x (1 ≤ x ≤ k − n + 1), что b₁ = a_x, b₂ = a_x+1, …, b_n = a_x+n−1.

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

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

Формат входного файла

В единственной строке входного файла находится целое число n (1 ≤ n ≤ 9) — количество кнопок на кодовом замке.

Формат выходного файла

В первой строке выходного файла выведите число k (0 ≤ k ≤ 2 n!) — длину универсальной последовательности. Во второй строке выведите k целых чисел a_i, разделенных пробелами (1 ≤ a_i ≤ n) — порядок, в котором следует нажимать кнопки. Обратите внимание, что достаточно вывести любую последовательность длины не более 2 n!, минимизировать длину не нужно. Гарантируется, что такая последовательность существует для любого n.

Примеры тестов

2

3
1 2 1

3

10
1 2 3 1 3 2 1 3 1 2

Задача E. Супрематизм ≡

Условие

Недавно на уроках ИЗО Казимиру рассказали о различных направлениях искусства. Больше всего его впечатлил супрематизм, и он решил нарисовать свою первую картину в этом стиле.

Казимир помнил, что в супрематизме картина состоит из простых фигур, поэтому, сначала он нарисовал прямоугольник n × m, составленный из разноцветных квадратов 1 × 1. После критического переосмысления своего творения, Казимир пришел к выводу, что получившаяся картина слишком сложна, и не все смогут понять его задумку. Второго холста у него не было, и он решил исправлять эту картину. На достаточно простой картине, по мнению Казимира, должен присутствовать всего один цвет.

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

Помогите Казимиру определить, cможет ли он с помощью этих операций исправить свою картину и сделать ее достаточно простой.

Формат входного файла

В первой строке заданы два числа n и m (1 ≤ n, m ≤ 300) — размеры картины. Далее, в n~строках задано по m чисел c_i,j (1 ≤ c_i,j ≤ 1 000 000) — цвета квадратов, из которых составлена картина. Гарантируется, что на картине представлено хотя бы два цвета.

Формат выходного файла

Если Казимиру не удастся сделать картину достаточно простой, выведите Poor Kazimir.

Иначе, выведите в первой строке k — количество действий, которое нужно сделать Казимиру. Действия могут быть двух видов:

• R r — перекрасить строку r (1 ≤ r ≤ n).
• C c — перекрасить столбец c (1 ≤ c ≤ m).

Разрешается сделать не более 1000 действий.

Примеры тестов

3 3
1 1 2
2 1 1
2 2 2

5
R 1
R 2
C 1
C 2
C 3

3 3
1 1 2
2 1 1
2 2 2

4
C 1
C 3
R 1
R 2

2 2
1 2
3 4

Poor Kazimir