SNTP

Комфортабельные коровы

Пастбище Фермера Юрика может рассматриваться как огромная 2D-решётка ячеек (шахматная доска). Изначально пастбище пустое.

Фермер Юрик добавит N (\(1<=N<=10^5\)) коров на пастбище одну за другой. i-ая корова займёт ячейку (xi,yi), которая отличается от ячеек, занятых всеми другими коровами (\(0<=x_i,y_i<=1000\)).

Корова называется "комфортабельной", если она имеет ровно трёх соседей по горизонтали и вертикали. Комфортабельные коровы дают меньше молока, поэтому Фермер Юрик хочет добавлять коров пока нет комфортабельных (включая ту которую он добавит). Заметим, что добавляемые коровы не обязательно должны иметь координаты x и y в интервале \(0…1000\).

Для каждого i в интервале \(1…N\), выведите минимальное количество коров, которое он должен добавить, чтобы не осталось комфортабельных коров, если считать, что на пастбище находятся только коровы \(1…i\).

Примеры

Выбор конфет

Скоро у Гарри Поттера день рождения! Гермиона хочет приготовить для него необычный подарок. Она хочет подарить Гарри набор из n волшебных конфет. Каждая конфета характеризуется её вкусом — целым числом t_i . Удовольствие , которое получит Гарри от набора конфет — это сумма вкусов всех конфет в этом наборе. Обратите внимание, что вкусы конфет, как и удовольствие Гарри, не обязательно должны быть положительными.

У Гермионы есть огромная коробка с конфетами, в которой для каждого целого числа t от - 10⁹ до 10⁹ лежит ровно одна конфета со вкусом t . Гермиона хочет взять из этой коробки n конфет, из которых будет состоять набор для Гарри.

Гермиона хочет, чтобы Гарри получил от подаренного ему набора конфет удовольствие, в точности равное целому числу s . Помогите ей выбрать подходящий набор или определите, что это невозможно.

Входные данные
Первая строка входных данных содержит единственное целое число n ( 1 ≤ n ≤ 100 ) — количество конфет, которое хочет Гермиона положить в набор. Вторая строка входных данных содержит единственное целое число s ( - 10⁹ ≤ s ≤ 10⁹ ) — удовольствие, которое должен получить Гарри от набора.

Выходные данные
Если составить желаемый набор из имеющихся у Гермионы конфет невозможно, выведите « NO ». Иначе, в первой строке выведите « YES », а во второй строке в произвольном порядке n чисел — вкусы конфет в искомом наборе. Если правильных ответов несколько, выведите любой из них.

Примеры

Карты на троих

Антонин, Бальбин и Цезарь играют в игру "Карты на троих", алгоритм которой следующий:
- сначала у каждого из трех игроков есть колода, состоящая из некоторого количества карт. На каждой карточке написана буква a, b или c. Порядок карт в колодах не может быть изменен;
- игроки ходят по очереди. Антонин ходит первым;
- если в колоде текущего игрока есть хотя бы одна карта, ему необходимо сбросить верхнюю карту в колоде;
- следующий ход переходит к игроку, имя которого начинается с буквы на сброшенной карте (a - Антонин, b - Бальбин, c - Цезарь);
- если колода текущего игрока пуста, игра заканчивается, и текущий игрок выигрывает игру.
Вам выдаются начальные колоды игроков (Sa, Sb, Sc). Состояние колоды Антонина записано в строке Sa, где i-й (\(1<=i<=len(S_a)\)) символ это буква в i-й карты в колоде. Строка Бальбина (Sb) и строка Цезаря (Sс) описываются таким же образом. 
Определите победителя в игре.

Формат входных данных
На вход подаются три ненулевых строки Sa, Sb и Sc, каждая с новой строки. Длина каждой строки не более 100 символов. Каждая строка состоит только из букв a, b или c.

Формат выходных данных
Если выиграл Антонин. то выведите букву A, если Бальбин - букву B, если Цезарь - букву C.

Примечание 
В первом тестовом примере игра будет развиваться следующим образом:
Антонин сбрасывает верхнюю карту своей колоды, a. Антонин делает следующий ход.
Антонин сбрасывает верхнюю карту своей колоды, с. Цезарь следующий.
Цезарь сбрасывает верхнюю карту своей колоды, с. Цезарь следующий.
Цезарь сбрасывает верхнюю карту своей колоды: a. Антонин делает следующий ход.
Антонин сбрасывает верхнюю карту своей колоды: a. Антонин делает следующий ход.
Колода Антонина пуста. Игра заканчивается, и Антонин выигрывает игру.

Делимость

Сегодня в школе на уроке математики проходят делимость. Чтобы продемонстрировать свойства делимости, учитель выписал на доске все целые числа от 1 до
N в несколько групп, при этом если одно число делится на другое, то они обязательно оказались в разных группах. Например, если взять N = 10, то получится 4 группы.

• Первая группа: 1.
• Вторая группа: 2, 7, 9.
• Третья группа: 3, 4, 10.
• Четвёртая группа: 5, 6, 8.

Примеры

Голосование

Коротышки решили взять в полет на Луну либо Незнайку либо Пончика. Не сумев договориться, они решили проголосовать. Незнайка и Пончик наблюдают краткий отчет о голосовании. Коротышки показывают Незнайке и Пончику соотношение текущего количества голосов, полученных Незнайкой и Пончиком, но не фактическое количество голосов. Незнайка и Пончик посмотрели отчет N раз, и когда они смотрели его в i-й (1<=i<=N) раз, соотношение было Pi:Ni. Известно, что Незнайка и Пончик имели хотя бы один голос, когда впервые увидели отчет. Найдите минимально возможное общее количество голосов, полученных Незнайкой и Пончиком, когда они проверили отчет в N-й раз. Можно предположить, что количество голосов, полученных Незнайкой и Пончиком, никогда не уменьшается.

Входные данные
В первой строке задается целое число N (1<=N<=1000). В следующих N строках записано по 2 числа Pi и Ni (1<=P_i,N_i<=1000). Pi и Ni - взаимно простые числа. 

Выходные данные
Выведите минимально возможное общее количество голосов. Гарантируется, что правильный ответ - не более 10¹⁸.
 

Примеры

Лягушки

