Алгоритмы

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

Входные данные
В первой строке входного файла находятся числа N - количество площадей в городе и М - количество улиц их соединяющих (1 <= N <= 20000, 1 <= M <= 200000). Площади имеют номера от 1 до N. В каждой из следующих M строк находится пара натуральных чисел, описывающая между какими двумя площадями проходит соответствующая улица (две площади соединяются не более чем одной улицей).

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

 
 

Примеры

№	Входные данные	Выходные данные
1	10 16 2 6 3 7 6 5 5 9 5 4 1 2 9 8 6 4 2 10 3 8 7 9 1 4 2 4 10 5 1 6 6 10	1 4

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

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

Входные данные
Программа получает на вход несколько строк. В первой строке находятся числа n (1 <= n <= 500) и m - количество планет и количество космических маршрутов между планетми, соответственно. В следующих m строках записана информация о маршрутах. Каждый маршрут описывается в отдельной строке следующим образом. Сначала указаны номера планет, которые соединяются космическим маршрутом, потом время, которое тратится на перелет по этому маршруту, и, наконец, максимальный космического корабля, который можно заправить на этом маршруте. Известно, что все космические маршруты соединяют различные планеты, причем для каждой пары планет есть не более одного маршрута, непосредственно их соединяющий. Все числа разделены одним или несколькими пробелами. 

Планеты нумеруются числами от 1 до n. Планеты Земля имеет номер 1, а планета Шешинера - номер n. Время перелета по маршруту задано в минутах и не превосходит 1440 (24 часа). Ограничение на массу задано в граммах и не превосходит одного миллиарда. Кроме того, известно, что один ананас весит 100 грамм, а пустой корабль -  3 тонны.

Выходные данные
Выведите одно число - максимальное количество ананасов, которое можно доставить, потратив не более 24часов.
 

Примеры

№	Входные данные	Выходные данные
1	3 3 1 2 10 3000220 2 3 20 3000201 1 3 1 3000099	2

Игрушечный лабиринт представляет собой прозрачную плоскую прямоугольную коробку, внутри которой есть препятствия и перемещается шарик. Лабиринт можно наклонять влево, вправо, к себе или от себя, после каждого наклона шарик перемещается в заданном направлении до ближайшего препятствия или до стенки лабиринта, после чего останавливается. Целью игры является загнать шарик в одно из специальных отверстий – выходов. Шарик проваливается в отверстие, если оно встречается на его пути (шарик не обязан останавливаться в отверстии).

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

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

В первой строке входного файла записаны числа N и M – размеры лабиринта (целые положительные числа, не превышающие 100). Затем идет N строк по M чисел в каждой – описание лабиринта. Число 0 в описании означает свободное место, число 1 – препятствие, число 2 – отверстие.

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

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

 

Примеры

№	Входные данные	Выходные данные
1	4 5 0 0 0 0 1 0 1 1 0 2 0 2 1 0 0 0 0 1 0 0	3

На плоскости даны N точек. Вам требуется построить выпуклую оболочку данного множества точек. Выведите два числа: периметр и площадь.

Входные данные
Первая строка содержит количество точек N, 1≤N≤10000. Каждая из последующих N строк содержит два целых числа – координаты x_i и y_i. Все числа по модулю не превосходят 10⁴.

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

Примеры

№	Входные данные	Выходные данные
1	4 0 0 3 4 3 1 6 0	16.0000000000 12.0000000000

Молчун, Ворчун и Пилюлькин играют в карточную игру на троих. Правила игры следующие.
Сначала у каждого из трех игроков есть колода, состоящая из некоторого количества карт.
В колоде Пилюлькина N карт, в колоде Молчуна M карт, а в колоде Ворчуна K карт. На каждой карточке написана буква p, m или v. Порядок карт в колодах не может быть изменен. Игроки ходят по очереди. Пилюлькин ходит первым.
Если в колоде текущего игрока есть хотя бы одна карта, сбросьте верхнюю карту в колоде.
Затем следующий ход переходит к игроку, имя которого начинается с буквы на сброшенной карте.Например, если на карте написано «p», следующий ход переходит Пилюлькину.
Если колода текущего игрока пуста, игра заканчивается, и текущий игрок выигрывает игру.
Есть 3N + M + K возможных вариантов раскладки начальных колод трех игроков.
Сколько из этих шаблонов приведет к победе Пилюлькина? Поскольку ответ может быть большим, выведите его по модулю 1000000007 (= 10⁹ +7).