Три лягушки сидят на числовой прямой в трёх различных точках с целочисленными координатами a, b, c. Лягушки боятся отступать слишком далеко друг от друга, поэтому прыгать может только одна из крайних лягушек (такая, что слева или справа от нее нет других лягушек) и только в целочисленную точку между двумя другими лягушками, если такая есть. Заметим, что в некоторых положениях ни одна из лягушек прыгнуть не может, назовем их стабильными .

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

В трёх строках заданы три различных целых числа - a, b, c (1 <= a, b, c <= 10¹⁸), исходные позиции лягушек.

Обратите внимание, что входные данные могут быть больше, чем возможное значение 32-битной целочисленной переменной, поэтому необходимо использовать 64-битные целочисленные типы данных (тип int64 в языке Pascal, тип long long в C и C++, тип long в Java и C#). Язык Python будет корректно работать и с типом int.

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

В первом примере из условия лягушка с позиции 4 может прыгнуть на позицию 2 и образовать стабильное положение (1,2,3). Можно показать, что больше одного прыжка они сделать не смогут.

Во втором тесте из условия лягушка с позиции 1 может прыгнуть на позицию 4, а затем лягушка с позиции 10 может прыгнуть на позицию 3, тем самым придя в стабильное положение (2,3,4) за два прыжка. Можно показать, что больше 7 прыжков по описанным правилам лягушки сделать не могли.

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

В четвёртом тесте из условия лягушка с позиции 1 может прыгнуть на позицию 4, а затем лягушка с позиции 5 может прыгнуть на позицию 3, тем самым придя в положение (2,3,4) за два прыжка. Можно показать, что больше двух прыжков лягушки сделать не могли.

Примеры

1
3
4

1
1

1
10
2

2
7

1
2
3

0
0

2
1
5

2
2

Не летное положение

Три скворца сидят на ветке дерева. Ветку дерева будем считать числовой прямой. С учетом этого, можно сказать, что скворцы сидят в трёх разных точках с целочисленными координатами a, b, c. Когда скорцам становится скучно, один из крайних скворцов перелетает на другое место (скворец считается крайним, если слева или справа нет другого скворца). Причем, из-за того, что скворцы не хотят улетать друг от друга слишком далеко, скворец, который решил сменить положение, перелетает только в целочисленную точку между двумя другими скворцами, если такая есть. Скворцы могут менять свое положение до тех пор пока их положение не станет "не летным". "Не летным" называется положение, при котором ни один из скорцов не может перелететь и сесть между двумя другими в целочисленную точку. 

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

В трёх строках заданы три различных целых числа - a, b, c (1 <= a, b, c <= 10¹⁸), исходные позиции скворцов.

Выходные данные

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

Примеры

1
3
4

1
1

1
10
2

2
7

1
2
3

0
0

2
1
5

2
2

Auxiliary Project

Anna has just finished her course project. She has a lot of seven-segment LED displays as leftovers and a small power source. Each display consumes power proportionally to the number of lit segments, e.g. ‘9’ consumes twice more power than ‘7’.


Anna wonders what is the maximum possible sum of digits she is able to achieve, if her power source is able to light n segments, and she wants to light exactly n segments.
Input
The single line of the input contains one integer n — the number of segments that should be lit (2 ≤ n ≤ 10⁶ ).
Output
Output a single integer — the maximum possible sum of digits that can be displayed simultaneously.

ПТИЦЫ

Всеволод Юрьевич устроился работать охранником на склад. Работа монотонная, и от скуки Всеволод Юрьевич считает ворон и других птиц, пролетающих мимо будки охраны. За годы работы он обнаружил следующую закономерность. Вороны летают поодиночке, начиная с 8:00 утра с периодичностью P1 минут, а после 8:00 вечера летать перестают. Утки пролетают стайками по N штук, начиная с 10:00 утра, с периодичностью P2 минут и перестают летать после 5:00 вечера. Голуби летают поодиночке с 7:00 утра до 8:00 вечера с периодичностью P3 минут. Три раза в день Всеволоду Юрьевичу приходится отвлечься от своего занятия ровно на полтора часа, чтобы принять на склад товар. Приемка начинается ровно в 11:00, 15:00 и 17:00. Сколько птиц (M) Всеволод Юрьевич насчитает за смену, если смена начинается в 6:00 утра и заканчивается в 6:00 утра на следующий день?

Во всех временных интервалах левый конец входит в него, а правый - нет. Например, одна из приемок начинается в 11:00 и Всеволод Юрьевич не считает птиц пролетающих в моменты с 11:00 до 12:29 включительно, а птиц, пролетающих в 12:30 - считает.

Формат входных данных
В строке указываются 4 целых положительных числа не превышающих 10000 каждое: P1, P2, N, P3, разделенные пробелом.
Формат выходных данных
В единственной строке указывается целое число M – количество птиц, которых Всеволод Юрьевич насчитает за смену при указанных условиях входа.
 

Помогаем природе

Участникам, использующим язык Python3, рекомендуется отправлять решения на проверку с использованием интерпретатора PyPy3.

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

Возле тропинки растут \(n\) деревьев, текущие уровни влажности которых заданы массивом \(a_1, a_2, \dots, a_n\). Леон научился трем способностям, которые помогут ему осушать и поливать почву.

• Он может выбрать позицию \(i\) и уменьшить уровень влажности деревьев \(1, 2, \dots, i\) на \(1\).

• Он может выбрать позицию \(i\) и уменьшить уровень влажности деревьев \(i, i + 1, \dots, n\) на \(1\).

• Увеличить уровень влажности всех деревьев на \(1\).

Леон хочет узнать минимальное число действий, которое необходимо совершить, чтобы каждое дерево имело уровень влажности равный \(0\).

Формат входных данных
В первой строке вводится одно целое число \(n\) (\(1 \leq n \leq 200\,000\)).

Во второй строке вводятся \(n\) целых чисел \(a_1, a_2 \ldots a_n\) (\(-10^9 \leq a_i \leq 10^9\)) — изначальные уровни влажности деревьев.

Формат выходных данных
Выведите одно целое число — минимальное число действий.

В первом примере из условия достаточно \(2\) раза применить операцию прибавления \(1\) ко всему массиву.

Во втором примере из условия можно \(4\) раза применить операцию вычитания на префиксе длины \(3\) и получить массив \(6, 0, 3\).

После этого \(6\) раз применить операцию вычитания на префиксе длины \(1\) и \(3\) раза операцию вычитания на суффиксе длины \(1\). Итого, количество действий составит \(4 + 6 + 3 = 13\). Можно показать, что меньшим количеством действий обойтись нельзя, поэтому \(13\) — это ответ.

Олег и двоичные последовательности

Олег очень любит двоичные последовательности — последовательности из нулей и единиц. Совсем недавно он написал в тетради очередную двоичную последовательность из n элементов.
Для выписанной последовательности Олег посчитал Z-функцию.

Z-функцией последовательности s₁, . . . , s_n называется массив z[1..n], в котором:

• z[1] = 0;
• Если i > 1, то z[i] равно длине наибольшего общего префикса последовательности s и суффикса последовательности s, начинающегося с i-й позиции. Иначе говоря, z[i] равно максимальному k, такому что s₁ = s_i , s₂ = s_i+1, . . . , s_k = s_i+k−1.

Например, для последовательности s = h0, 0, 1, 1, 0, 0, 1i Z-функция следующая: z = h0, 1, 0, 0, 3, 1, 0i.
Записав в тетради последовательность и ее Z-функцию, Олег лег спать. Пока он спал, его младший брат Егор прокрался в комнату и закрасил фломастером последовательность и некоторые значения Z-функции. Проснувшись, Олег заинтересовался, сколько различных двоичных последовательностей он мог вечером написать в тетради, чтобы незакрашенные значения Z-функции были правильными.

Найдите число искомых последовательностей и выведите его по модулю 10⁹ + 7. Заметьте, что Олег мог и ошибиться при вычислении Z-функции, в этом случае ни одна последовательность не подходит и ответ равен 0.
Формат входных данных
В первой строке входного файла находится целое число n — длина исходной двоичной последовательности (1 ≤ n ≤ 1000). Во второй строке входного файла находятся n целых чисел z[1], . . . , z[n], где z[i] — значение Z-функции в позиции i, или −1, если значение в i-й позиции было закрашено (−1 ≤ z[i] ≤ n).

Формат выходных данных
В выходной файл выведите единственное число — остаток от деления числа подходящих двоичных последовательностей на число 10⁹ + 7.
 

Призы

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

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

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

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

Помогите организаторам — посчитайте, сколько раз надпись «ВКОШП» коснется пола при оптимальном перекатывании куба с футболками.

Формат входных данных
В первой строке задано два числа n и m (1 ≤ n, m ≤ 10⁹ ) — размеры комнаты в метрах.

Формат выходных данных
Выведите одно число — сколько раз надпись «ВКОШП» окажется на нижней грани при оптимальном перемещении ящика.
 

Ряд чисел

Легенда гласит, что Карл Фридрих Гаусс, учась в школе, смог быстро посчитать сумму целых чисел от 1 до 100, заметив, что 1 + 100 = 2 + 99 = … = 50 + 51. Теперь решите задачу посложнее: можно ли перед каждым из чисел от 1 до N расставить знаки «+» или «–» так, чтобы сумма получившихся чисел была равна 0? Например, для N = 3 сумма –1 –2 +3 будет равна 0, а для N = 2 этого сделать нельзя. Программа получает на вход целое неотрицательное число N, не превосходящее 10⁵.
Программа должна вывести последовательность из N символов «+» или «–», соответствующих знакам, которые нужно расставить перед числами от 1 до N так, чтобы сумма получившихся чисел была равна 0. Если задача имеет несколько решений, нужно вывести один (лобой) ответ. Если задача не имеет решения для данного N, нужно вывести
одно слово «IMPOSSIBLE».
 

Пирожные

Для праздничного чаепития необходимо купить n пирожных. В магазине продается всего два вида пирожных, причем пирожных одного вида осталось a штук, а пирожных другого вида осталось b штук. Пирожные одного вида считаются одинаковыми. Сколькими способами можно купить ровно n пирожных?

Формат входных данных
В первой строке входных данных записано число n — количество пирожных, которое нужно купить, во второй и третьей строке записаны числа a и b — количество пирожных каждого из двух видов, которые есть в магазине. Все числа — целые, от 1 до 100.

Формат выходных данных
Программа должна вывести одно целое число — количество различных способов купить n пирожных.
 

Весы

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

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

Формат входных данных
Входные данные содержат четыре строки, каждая из них содержит вес одной из гирь — натуральное число, не превышающее \(100\).

Формат выходных данных
Если уравновесить весы невозможно, выведите единственное число \(-1\).

Иначе выведите две строки. На первой строке выведите веса гирь, которые необходимо разместить на левой чаше весов. На второй строке выведите веса гирь, которые необходимо разместить на правой чаше весов.

Если есть несколько способов уравновесить весы, можно вывести любой из них.

Lights Out

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

Амбар описывается простым (несамопересекающимся) многоугольником с целочисленными вершинами \((x_1, y_1) \ldots (x_n, y_n)\) перечисленными в порядке обхода по часовой стрелке. Его рёбра составляются чередующимися горизонтальными (параллельными оси Х) и вертикальными (параллельными оси Y) отрезками. Первое ребро может быть как горизонтальным, так и вертикальным. Выход расположен в точке \((x_1, y_1)\). Беси начинает в некоторой вершине \((x_i, y_i)\) для \(i > 1\). Она идёт только по периметру амбара, по часовой стрелке или против часовой стрелки, потенциально изменяя направления движения, в любой вершине. Её цель - пройти минимальное расстояние и добраться до выхода. Это довольно просто, когда свет включён - просто выбрать между движением по часовой стрелке и движением против часовой стрелки.

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

Помогите Беси определить минимальное количество, на которое возрастёт её путь в худшем случае при движении в темноте, по сравнению с движением при свете, полагая, что она движется оптимально в каждом случае. Оптимальная стратегия - такая, которая минимизирует увеличение расстояния в худшем случае.

Fence Painting

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

Если мы рассмотрим изгородь ФД как одномерную числовую прямую, то ФД закрашивает интервал между \(x=a\) and \(x=b\). Например, если \(a=3\) and \(b=5\), то ФД закрашивает интервал длиной 2. Беси, не понимая команды ФД, закрашивает интервал от \(x=c\) to \(x=d\), который может частично или полностью перекрываться с интервалом ФД. Пожалуйста, определите общую длину изгороди которую покрасят ФД и Беси.

Reverse Engineering

У Эльзы есть программа, которая получает на ввод массив из \(N\) (\(1\le N\le 100\)) переменных \(b[0],\dots,b[N-1]\), каждая из которых равна 0 или 1 и возвращает результат применяя последовательность операторов if / else if / else, указанную на вводе. Каждый оператор проверяет значение не более одной переменной и возвращает 0 или 1. Примером такой программы может быть:

if (b[1] == 1) return 1;
else if (b[0] == 0) return 0;
else return 1;

Например, если ввод в эту программу есть "10" (то есть, \(b[0] = 1\) и \(b[1] = 0\)), тогда вывод должен быть 1

Эльза должна сказать правильный ответ для \(M\) (\(1\le M\le 100\)) различных вводов. Бесси сейчас пытается сделать "реверс инжиниринг" для программы Эльзы. К несчастью, Эльза может и солгать - то есть не существует программы вида указанного выше, которая выведет ответы как сказала Эльза.

Для каждого из \(T\) (\(1\le T\le 10\)) подтестов определит, лгала Эльза или нет.

Sleepy Cow Herding

Три лучшие коровы Фермера Джона Беси, Эльза и Милдред всегда уходят далеко от фермы. Помогите ФД "сгрудить их в стадо".

Главное поле фермы можно представить в виде числовой прямой, и каждая корова находится в целочисленной координате. Все три координаты различны. ФД хочет переместить их так, чтобы они заняли последовательные координаты (например, 6,7,8).

В любой момент времени ФД может заставить корову двигаться только, если она находится в "конечной" точке (минимальной или максимальной позиции среди всех коров). Когда он перемещает корову, он говорит ей двигаться на любую незанятую целую позицию, так чтобы она перестала быть в конечной точке. С течением времени такие передвижения обеспечивают сближение коров.

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

65823

Аспирант Шлёпов собирается провести чемпионат вуза по шахматам. Так как игроков в вузе много, у сообщества есть свой рейтинг ELO. Шлёпов собирается разделить игроков на основании этого рейтинга на две лиги. В высшей лиге должно играть не менее трети игроков, но при этом наименьшее возможное количество; отбор в лигу идёт на основании ELO. Двух игроков с одинаковым ELO распределять в разные лиги нельзя. Высшая лига на турнире должна быть обязательно. Определите, начиная с какого ELO, игроки попадают в высшую лигу.

Формат входных данных
На вход программе в первой строке подаётся натуральное число N (N ≤ 1000) – количество игроков. Далее в N строках идёт по одному натуральному числу k_i – рейтинг ELO игрока номер i (1 ≤ k_i ≤ 2500).
Формат выходных данных
Выведите одно целое число – ELO, начиная с которого, игроки попадают в высшую лигу. Если в высшей лиге окажется весь турнир, надо вывести наименьший ELO среди заявленных игроков.

Пояснение
Всего пять игроков, значит, в высшей лиге должно быть не меньшедвух. 1750 – точно в высшей лиге. 1600 надо брать в высшую лигу, но их два. Значит, оба идутв высшую лигу, после чего она набрана.
 

Порядок во всём

Вася — очень порядочный мальчик, он любит порядок во всём.

У него в тетради есть столбик натуральных чисел, и он хочет изменить его так, чтобы числа шли по порядку, то есть по неубыванию. При этом Вася, естественно, ничего не хочет зачёркивать, поэтому единственное, что ему остаётся — это дописать цифры в конец некоторых чисел.

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

Формат входных данных
Первая строка входных данных содержит целое число \(n\) (\(2 \le n \le 3 \cdot 10^{5}\)) — количество чисел в тетрадке у Васи.

Следующие \(n\) строк содержат \(n\) чисел, записанных в тетрадке, по одному в каждой строке. Все числа натуральные, не превосходящие \(10^9\).

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

Примечание

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

Во втором примере Васе можно приписать ко второму числу цифру 3, тогда числа станут равны 13, а значит, будут расположены по неубыванию. При этом 13 — это минимально возможное последнее число.

В третьем примере Вася может, например, получить числа 20, 25, 100. Возможны и другие варианты, но последнее число при любом способе дописывания цифр получится не меньше 100.

Прямоугольный забег

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

Центральная площадь Зожбурга представляет собой прямоугольник, разделенный на одинаковые единичные квадраты. Строки пронумерованы сверху вниз с единицы, столбцы слева направо с единицы. Каждый квадрат площади имеет координаты \(r\) и \(c\) — номер строки и столбца, соответственно.

На площади находится прямоугольный газон со сторонами, параллельными сторонам площади. Координаты левого верхнего углового квадрата газона \((R_L, C_L)\), координаты правого нижнего углового квадрата газона \((R_R, C_R)\). Вокруг газона оборудованы \(n\) дорожек для \(n\) бегунов. Дорожка \(i\) находится на расстоянии \(i\) от границы газона, на дорожке \(i\) находится бегун с номером \(i\). Бегун \(i\) стартует с квадрата с координатами \((r_i, c_i)\). Бегуны стартуют одновременно с одинаковой скоростью: через каждую секунду каждый спорстмен меняет текущий квадрат на своей дорожке на следующий квадрат на своей дорожке в направлении против часовой стрелки.

На прямоугольном газоне в квадрате \((R_p, C_p)\) стоит фотограф, цель которого — сделать красивую фотографию. Фотограф тестирует инновационную камеру с двойным объективом. Эта камера делает снимок одновременно в двух противоположных направлениях. Фотограф считает фотографию красивой, если все бегуны в момент, когда он делает снимок, находятся в одновременно в строке \(R_p\) или в стоблце \(C_p\). При этом благодаря инновационному свойству камеры они могут быть либо в одной строке с ним и справа и слева от него, либо в одном столбце с фотографом и выше и ниже него.

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

Формат входных данных
В первой строке входных данных находится число \(n\) (\(1 \le n \le 18\)) — количество бегунов. В следующей строке ввода даны шесть целых чисел \(R_L\), \(C_L\), \(R_R\), \(C_R\) (\(n + 1 \le R_L \le R_R \le 100 - n\), \(n + 1 \le C_L \le C_R \le 100 - n\)), \(R_p\) (\(R_L \le R_p \le R_R\)), \(C_p\) (\(C_L \le C_p \le C_R\)) — координаты левого верхнего квадрата газона, правого нижнего квадрата газона, координаты фотографа, соответственно. Гарантируется, что \(R_R - R_L + C_R - C_L\) делится на \(4\).

В следующих \(n\) строках даны два числа \(r_i\), \(c_i\) — стартовые координаты бегуна \(i\). Гарантируется, что стартовые координаты бегуна \(i\) находятся на дорожке \(i\), на каждой дорожке находится один бегун, дорожка \(i\) находится на расстоянии \(i\) от границы газона.

Формат выходных данных
Выведите единственное число \(t\) — через какое минимальное количество секунд \(t\) после старта забега фотограф сможет сделать красивую фотографию, или \(-1\), если фотографию сделать не получится.

Рисунок ко второму примеру.

Диалог компьютеров

Три компьютера соединены сетью. Один из них - сервер, два других - клиенты. На сервере есть несколько файлов. Полные имена файлов, состоящие из двух частей (имя и расширение), различны. Оба клиента знают полные имена всех файлов, находящихся на сервере. Сервер выбирает один из своих файлов и посылает его имя одному из клиентов, а расширение - второму.

Затем клиенты начинают общаться друг с другом, пытаясь определить, какой файл был выбран сервером (они хотят узнать полное имя файла). Однако клиенты вынуждены общаться очень ограниченным способом. Они по очереди посылают сообщения друг другу, но могут сказать только, что не знают полного имени файла. Если клиент не знает полного имени выбранного файла, он может послать другому клиенту сообщение, говорящее: "Я не знаю полного имени файла". Клиенты чередуются, посылая только это сообщение туда и обратно. Так продолжается до тех пор, пока один из клиентов не узнает полное имя файла, или они не решат закончить диалог. Клиент, получивший первую часть полного имени файла, всегда ждёт, что второй клиент пошлёт первое сообщение.

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

Входные данные
В первой строке находятся два целых числа, N и M, разделённые пробелом: N - число файлов на сервере, M - число сообщений, посланных клиентами, пытающимися определить полное имя файла.

Каждая из следующих N строк содержит одно полное имя файла. Полное имя файла дано в стиле, аналогичном формату 8.3 MS-DOS. Каждое полное имя представлено в форме имя.расширение, где и имя, и расширение состоит только из заглавных латинских букв и цифр. Имя всегда имеет от одного до восьми символов. Расширение имеет до трёх символов и может быть пусто. Если расширение пусто, разделяющая точка может быть опущена.

Каждое полное имя файла появляется во входном файле не более одного раза.

1 <= N <= 1000, 1 <= M <= 100.

Выходные данные
В первой строке выводится число файлов-кандидатов для данных набора файлов и числа сообщений между клиентами. Выводится 0, если файлы-кандидаты отсутствуют.

В следующих строках находятся полные имена файлов-кандидатов, каждое в отдельной строке. Они должны идти в том же порядке и в том же написании, что и во входном файле. Это означает, что, если разделяющая точка в названии конкретного файла была опущена во входном файле, то она должна быть опущена и в выводе, и наоборот. Файл нельзя упоминать более чем один раз.

Сложное уравнение

Решить в целых числах уравнение ( ax + b ) : ( cx + d ) = 0.

Входные данные
Вводятся 4 числа: a, b, c и d; c и d не равны нулю одновременно.

Выходные данные
Необходимо вывести все целочисленные решения, если их число конечно, “NO” (без кавычек), если целочисленных решений нет, и “INF” (без кавычек), если их бесконечно много.

Сломанный индикатор

У радиолюбителя Алексея есть девятисегментный жидкокристаллический индикатор, который может показывать цифры от \(0\) до \(9\) в виде цифр <<почтового индекса>> (см. рисунок):

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

Алексей уже выяснил, что индикатор всё ещё способен показать какие-то \(n\) цифр. Однако радиолюбитель не может проверить остальные цифры, равно как и каждый сегмент отдельно. Поэтому он просит вас помочь найти те цифры, которые гарантированно можно показать на этом индикаторе.

Формат входных данных
Первая строка входных данных содержит число \(n\) (\(1 \le n \le 10\)) — количество цифр, которые смог показать на индикаторе Алексей.

Следующие \(n\) строк содержат по одной цифре \(a_i\) (\(0 \le a_i \le 9\)) — сами цифры, которые Алексей смог показать. Гарантируется, что все \(a_i\) различны.

Формат выходных данных
Выведите элементы искомого множества в порядке возрастания, каждую цифру в отдельной строке.

Турнир ФХЛ

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

В этом году в финал вышли команды <<Капибары>> и <<Бурундучки>>. Петя и Вася очень любят хоккей, но во время турнира они были на сборах по информатике. Теперь они решили просмотреть все матчи финального турнира в записи, скачав их с официального сайта. Зайдя на сайт, они обнаружили, что в этом году финальный турнир ФХЛ состоял из \(k\) матчей. Скачав все видеозаписи, ребята начали их смотреть, но неожиданно поняли, что могут предсказать итог турнира, не досмотрев все матчи. Более того, они заметили, что про некоторые матчи они понимают, кто их выиграет, даже не начав смотреть запись.

Например, пусть \(n = 3\) и \(k = 4\). Петя и Вася сразу могут сделать вывод, что турнир закончится со счетом по матчам \(3:1\) или \(1:3\), ведь всего будет сыграно 4 игры. Пусть первый матч закончился победой команды <<Капибары>>, счет стал \(1:0\), второй матч также закончился победой команды <<Капибары>>, счет стал \(2:0\). Теперь ребята точно знают, что победителем турнира станет команда <<Капибары>>, ведь если бы турнир выиграла команда <<Бурундучки>>, то финальный счет был бы \(2:3\) и всего было бы сыграно 5 игр. Более того, команда <<Бурундучки>> гарантированно выиграет третий матч, иначе окончательный счет был бы \(3:0\), а команда <<Капибары>> "— четвертый матч.

По заданным \(n\), \(k\) и результатам игр определите, после какой игры Петя и Вася поймут, какая команда станет победителем турнира, а также про каждый матч определите, знают ли ребята победителя этого матча до того, как посмотрят его.

Формат входных данных
Первая строка ввода содержит два целых числа: \(n\) и \(k\) (\(1 \le n \le 100\), \(n \le k \le 2n-1\)). Вторая строка ввода содержит \(k\) целых чисел: \(i\)-е из них равно 1, если \(i\)-й матч выиграла команда <<Капибары>>, либо 2, если \(i\)-й матч выиграла команда <<Бурундучки>>.

Гарантируется, что по итогам турнира одна из команд выиграла ровно \(n\) матчей, причем ни одна из команд не выигрывает \(n\) матчей до того, как будут сыграны все \(k\) матчей, описанных во входных данных.

Формат выходных данных
Выведите две строки. Первая строка должна содержать одно число \(z\) (\(1 \le z \le k\)) "— номер матча, после которого ребята могут однозначно определить победителя турнира.

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

Ремонт кладовки

Дима купил кладовку размера \(X\times Y \times Z\), где \(X, Y, Z\) — это длина, ширина и высота в метрах соответственно. Но она оказалась без окон, без дверей и с голыми стенами. В магазине продается два типа обоев. В наличии имеется \(S_1\) квадратных метров обоев первого типа, стоимостью \(C_1\) рублей за квадратный метр, а второго типа — \(S_2\) квадратных метров стоимостью \(C_2\) рублей за квадратный метр.

Дима хочет сделать дверь размера \(A \times B\), где \(A\) — ширина, а \(B\) — высота, в одной из стен (обои на дверь клеить не надо). Также он хочет, чтобы на стенах, расположенных друг напротив друга, были наклеены одинаковые обои. То есть обе стены размером \(X \times Z\) должны быть оклеены одним типом обоев. Аналогично, обе стены размером \(Y \times Z\) также должны быть оклеены одним типом обоев. Определите, получится ли у него поклеить обои, и если получится, то какая минимальная сумма в рублях ему потребуется.

Формат входных данных
В первой строке вводится три целых числа \(X\), \(Y\) и \(Z\) (\(1 \leq X, Y, Z \leq 10\,000\)) — длина, ширина и высота комнаты.

Во второй строке вводится четыре целых числа \(S_1\), \(C_1\), \(S_2\) и \(C_2\) (\(1 \leq S_1, C_1, S_2, C_2 \leq 10^{8}\)) — количество квадратных метров обоев первого типа на складе, стоимость квадратного метра обоев первого типа, количество квадратных метров обоев второго типа и стоимость квадратного метра обоев второго типа.

В третьей строке вводится два числа \(A\) и \(B\) (\(1 \leq A, B \leq 10\,000\)) — ширина и высота двери.

Формат выходных данных
Определите, сможет ли Дима оклеить кладовку обоями. Если это невозможно, то выведите -1. Иначе выведите минимальную сумму в рублях, которую Дима потратит на покупку обоев.

Решения, верно работающие при \(X=Y=Z\), будут оцениваться не менее чем в 30 баллов.

Примечание
В первом примере Дима установит дверь в стену размером \(5 \times 10\) и наклеит первый вид обоев на все стены.

Во втором примере Дима установит дверь в стену \(5 \times 10\), наклеит первый вид обоев на стены \(6 \times 10\) и второй вид обоев на стены \(5 \times 10\).

В третьем примере высота двери слишком большая.

В четвертом примере суммарная площадь доступных обоев меньше, чем площадь стен.

Лягушка и кузнечик

В крайних клетках полоски шириной в одну клетку и длиной в N клеток сидят лягушка и кузнечик: лягушка в клетке № 1, кузнечик в клетке № N. Каждую секунду лягушка прыгает в сторону кузнечика, и одновременно кузнечик прыгает в сторону лягушки. Лягушка может прыгать только на две или на три клетки, кузнечик — только на одну или на две клетки. За какое наименьшее время они смогут оказаться в одной клетке?

Входные данные
Единственная строка входных данных содержит целое число N — длину клетчатой полосы (2 ≤ N ≤ 2 · 10⁹ ).
Выходные данные
Если лягушка и кузнечик могут оказаться в одной клетке, требуется вывести одно целое число — минимальное количество секунд, через которое они встретятся. Если они не смогут оказаться в одной клетке, требуется вывести число «-1» (без кавычек).
 

Примеры

Лекция по товароведению

Гена Букин приехал в Златоуст провести управленческую лекцию в обувном магазине. Зайдя в магазин, Гена увидел полнейший бардак: коробки обуви хаотично валялись в куче посреди зала.
Конечно же, его эта ситуация не устроила, и он решил, что нужно показать, как правильно расставлять коробки. Он заметил, что в магазине есть коробки только двух типов: красные имеют высоту x сантиметров, их a штук; синие имеют высоту y сантиметров, их b штук.
Гена хочет взять несколько коробок из кучи и составить из них башню. Однако из каких-то личных представлений об эстетике Гена не ставит две коробки одинакового цвета друг на друга, в башне он может только чередовать цвета.
Попробовав все возможные способы построения башни, Гена запомнил, сколько различных высот конструкции он смог получить. А сможете ли вы определить, сколько существует различных высот h > 0, что можно построить башню из коробок высотой h, удовлетворяя требованиям о чередовании цветов?
Входные данные
В единственной строке через пробел вводятся 4 целых числа x, y, a, b — высота красной коробки, высота синей коробки, количество красных коробок, количество синих коробок (1<= x,y,a,b <=10⁹).
Выходные данные
Выведите одно число — количество различных высот башен из коробок.
 

Примеры

Диадема Клеопатры

Аня — страстный любитель ювелирных изделий. Ее коллекция насчитывает множество бриллиантов, изумрудов и алмазов.

...Срочная новость! Бесценный змеиный рубин Клеопатры был украден!

Три дня назад мир потрясло сенсационное известие: исследовательская экспедиция обнаружила в одном из храмов, построенных во времена великой египетской императрицы Клеопатры, потайную комнату. В ней кроме бронзовой статуи императрицы обнаружилась поразительной красоты диадема, ранее считавшаяся бесследно утерянной! Ученые сообщили, что диадема увенчана алым a-каратным рубином в форме змеиной головы. Однако буквально пару часов назад поступила новость, что бесценное украшение было изувечено: кто-то пробрался в камеру хранения диадемы и вырезал из нее рубин! Полиция устанавливает круг подозреваемых...

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

Купив все N камней, Глеб тут же провел несколько пробных измерений, взвесив некоторые наборы из них, и отправил результаты Ане по электронной почте. Тем временем она проконсультировалась с известным исследователем старины Андрэ Шесто-Мерта по поводу украденной драгоценности и узнала, что по всем имеющимся историческим источникам рубин весил не a карат, как утверждали журналисты, а b карат!

Зная результаты взвешиваний Глеба, и учитывая, что все поддельные камни весят a карат, и только настоящий змеиный рубин может весить b карат, определите, какие из купленных камней могут на самом деле являться потерянной реликвией великой императрицы прошлого.

Входные данные
В первой строке находятся четыре целых числа N, a, b и K (1 ≤ N ≤ 200, 1 ≤ a, b ≤ 1 000 000, a ≠ b, 1 ≤ K ≤ 1 000).

Далее идут K строк, описывающих взвешивания, проведенные Глебом.

Первое число в i-ом описании — w_i (1 ≤ w_i ≤ 200 000 000), суммарный вес группы камней, участвовавших в i-ом взвешивании.

Второе число — m_i (1 ≤ m_i ≤ N) — количество камней, участвовавших в i-ом взвешивании.

Далее следуют m_i целых чисел, упорядоченных по возрастанию, — номера камней, участвовавших в i-ом взвешивании.

Выходные данные
Если среди купленных Глебом камней змеиного рубина точно нет, выведите строку "Fail" (без кавычек).

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

Если же Глеб в некоторый момент ошибся в расчетах, и присланная им информация о взвешиваниях не может соответствовать действительности, выведите строку "Impossible" (без кавычек).

Примеры

Лазерная пушка

У игрока в космической стрелялке есть очень мощная лазерная пушка. Но она неподвижна и может стрелять только в одном направлении. Игрок может расставить на игровом поле двусторонние зеркала, меняющие ход луча, чтобы поражать врагов. Введём декартову систему координат с центром, где расположена пушка, то есть пушка имеет координаты (0; 0). Пушка стреляет в направлении точки (1; 1). Игрок может поставить зеркала в точках с целочисленными координатами. Зеркала могут быть горизонтальными или вертикальными, попадание луча в зеркало меняет траекторию луча по законам отражения света. Некоторые возможные варианты отражения луча от зеркала изображены на рисунке.

Вам необходимо расставить минимальное количество зеркал так, чтобы лазерный луч поразил цель.

Входные данные
Программа получает на вход два целых числа X и Y , не превосходящих по модулю 10000, записанные в разных строках — координаты цели. Точка (X; Y) не совпадает с началом координат.

Выходные данные
Программа должна вывести в первой строке число N — необходимое количество зеркал. Следующие N строк должны содержать информацию о каждом зеркале. В i-й строке должны быть записаны через пробелы два целых числа xi и yi и один символ ti , обозначающие координаты (xi ; yi) точки, в которых установлено i-е зеркало, и тип этого зеркала ti . Если ti является символом «V», то i-е зеркало размещено вертикально, если же ti является символом «H», то зеркало размещено горизонтально. Например, строка «-2 5 H» обозначает горизонтальное зеркало в точке (−2; 5). Зеркала можно выводить в любом порядке. Зеркало нельзя размещать в точке (0; 0), также нельзя размещать два зеркала в одной точке. Значения xi и yi не должны по модулю превосходить 100 000. Также, разумеется, нельзя допустить, чтобы отражённый луч попал в пушку. Если вариантов ответа несколько, выведите любой из них. Если поразить цель в соответствии с условиями задачи невозможно, программа должна вывести одно число «-1». Если для поражения цели зеркала не нужны, программа должна вывести одно число «0»
 

Примеры

№	Входные данные	Выходные данные	Пояснение
1	5 1	1 3 3 H

Хорошая сетка

Имеется сетка из N строк и N столбцов квадратов. Пусть (i, j) индексы клетки, которая расположена в i-й строке сверху и j-м столбце слева. Эти клетки должны быть окрашены в один из цветов C от цвета 1 до цвета C. Первоначально (i, j) окрашен в цвет ci,j. Назовем сетку хорошей, когда выполняются следующие условия для всех i, j, x, y, удовлетворяющих \(1<=i,j,x,y<=N\):
- если \((i+j)\%3=(x+y)\%3\), цвет (i, j) и цвет (x, y) совпадают;
- если \((i+j)\%3\neq(x+y)\%3\), цвет (i, j) и цвет (x, y) различны.
Здесь \(X \% Y \) представляет X по модулю Y.
Мы перекрасим ноль или более клеток, чтобы сетка была хорошей сеткой.
Неправильной клеткой назовем клетку, которая имела цвет X до перерисовки и Y после перекраски (DX,Y).
Найдите минимально возможную сумму всех неправильных клеток.

Входные данные
В первой строке задаются два целых числа N и C. В следующих C строках задаются по C значений Di,j. В последних N строках записаны N чисел в каждой строке - ci,j.

Выходные данные
Выведите минимально возможную сумму всех неправильных клеток
 

Примеры

Конфеты

На столе стоят три вазы с конфетами. В левой вазе лежат A конфет, в средней вазе лежат B конфет, в правой вазе лежат C конфет. Лена съедает одну конфету из левой вазы,
затем – одну конфету из средней вазы, затем из правой, средней, левой, средней, правой, средней и т. д. (слева направо, затем налево, опять направо и т.д.)
Если Лена хочет взять конфету из какой-то вазы, а конфет там нет, она расстраивается и идёт спать. Определите, сколько конфет съест Лена.
Программа получает на вход три целых неотрицательных числа A, B, C – количество конфет в левой, средней, правой вазе. Сумма трёх данных чисел не превосходит 2×10⁹.
 

Примеры

Робот

Некоторый заводской цех представляет собой прямоугольник размером M на N метров (1 <= M, N <= 30). Инженер-конструктор Петя создал робота, который  может перемещаться по территории цеха и выполнять некоторую общественно-полезную работу. Робот может перемещаться только по плитам, размером 1 на 1 метр, которыми выложен пол цеха, и только параллельно осям координат.

У робота есть 4 регистра состояния, A, B, C и D. Каждый регистр может принимать одно из двух значений - TRUE или FALSE. На некоторых плитах цеха стоят радио-триггеры, которые переключают состояние каких-то регистров робота. Также на некоторых других плитах могут находиться радиомаяки, которые в зависимости от истинности формулы, соответствующей данному маяку, заставляют робота повернуть на 90 градусов налево или направо. В случае истинности совершается поворот направо.

Спецслужбы заинтересовались разработкой Пети, и решили проверить пригодность робота для работ в условиях радиации, под водой, в кратерах вулканов, на других планетах и много где еще. Для испытаний из цеха было вынесено все оборудование, поставлено некоторое количество радиомаяков и триггеров. Начиная с некоторой пустой плиты X₀, Y₀ под начальным углом A0 (0,90,180 или 270 градусов, отсчитывая от направления вверх по часовой стрелке) был запущен робот. Изначально состояния всех регистров робота - FALSE.

Аккумуляторных батарей робота хватит на K (0 < K <= 10⁹) перемещений на соседнюю плиту. После этого он остановится. Кроме того, возможен такой вариант, что Петя неправильно расставил триггеры и маяки, поэтому на некотором шаге робот врежется в стену цеха. Необходимо определить, уцелеет ли робот после испытаний и на какой клетке он остановится в случае положительного ответа на первый вопрос.

Оси координат направлены из левого верхнего угла - точки (1,1) - соответственно вправо и вниз. M - размер цеха по горизонтали, а N - по вертикали. Количество триггеров - P - не превосходит 10000, а радиомаяков - Q - 25.

Входные данные
На первой строке входного файла записаны 8 чисел - M,N,P,Q,K,X0,Y0,A0. Далее на Р строках записаны триггеры в формате "X Y R", где R - название регистра. Далее на Q строках записаны радиомаяки в формате "X Y F", где F - булева функция от переменных A..D длиной не более 250 символов, заданная корректной формулой, причем:

-    A, B, C, D, TRUE, FALSE – корректные формулы
-    Если F – корректная формула, то «(F)» и «NOT F» – корректные формулы 
-    Если F и G – корректные формулы, то «F AND G», «F OR G» и «F XOR G» – корректные формулы 
-    Операция NOT имеет наивысший приоритет, остальные операции имеют одинаковые приоритеты и выполняются слева направо, т.е. A AND NOT B OR C XOR D эквивалентно (((A AND (NOT B)) OR C) XOR D)
-    регистр букв не имеет значения
-    корректная формула не содержит лишних пробелов
Выходные данные
В случае успешного исхода вывести координаты плиты, где остановится робот. В случае краха эксперимента вывести в выходной файл единственное число «-1».

Примеры

Двухтуровая олимпиада

Как известно, личная олимпиада по информатике проходит в два тура. На каждом из туров участники получают какие-то баллы, при этом итоговый балл определяется как сумма полученных баллов. Известны баллы, которые каждый участник получил на каждом из туров. Жюри хочет фальсифицировать итоги олимпиады так, чтобы победил «нужный» участник.

При этом жюри может делать следующие «подтасовки» (можно делать несколько «подтасовок» применительно как к одному и тому же, так и к разным турам):

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

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

Входные данные
Во входном файле записано сначала число участников N (1 ≤ N ≤ 1000), затем N пар чисел — результаты каждого участника за 1-й и за 2-й туры (результат участника за тур — это вещественное число от 0 до 100) не более, чем с 3 знаками после десятичной точки.

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

Примеры

Операнды

Алина выписала на доске \(n + 1\) цифру, каждая из которых от \(1\) до \(9\). Даша поставила между каждой парой соседних цифр знак одной из арифметических операций <<+>>, <<->>, <<*>> и <</>> (плюс, минус, умножить, целочисленное деление). Затем девочки отправились в столовую на обед.

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

Они просят вас зная последовательность знаков, расставить цифры от \(1\) до \(9\) между ними так, чтобы итоговый результат был максимальным.

Формат входных данных
В первой строке дано число \(n\), число знаков, которые написала Даша (\(1 \le n \le 1000\)).

Во второй строке находится \(n\) знаков арифметических операций <<+>>, <<->>, <<*>> и <</>> (без кавычек).

Формат выходных данных
Выведите в единственной строке последовательность из \(n + 1\) цифры, таким образом, чтобы при расстановке между ними знаков итоговый результат был максимальным.

Если возможных решений несколько, разрешается вывести любое.

В автобусе

Кедор и Гихаил

Тяжелая, вариант-1

На уроке информатики учитель рассказал Васе про новый вид строк — минимально-символьные строки. Строка называется минимально-символьной, если символ, который встречается в ней минимальное количество раз, единственен. Например, строка "abacaba" — минимально-символьная, потому что единственный символ, который встречается минимальное количество раз в ней — 'c'. В то же время строка "cababac" — не минимально-символьная, потому что символы 'b' и 'c' встречаются в ней минимальное количество раз, то есть не являются единственными.

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

Входные данные

В единственной строке входного файла input.txt записана строка s, характеризующая набор символов. Ее длина не превосходит 100.

Выходные данные

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

В следующих k строках выходного файла требуется вывести минимально-символьные строки, составленные из данного набора символов.

Если существует несколько правильных ответов, разрешается вывести любой из них.

Пример входных и выходных данных

Легкая, вариант-1

Пете подарили n гирь и чашечные весы. Каждая гиря весит a_i грамм. Первым делом он разложил гири на чаши. При этом одна из чаш может быть пустой. Теперь он хочет выяснить, какой наименьшей разницы весов на чашах можно достичь, не более чем за два перекладывания гирь.

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

Входные данные

В первой строке находится одно натуральное число n (1 ≤ n ≤ 50) — количество гирек.
В каждой из следующих n строк находятся два натуральных числа a_i, b_i (1 ≤ a_i ≤ 1000, 1 ≤ b_i ≤ 2) — масса гири и номер чаши весов, на которой она находится.

Выходные данные

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

Пример входных и выходных данных

Сжатие текста

День рождения

Узник нейропривода

Игра