Входные данные
На вход подается три целых числа N, M и K (2<=N, M, K <=3*10⁵).

Выходные данные
Выведите количество победных для Пилюлькина шаблонов по модулю 1000000007 (= 10⁹ +7).

 

Примеры

№	Входные данные	Выходные данные	Пояснение
1	1 1 1	17	Если карта Пилюлькина - p, то Пилюлькин выиграет независимо от карты Молчуна и Ворчуна. Таких вариантов 3 × 3 = 9. Если карта Пилюлькина - m, Пилюлькин выиграет только тогда, когда карта Молчуна - p, или когда карта Молчуна - v, а карта Ворчуна - p. Всего таких шаблоно 3 + 1 = 4. Если карта Пилюлькина - v, Пилюлькин выиграет только тогда, когда карта Ворчуна - p, или когда карта Ворчуна - m, а карта Ворчуна - p. Всего таких шаблонов 3 + 1 = 4. Таким образом, всего 9 + 4 + 4 = 17 шаблонов, которые приведут к победе Пилюлькина.
2	4 2 2	1227
3	1000 1000 1000	261790852

 

Сегодня на уроке Петя узнал про бессуффиксные коды. Множество строк называется бессуффиксным кодом, если:

• все строки в множестве различны;
• не существует такой пары различных строк, что одна строка является суффиксом другой.

Строка s называется суффиксом строки t, если длина строки s не больше длины строки t, а также для любого i i-й символ строки s, считая с конца, совпадает с i-м символом строки t, считая с конца.

Например, ab является суффиксом строк ab и cab, но не является суффиксом строк a и ac.

Петя же решил придумать что-то новое и ввёл новое понятие — k-бессуффиксный код. Таким кодом он назвал множество строк, такое что:

• все строки в множестве различны;
• у любых двух различных строк наибольший общий суффикс имеет длину не больше k.

Наибольшим общим суффиксом двух строк s и t называется наибольшая по длине строка, являющаяся суффиксом обеих строк.

Теперь по данному набору строк s1, s2, ..., sn и числу k Петя хочет найти в этом наборе k-бессуффиксный код, состоящий из максимально возможного количества строк.

Помогите ему — найдите этот код.
 

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

В первой строке содержатся два числа n и k — количество строк в наборе и максимальная длина общего суффикса соответственно (1 ≤ n ≤ 105, 1 ≤ k ≤ 100). В i-й из следующих n строк содержится строка si — i-е слово из набора (1 ≤ |si| ≤ 100). Все строки состоят из строчных латинских букв. Гарантируется, что суммарная длина всех строк не превосходит 106.
 

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

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

Примечание
В первом примере у строк 1 и 5, а также у строк 2 и 4 наибольший общий префикс больше k, поэтому максимальное количество строк, из которых может состоять k-беспрефиксный код - 3. Во втором примере у любой пары подстрок наибольший общий префикс не больше 2, однако, так как код не может содержать одинаковые строки, больше 3 строк в него не включить.

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

Входные данные
В первой строке входных данных содержится число N (1 <= N <= 10000). Во второй строке находится перестановка (последовательность натуральных чисел от 1 до N, разделенных пробелами).

Выходные данные
Требуется вывести искомую перестановку.

Примеры

№	Входные данные	Выходные данные
1	3 1 3 2	2 1 3

Рассмотрим таблицу размера MxN, в клетках которой стоят целые неотрицательные числа. Скажем, что таблица является симпатичной, если для всех i сумма чисел ее i-ой строки не превышает R_i, и для всех j сумма чисел ее j-го столбца не превышает Cj.

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

Входные данные
Первая строка входных данных содержит числа M и N (1 <= M, N <= 20). Следующая строка содержит M целых неотрицательных чисел - R₁, R₂, ..., R_M. Далее идет строка, содержащая N целых неотрицательных чисел C₁, C₂, ..., C_N. Все вводимые ограничения не превышают 106. Следующие M строк содержит по N целых чисел, которые задают Z. Если на некотором месте в таблице Z отсутствует число, то на этом месте во входных данных стоит  -1.

Выходные данные
Выведите найденную таблицу – M строк по N чисел. Если решения не существует, выведите единственное число -1.
 

Примеры

№	Входные данные	Выходные данные
1	2 2 1 10 1 10 -1 -1 -1 1	0 1  1 1

Со времен написания условия предыдущей задачи многое изменилось. Симпатичные узоры (о том, что это такое – см. задачу "Симпатичные узоры") стали очень популярны по всему миру, поэтому люди готовы содержать очень большой участок земли, лишь бы иметь на ней узор, не встречающийся больше нигде.

Теперь компания BrokenTiles является ведущим производителем симпатичных узоров в мире! Для составления плана исполнительному директору Васе по-прежнему необходимо знать, сколько клиентов могут рассчитывать на узор данных размеров.

Так как масштабы буквально мировые, N <= 10¹⁰⁰. Однако Вася не любит большие числа, поэтому просит выдать ответ по модулю P.

Входные данные
В первой строке входных данных  содержатся три положительных целых числа, разделенные пробелом – N, M и P (1 <= N <= 10¹⁰⁰, 1 <= M <= 5, 1 <= P <= 10 000).

Выходные данные
Выведите  количество различных симпатичных узоров N x M по модулю P .

Имеется сетка из 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.

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

 

Примеры

№	Входные данные	Выходные данные	Пояснения
1	2 3 0 1 1 1 0 1 1 4 0 1 2 3 3	3	Перекрасить (1,1) в цвет 2. Неправильный (1,1) становится D 1,2 = 1. Перекрасить (1,2) в цвет 3. Неправильность (1,2) становится D 2,3 = 1. Перекрасить (2,2) в цвет 1. Неправильность (2,2) становится D. 3,1 = 1. В этом случае сумма неправильности всех квадратов равна 3. Отметим, что возможно \(Di, j  \neq D j, i \).
2	4 3 0 12 71 81 0 53 14 92 0 1 1 2 1 2 1 1 2 2 2 1 3 1 1 2 2	428

 

Напишите программу, переводящую число из двоичной системы счисления в шестнадцатеричную

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

Выходные данные
Необходимо записать в шестнадцатеричном виде и вывести данное число с использованием цифр 0, ..., 9 и букв A, ..., F без лидирующих нулей.

Примеры

№	Входные данные	Выходные данные
1	10100	14

Вновь открытое казино предложило оригинальную игру.

В начале игры крупье выставляет в ряд несколько фишек разных цветов. Кроме того, он объявляет, какие последовательности фишек игрок может забирать себе в процессе игры. Далее игрок забирает себе одну из заранее объявленных последовательностей фишек, расположенных подряд. После этого крупье сдвигает оставшиеся фишки, убирая разрыв. Затем игрок снова забирает себе одну из объявленных последовательностей и так далее. Игра продолжается до тех пор, пока игрок может забирать фишки.

Рассмотрим пример. Пусть на столе выставлен ряд фишек rrrgggbbb, и крупье объявил последовательности rg и gb. Игрок, например, может забрать фишки rg, лежащие на третьем и четвёртом местах слева. После этого крупье сдвинет фишки, и на столе получится ряд rrggbbb. Ещё дважды забрав фишки rg, игрок добьётся того, что на столе останутся фишки bbb и игра закончится, так как игроку больше нечего забрать со стола. Игрок мог бы действовать и по-другому — на втором и третьем ходах забрать не последовательности rg, а последовательности gb. Тогда на столе остались бы фишки rrb. Аналогично, игрок мог бы добиться того, чтобы в конце остались ряды rrr или rbb.

После окончания игры полученные фишки игрок меняет на деньги. Цена фишки зависит от её цвета.

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

Входные данные
В первой строке входных данных содержится число K (1 ≤ K ≤ 26) — количество цветов фишек. Каждая из следующих K строк начинается со строчной латинской буквы, обозначающей цвет. Далее в той же строке через пробел следует целое число X_i (1 ≤ X_i ≤ 150, i = 1..K) — цена фишки соответствующего цвета.

В (K+2)-ой строке описан ряд фишек, лежащих на столе в начале игры. Ряд задаетсяL строчными латинскими буквами (1 ≤ L ≤ 150), которые обозначают цвета фишек ряда.

В следующей строке содержится число N(1 ≤ N ≤ 150) — количество последовательностей, которые были объявлены крупье. В следующих N строках записаны эти последовательности. Гарантируется, что сумма длин этих N строк не превосходит 150 символов, и все они непустые.

Выходные данные
Выведите единственное целое число — максимальную сумму денег, которую может получить игрок.
 

Примеры

№	Входные данные	Выходные данные
1	3 v 3 l 1 u 2 luvu 3 luv vul uuu	6

Алиса и капитан Буран играют в покер с одной картой. Однокарточный покер - это игра для двух игроков с игральными картами. Каждая карта в этой игре показывает целое число от 1 до 13 включительно. Сила карты определяется числом, написанным на ней, следующим образом:
Слабая 2 <3 <4 <5 <6 <7 <8 <9 <10 <11 <12 <13 <1 Сильная
В покер с одной картой играют следующим образом:
- Каждый игрок берет одну карту из колоды.
- Выбранная карта становится рукой игрока.
- Игроки раскрывают друг другу руки.
- Игрок с более сильной картой побеждает в игре.
- Если их карты одинаково сильны, игра заканчивается вничью.
Вы смотрите, как Алиса и капитан Буран играют в игру, и можете видеть их руки. Число, написанное на карточке Алисы, - A, а число, написанное на карточке капитана Бурана, - B.

Напишите программу для определения исхода игры.
 

Ушан решил сыграть шестигранным кубиком. На каждой из шести сторон изображено целое число от 1 до 6, а два числа на противоположных сторонах всегда в сумме дают 7. Ушан сначала кладет кубик на стол произвольной стороной вверх, а затем повторно выполняет следующую операцию. Поверните кубик на 90 ° в одном из следующих направлений: влево, вправо, вперед (кубик приблизится) и назад (кубик уйдет дальше), затем получите y очков, где y - это число, написанное на стороне, обращенной вверх.

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

Найдите минимальное количество операций, которое Ушан должен выполнить, чтобы набрать в сумме не менее x баллов.

Входные данные
На вход подается целое число x (\(1<=x<=10^{15}\)).

Выходные данные
Выведите на экран ответ.
 

 

Примеры

№	Входные данные	Выходные данные
1	7	2
2	149696127901	27217477801

 

На линии, идущей с востока на запад, есть N городов. Города пронумерованы от 1 до N в порядке с запада на восток. Каждая точка на линии имеет одномерные координаты, а точка, которая находится дальше на восток, имеет большее значение координаты. Координата города i - Xi. Вы находитесь в городе 1 и хотите посетить все остальные города. У вас есть два способа путешествовать:
- Ходить по линии. Ваш уровень усталости увеличивается на A каждый раз, когда вы путешествуете на расстояние 1, независимо от направления.
- Телепортируйтесь в любое место по вашему выбору. Ваш уровень усталости увеличивается на B независимо от пройденного расстояния.
Найдите минимально возможное общее повышение уровня вашей усталости, когда вы посетите все города этими двумя способами.

Входные данные
В первой строке заданы три целых числа N (\(2<=N<=10^5\)), A (\(1<=A<=10^9\)), B (\(1<=B<=10^9\)). Во второй строке заданы координаты городов Xi (\(1<=X_i<=10^9\)), для всех i \(X_i <X_{i+1}\)(\(1<=i<=N-1\)).

Выходные данные
Выведите на экран ответ на задачу.
 

 

Примеры

№	Входные данные	Выходные данные	Пояснение
1	4 2 5 1 2 5 7	11	Из города 1 пройдите расстояние 1 до города 2, затем телепортируйтесь в город 3, затем пройдите расстояние 2 до города 4. Общее увеличение вашего уровня усталости в этом случае составляет 2 × 1 + 5 + 2 × 2 = 11, что является минимально возможным значением.
2	7 1 100 40 43 45 105 108 115 124	84	Из города 1 пройдите пешком до города 7. Общее увеличение вашего уровня усталости в этом случае составляет 84, что является минимально возможным значением.
3	7 1 2 24 35 40 68 72 99 103	12	Посетите все города в любом порядке, телепортировавшись шесть раз. Суммарное повышение уровня утомляемости в этом случае составляет 12, что является минимально возможным значением.

 

Вам дано положительное целое число N (\(1<=N<=10^{18}\)). Найдите количество пар целых чисел u и v (\(0<=u, v<=N\)) таких, что существуют два неотрицательных целых числа a и b, удовлетворяющих \(a\ xor\ b=u\) и \(a+b=v\). Здесь xor обозначает побитовое исключающее ИЛИ. Поскольку ответ может быть очень большим, вычислите его по модулю \(10^9+7\).

Входные данные
На вход подается положительное целое число N (\(1<=N<=10^{18}\)).

Выходные данные
Выведите количество возможных пар целых чисел u и v (\(0<=u, v<=N\)) , по модулю \(10^9+7\).
 

 

Примеры

№	Входные данные	Выходные данные	Пояснения
1	3	5	u=0,v=0 (Пусть a=0,b=0, тогда 0 xor 0=0, 0+0=0) u=0,v=2 (Пусть a=1,b=1, тогда 1 xor 1=0, 1+1=2) u=1,v=1 (Пусть a=1,b=0, тогда 1 xor 0=1, 1+0=1) u=2,v=2 (Пусть a=2,b=0, тогда 2 xor 0=2, 2+0=2) u=3,v=3 (Пусть a=3,b=0, тогда 3 xor 0=3, 3+0=3)
2	1422	52277
3	1000000000000000000	787014179

 

Есть N городов. Есть также шоссе K и железные дороги L, проходящие между городами. Каждое i-я шоссе двунаправленно соединяет рi и qi города, а каждая i-я железная дорога двунаправленно соединяет ri и si города. Нет двух шоссе, соединяющих одну и ту же пару городов. Точно так же, никакие две железные дороги не соединяют одну и ту же пару городов. Будем считать, что города A и B соединены шоссе, если до города B можно добраться из города A по некоторому количеству шоссе. Здесь любой город считается соединенным с собой шоссе. Аналогичным образом, мы также определим возможность сообщения железными дорогами. Для каждого города найдите количество городов, соединенных с этим городом как шоссе, так и железными дорогами.

Входные данные
Входные данные поступают в следующем формате:

N K L 
p1 q1 
...
pK qK 
r1 s1 
... 
rl sL

Ограничения:
\(2<=N<=2\cdot10^5 \\ 1<=K,L<=10^5 \\ 1<=p_i,q_i,r_i,s_i<=N\\ p_i <q_i \\ r_i<s_i \\ Когда\ i \neq j, (p_i,q_i)\neq(p_j,q_j) \\ ?Когда\ i \neq j, (r_i,s_i)\neq(r_j,s_j)\)


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

 

Примеры

№	Входные данные	Выходные данные	Пояснения
1	4 3 1 1 2 2 3 3 4 2 3	1 2 2 1	Все четыре города связаны между собой дорогами. Железной дорогой соединены только второй и третий города. Таким образом, ответы для городов 1,2,2 и 1 соответственно.
2	4 2 2 1 2 2 3 1 4 2 3	1 2 2 1
3	7 4 4 1 2 2 3 2 5 6 7 3 5 4 5 3 4 6 7	1 1 2 1 2 2 2

 

Некоторый заводской цех представляет собой прямоугольник размером 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	8 8 1 9 420000001 3 4 180 3 3 A 3 5 FALSE 6 5 FALSE 6 2 FALSE 3 2 A     3 1 FALSE 1 1 FALSE 1 8 FALSE 2 8 FALSE 2 2 TRUE	3 5

Примечание

В соответствии с рисунком, робот будет двигаться по «восьмерке» суммарной длиной 42 метра. Следовательно, прохождение 42n+1 метра эквивалентно прохождению 1 метра, т.е. робот остановится на плите с координатами 
«3 5».
 

Во время недавних раскопок на Марсе были обнаружены листы бумаги с таинственными символами на них. После долгих исследований ученые пришли к выводу, что надписи на них на самом деле могли быть обычными числовыми равенствами. Если бы этот вывод оказался верным, это доказало бы не только то, что на Марсе много лет назад были разумные существа, но и то, что они уже умели считать…
Ученые смогли понять, что в этом случае означают найденные символы, и перевели эти равенства на обычный язык — язык цифр, скобок, знаков арифметических действий и равенства. Кроме того, из других источников было получено веское доказательство того, что марсиане знали только три операции — сложение, умножение и вычитание (марсиане никогда не использовали “унарный минус”: вместо “–5” они писали “0–5”). Также ученые доказали, что марсиане не наделяли операции разным приоритетом, а просто вычисляли выражения (если в них не было скобок) слева направо: например, 3 + 3*5 у них равнялось 30, а не 18.
К сожалению, символы арифметических действий марсиане почему-то наносили специальными чернилами, которые, как оказалось, были не очень стойкими, и поэтому в найденных листках между числами вместо знаков действий были пробелы. Если вся вышеизложенная теория верна, то вместо этих пробелов можно поставить знаки сложения, вычитания и умножения так, чтобы равенства стали верными. Например, если был найден лист бумаги с надписью “18=7 (5 3) 2”, то возможна такая расстановка знаков: “18=7+(5–3)*2” (помните про то, в каком порядке марсиане вычисляют выражения!). В то же время, если попался лист с надписью “5=3 3”, то марсиане явно не имели в виду числового равенства, когда писали это…
Вы должны написать программу, находящую требуемую расстановку знаков или сообщающую, что таковой не существует.

Формат входных данных
Первая строка входного файла состоит из натурального (целого положительного) числа, не превосходящего 2³⁰, знака равенства, и последовательности натуральных чисел (не более десяти), произведение которых также не превосходит 2³⁰. Некоторые группы чисел (одно или более) могут быть окружены скобками. Длина входной строки не будет превосходить 80 символов, и других ограничений на количество и вложенность скобок нет. Между двумя соседними числами, не разделенными скобками, всегда будет хотя бы один пробел, во всех остальных местах может быть любое (в том числе и 0) число пробелов (естественно, внутри числа пробелов нет).

Формат выходных данных
В выходной файл необходимо вывести одну строку, содержащую полученное равенство (т.е., исходное равенство со вставленными знаками арифметических действий). В случае если требуемая расстановка знаков невозможна, вывести строку, состоящую из единственного числа “–1”. Выходная строка не должна содержать пробелов.
 

Примеры

№	Входные данные	Выходные данные
1	18=7 (5 3) 2	18=7+(5–3)*2
2	5= 3 3	-1

Вы являетесь одним из разработчиков новой компьютерной игры. Игра происходит на прямоугольной доске, состоящей из W×H клеток. Каждая клетка может либо содержать, либо не содержать фишку (см. рисунок).
Важной частью игры является проверка того, соединены ли две фишки путем, удовлетворяющим следующим свойствам:
1.    Путь должен состоять из отрезков вертикальных и горизонтальных прямых.
2.    Путь не должен пересекать других фишек.
При этом часть пути может оказаться вне доски. Например: Фишки с координатами (1, 3) и (4, 4) могут быть соединены. Фишки с координатами (2, 3) и (5, 3) тоже могут быть соединены. А вот фишки с координатами (2, 3) и (3, 4) соединить нельзя — любой соединяющий их путь пересекает другие фишки.
Вам необходимо написать программу, проверяющую, можно ли соединить две фишки путем, обладающим вышеуказанными свойствами, и, в случае положительного ответа, определяющую минимальную длину такого пути (считается, что путь имеет изломы, начало и конец только в центрах клеток (или “мнимых клеток”, расположенных вне доски), а отрезок, соединяющий центры двух соседних клеток, имеет длину 1).

Формат входных данных
Первая строка входного файла содержит два натуральных числа: W — ширина доски, H — высота доски (1 ≤ W, H ≤ 75). Следующие H строк содержат описание доски: каждая строка состоит ровно из W символов: символ “X” (заглавная английская буква “экс”) обозначает фишку, символ “.” (точка) обозначает пустое место. Все остальные строки содержат описания запросов: каждый запрос состоит из четырех натуральных чисел, разделенных пробелами — X₁, Y₁, X₂, Y₂, причем 1 ≤ X₁, X₂ ≤ W, 1 ≤ Y₁, Y₂ ≤ H. Здесь (X₁, Y₁) и (X₂, Y₂) — координаты фишек, которые требуется соединить (левая верхняя клетка имеет координаты (1, 1)). Гарантируется, что эти координаты не будут совпадать (кроме последнего запроса). Последняя строка содержит запрос, состоящий из четырех чисел 0; этот запрос обрабатывать не надо. Количество запросов не превосходит 20.

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

Примеры

№	Входные данные	Выходные данные
1	5 4 XXXXX X...X XXX.X .XXX. 2 3 5 3 1 3 4 4 2 3 3 4 0 0 0 0	5 6 0
2	4 4 XXXX .X.. ..X. X... 1 1 3 1 0 0 0 0	4