Информатика

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

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

Напишите программу, вычисляющую, через какое минимальное время все роботы смогут собраться вместе (в зале или в туннеле).

Входные данные
Сначала на вход программы поступают числа N — количество залов (1≤N≤400) и K — количество туннелей (1≤K≤20000). Далее вводится K пар чисел, каждая пара описывает номера залов, соединяемых туннелем (по туннелю можно перемещаться в обе стороны). Между двумя залами может быть несколько туннелей. Туннель может соединять зал с самим собой. Далее следует число M (1≤M≤400) — количество роботов. Затем вводятся M чисел, задающих номера залов, где вначале расположены роботы. В одном зале может быть несколько роботов.

Выходные данные
Выведите минимальное время в минутах, через которое роботы могут собраться вместе. Если роботы никогда не смогут собраться вместе, выведите одно число –1 (минус один).

Примеры

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

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

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

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

Входные данные
Сначала на вход программы поступают числа N и M (1 < N <= 100, 1 <= M <= 5000) – количество солдат в роте и количество пар солдат, про которых прапорщик знает, кто из них выше. Далее идут эти пары чисел A и B по одной на строке (1 <= A,B <= N), что означает, что, по мнению прапорщика, солдат A выше, чем B. Не гарантируется, что все пары чисел во входных данных различны.

Выходные данные
В первой строке выведите "Yes" (если можно построиться так, чтобы прапорщик остался доволен) или "No" (если нет). После ответа "Yes" на следующей строке выведите N чисел, разделенных пробелами, - одно из возможных построений.

Примеры

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

Автомат обрабатывает десятичное натуральное число N по следующему алгоритму.
1. Строится двоичная запись числа.
2. К полученному числу справа дописывается 0, если в числе единиц больше, чем нулей, и 1 в обратном случае.
3. К полученному числу справа дописывается бит четности (0, если количество единиц четное, и 1 в обратном случае).
4. Полученное число переводится в десятичную систему счисления и является результатом работы автомата.
При каком наибольшем значении N результатом работы будет число, не превышающее 155?

Автомат обрабатывает десятичное натуральное число N по следующему алгоритму.
1. Строится двоичная запись числа,
2. К полученному числу справа дописывается 0, если в числе единиц больше, чем нулей, и 1 в обратном случае.
3. Действие 2 повторяется еще раз.
4. Из середины двоичного числа убирается 2 разряда, если количество разрядов получилось четным, и 3 разряда, если нечетным.
5. Полученное число переводится в десятичную систему счисления и является результатом работы автомата.
Сколько различных значений может получиться в результате работы, если автомат обработает все значения N, которые принадлежат отрезку [100; 200] ?

Черепашка ползет по полу, который уложен квадратной плиткой со стороной A см. Начало пути Черепахи в точке X. Черепашка успела проползти расстояние D см, прежде чем хозяин взял ее на руки. Определите сколько клеток (частично или целых) успела проползти Черепашка.

Входные данные
Первая строка содержит число A – длина стороны одной плитки. Вторая строка содержит число X - координата точки, с которой Черепашка начала свой путь. Третья строка - число D - расстояние, которое проползла Черепаха. Ось OX направлена вправо. Крайняя плитка в ряду, по которому ползет Черепашка находится в начале координат. Все числа целые, не превосходящие \(2\cdot10^9 \), числа A, D – положительные, число X – положительное или равно 0.

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

 

Примеры

№	Входные данные	Выходные данные	Пояснение
1	10 15 35	4	Сторона плитки (сторона клетки на рисунке) А = 10. Черепашка начала движение с координаты Х = 15, и прошла 35. Черепаха прошла полностью или частично 4 плитки.

 

Для хранения текста в памяти компьютера отводится целое число байт. Текст занимает N бит. Какое минимальное число байт потребуется для хранения данного текста? Напишите программу.

Входные данные
Вводится целое число N. 

Выходные данные
Вывести одно число - ответ на задачу.

Примеры

№	Входные данные	Выходные данные
1	8	1
2	9	2

 
 

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

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

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

Входные данные
В первой строке входного файла записано целое число N (1 ≤ N ≤ 10⁵) - количество папок. Во второй строке записаны N целых чисел a₁, a₂, ..., a_N (0 ≤ a_i ≤ 10⁵) - количество дипломов в каждой из папок.

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

Примечание
В первом примере Иван может открыть и просмотреть папку 2 за 2 секунды и, не найдя там диплома, понять, что диплом находится в папке 1.

Во втором примере Иван за 2 секунды просмотрит папку 1, потом за 2 секунды просмотрит папку 4, а если ни в одной из них диплома не встретилось, он поймет, что диплом в папке 3.

Примеры

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

Магазины в рекламных целях часто устраивают распродажи. Так, например,одна из крупных сетей магазинов канцелярских товаров объявила два рекламных предложения: "купи N одинаковых товаров и получи еще один товар бесплатно"и "купи K товаров по цене K−1 товара".

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

Входные данные
Во входном файле записаны целые числа N, K, A и B (1 ≤ N ≤ 100, 2 ≤ K ≤ 100, 1 ≤ A ≤ 10⁹, 1 ≤ B ≤ 10⁹), разделенные пробелами.

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

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

Во втором примере рекламными предложениями воспользоваться нельзя.

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

Примеры

№	Входные данные	Выходные данные
1	4 4 13 2	8
2	3 4 8 3	2
3	3 4 7 1	9

Ушан решил сыграть в карточную игру. У него есть колода, состоящая из N съедобных карт. На i-й карте сверху написано целое число Ai. Ушан выполняет описанную ниже операцию ноль или более раз, так что значения, записанные на оставшихся карточках, будут попарно различны.
Найдите максимально возможное количество оставшихся карт. Здесь N нечетное, что гарантирует сохранение хотя бы одной карты. 
Операция: вынуть из колоды три произвольные карты. Из этих трех карт съешьте две: одну с наибольшим значением, а другую с наименьшим значением. Затем верните оставшуюся одну карту в колоду.

Входные данные
В первой строке записано нечетное число N (\(3<=N<=10^5\)). Во второй строке записаны N чисел Ai (\(1<=A_i<=10^5\))

Выходные данные
Выведите максимально возможное количество оставшихся карт.
 

 

Примеры

№	Входные данные	Выходные данные	Пояснения
1	5 1 2 1 3 7	3	Оптимальное решение - выполнить операцию один раз, вынув две карты с 1 и одну карту с 2. Одна карта с 1 и другая с 2 будут съедены, а оставшаяся карта с 1 будет возвращена в колоду. Тогда значения, написанные на оставшихся картах в колоде, будут попарно различными: 1, 3 и 7.
2	15 1 3 5 2 1 3 2 8 8 6 2 6 11 1 1	7

 

У вас есть целочисленная переменная x. Первоначально \(x = 0\). Кто-то дал вам строку S длины N, и, используя эту строку, вы выполнили следующую операцию N раз. В i-й операции вы увеличили значение x на 1, если Si = I, и уменьшили значение x на 1, если Si = D. Найдите максимальное значение, которое принимает x во время операций (в том числе до первой операции и после последней операции).

Формат входных данных
В первой строке задается число N (\(1<=N<=100\)), во второй - строка S. Длина строки N. Строка содержит только символы I и D.

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

Дан неориентированный связный взвешенный граф с N вершинами и M ребрами, который не содержит ни петель, ни двойных ребер. I-е (\(1<=i<=M\)) ребро соединяет вершину ai и вершину bi на расстоянии ci. Будем считать, что петля - это ребро, где \(a_i=b_i\) (\(1<=i<=M\)), а двойные ребра - это два ребра, где \((a_i,b_i)=(a_j,b_j) \) или \((a_i,b_i)=(b_j,a_j)\) (\(1<=i<j<=M\)). Связный граф - это граф, в котором есть путь между каждой парой разных вершин. Найдите количество ребер, которые не входят ни в один кратчайший путь между любой парой различных вершин.

Входные данные
В первой строке задаются два целых числа N и M (\(2<=N<=100\), \(N-1<=M<=min(N \cdot (N-1)/2,1000)\)). Далее идет M строк по три целых числа в каждой строке: ai, bi, ci (\(1<=a_i, b_i<=N\), \(1<=c_i<=1000\)). Данный граф не содержит петель и двойных ребер. Данный граф является связанным.

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

 

Примеры

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

 

Вам даны два целых числа K и S. Три переменные X, Y и Z принимают целые значения, удовлетворяющие условию \(0<=X,Y,Z<=K\). Сколько существует различных значений X, Y и Z, таких что \(X+Y+Z=S\)?

Входные данные
На вход подается два целых числа K (\(2<=K<=2500\)) и S (\(0<=S<=3\cdot K\)).

Выходные данные
Выведите количество троек X, Y и Z, удовлетворяющих условию.
 

 

Примеры

№	Входные данные	Выходные данные	Пояснения
1	2 2	6	Есть шесть троек X, Y и Z, которые удовлетворяют условию: Х = 0, Y = 0, Z = 2 Х = 0, Y = 2, Z = 0 Х = 2, Y = 0, Z = 0 Х = 0, Y = 1, Z = 1 Х = 1, Y = 0, Z = 1 Х = 1, Y = 1, Z = 0
2	5 15	1	Лишь одна тройка удовлетворяют условию задачи: Х = 5, Y = 5, Z = 5

 

Популярная сеть быстрого питания «McDuck's» открыла новый филиал в Берляндии. В ресторане установлено k плит. Для того чтобы приготовить бургер, надо жарить котлету в течение минуты на одной из плит, поэтому ресторан может готовить не более k бургеров в минуту.

Известно, что в «McDuck's» придут n клиентов. i-й из них придёт в момент времени t_i, закажет x_i бургеров и будет готов заплатить за них c_i бурлей. Каждый клиент готов ждать заказ в течение w минут и, если через w минут после прихода он не получил x_i бургеров, он не заплатит ничего. При этом каждый клиент готов получать только свежие бургеры, то есть только те, котлеты для которых были поджарены не раньше времени t_i. Из-за таких сложных требований ресторан не всегда сможет выполнить все заказы всех клиентов.

Менеджеров ресторана заинтересовало, какую максимальную прибыль может получить «McDuck's». Помогите им ответить на этот непростой вопрос. Можно считать, что на готовку бургеров не расходуется никаких денег.

Входные данные
В первой строке содержатся три целых числа n, k и w (1 ≤ n ≤ 100000, 1 ≤ k ≤ 10, 1 ≤ w ≤ 60) — число клиентов, число плит и время ожидания клиента, соответственно.

Следующие n строк содержат описания клиентов, состоящие из трёх целых чисел — t_i, x_i, c_i (1 ≤ t_i, x_i, c_i ≤ 10⁹) — время (в минутах) прихода i-го клиента, число бургеров, которые он закажет и число бурлей, которые он готов заплатить, соответственно. Клиенты перечислены в порядке возрастания времени прихода, то есть для любого i > 1 верно, что t_i−1 ≤ t_i.

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

Примечание
В первом тестовом примере первую котлету можно поставить жариться в момент времени 0 и тогда в момент времени 1 она будет готова и её можно будет дать в бургере первому клиенту. В момент времени 1 можно поставить жариться ещё одну котлету, она будет готова в момент времени 2 и её можно будет дать в бургере второму клиенту.
 

Примеры

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

Колоссально! — воскликнул горбоносый. — Программист! Нам нужен именно программист.
Аркадий и Борис Стругацкие, Понедельник начинается в субботу
Изучая книгу «Уравнения математической магии» Роман Ойра-Ойра и Кристобаль Хунта обнаружили интересное уравнение: a−(a⊕x)−x=0 для заданного a, где знаком  ⊕  обозначено побитовое исключающее ИЛИ (XOR) двух чисел (эта операция обозначается как ^ или xor во многих современных языках программирования). Поскольку данное уравнение предназначалось для решения на машине Алдан-3, все вычисления производились над целыми неотрицательными числами по модулю 2³². Ойра-Ойра быстро нашел x, являющееся решением, однако Кристобалю Хунте результат Ойры-Ойры показался недостаточно интересным, поэтому он спросил коллегу, сколько всего существует решений данного уравнения. Так как все вычисления производятся по модулю 2³², Кристобаля Хунту интересует количество таких решений x, что 0 ≤ x ≤ 2³². Такая задача оказалась для Ойры-Ойры слишком сложной, поэтому он обратился за помощью к Вам.

Входные данные
В первой строке задано одно целое число a (0 ≤ a ≤ 2³²−1).

Выходные данные
Выведите одно целое число — количество неотрицательных решений уравнения.

Примечание
Определим операцию побитового ИЛИ (XOR). Пусть даны два целых неотрицательных числа x и y, рассмотрим их двоичные записи (возможно с ведущими нулями): x_k...x₂x₁x₀ и y_k...y₂y₁y₀. Здесь x_i это i-й бит числа x, а y_i это i-й бит числа y. Пусть r=x⊕y — результат операции XOR над числами x и y. Тогда двоичной записью r будет r_k...r₂r₁r₀, где:
В первом примере решениями уравнения являются 0 и 2147483648=2³¹, так как 0−(0⊕0)−0=0−0−0=0 и 0−(0⊕ 2147483648)−2147483648=−4294967296=−2³²=0 по модулю 2³².

Во втором примере решениями уравнения являются 0, 2, 2147483648=2³¹ и 2147483650=2³¹+2.

В третьем примере решениями являются все x, для которых выполнено 0 ≤ x ≤ 2³².
 

Примеры

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

На детском празднике дети водили хороводы. Как только музыка закончила играть, дети всё ещё стояли в кругу. Тут Лена вспомнила, что родители дали ей коробку с k конфетками «Wilky May». Лена не жадина, поэтому она решила раздать все свои конфетки друзьям из хоровода. Лена знает, что некоторые её друзья сладкоежки, а некоторые нет. Сладкоежки берут из коробки две конфетки, если в коробке есть хотя бы две конфетки, а иначе берут одну. Остальные друзья Лены всегда берут ровно одну конфетку из коробки.

Чтобы начать раздавать конфетки, Лена вышла из хоровода, после чего в хороводе остались n ее друзей. Чтобы раздавать конфетки было проще, Лена присвоила каждому другу в хороводе номер в порядке по часовой стрелке, начиная с её лучшего друга Ромы, который получил номер 1.

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

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

Входные данные
В единственной строке задаются четыре целых числа n, l, r, k (1 ≤ n, k ≤ 10¹¹ , 1 ≤ l, r ≤ n ) — количество детей в хороводе, номер друга, которому Лена отдала коробку конфет, номер друга, который взял последнюю конфетку, и количество конфет в коробке, соответственно.

Выходные данные
Выведите одно целое число — максимально возможное количество сладкоежек среди друзей Лены или « -1 » (без кавычек), если Лена ошиблась в своих наблюдениях.
 

Примеры

№	Входные данные	Выходные данные	Пояснение
1	4 1 4 12	2	Любые два друга могут быть сладкоежками, тогда каждый два раза получит коробку конфет и последним, кто возьмёт конфету, будет четвёртый человек.
2	5 3 4 10	3	Сладкоежками могут быть любые три друга, кроме друга, стоящего на третьем месте.
3	10 5 5 1	10	Только один друг возьмёт одну конфетку, но он может быть сладкоежкой, просто он не может взять две конфеты. Все остальные в кругу тоже могут быть сладкоежками, но они не могут взять ни одной конфеты.
4	5 4 5 6	-1	Лена ошиблась и такой ситуации быть не могло.

Дана последовательность из N целых чисел (они могут быть положительными, отрицательными или равными 0). Необходимо выбрать из этих чисел два числа так, чтобы их произведение было как можно меньшим (не рассматриваются квадраты данных чисел, но можно выбрать произведение двух различных элементов последовательности, равных друг другу).
В первой строке входных данных записано целое число N, 2 ≤ N ≤10⁵ – количество данных чисел. Следующие N строк содержат сами числа, не превосходящие по модулю 40 000.
Программа должна вывести единственное целое число – наименьшее возможное произведение двух различных элементов этой последовательности.

Примеры

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

Володе очень понравились задачи олимпиады по информатике, поэтому он решил ходить на занятия кружка по программированию. Придя на первое занятие кружка, он узнал, что занятия будут проходить еженедельно в один и тот же день недели. Помогите Володе составить календарь занятий до конца года – определите даты всех занятий, начиная с первого занятия и до конца года.
Программа получает на вход два числа, записанных в разных строках: номер месяца и номер дня месяца, когда проходит первое занятие. Номер месяца может быть одним из четырёх возможных чисел – 9, 10, 11, 12. Номер дня месяца – число от 1 до 30 для сентября и ноября (месяцы с номерами 9 и 11) или от 1 до 31 для октября и декабря (месяцы с номерами
10 и 12). 
Программа должна вывести даты всех занятий кружка до конца года в хронологическом порядке, по одной дате в строке, сначала месяц, затем день месяца, через пробел. Занятия проходят еженедельно, в тот же день недели, что и первое занятие. Формат вывода дат такой же, как в условии. Считайте, что каникулы отсутствуют, а последнее занятие может происходить в любой день декабря, в том числе и 31 числа.
 

Примеры

№	Входные данные	Выходные данные
1	11 20	11 20 11 27 12 4 12 11 12 18 12 25

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

Примеры

№	Входные данные	Выходные данные	Пояснение
1	3 3 3	7	Лена съест конфеты из левой, средней, правой, средней, левой, средней, правой вазы. После этого она захочет съесть конфету из средней вазы, но в ней уже не осталось конфет.

Для пополнения бюджета в стране Авалон, известной своими горными туристическими маршрутами, ввели новый налог для туристов. Величина налога
пропорциональна длине маршрута, но, поскольку маршрут проходит по горам и пройденное расстояние, зависящее от высоты спуска и подъёма, подсчитать сложно, налог считается без
учёта высоты, то есть величина налога пропорциональна горизонтальному перемещению, совершённому туристической группой. Кроме того, в силу старинного обычая все
туристические группы должны перемещаться по горам Авалона строго с запада на восток. Турфирма хочет сэкономить на налоге, поэтому она хочет разработать туристический
маршрут с минимальной величиной налога. При этом, поскольку маршрут является горным, он должен содержать подъём в гору и спуск с горы, то есть на маршруте должна быть точка,
которая находится строго выше начала и конца маршрута. 
Турфирма составила карту гор Авалона, содержащую информацию о высоте гор при передвижении с запада на восток. Высоты гор измерены в точках через равные расстояния. 
Найдите на данной карте гор Авалона туристический маршрут минимальной длины, удовлетворяющий условию наличия подъёма и спуска.
Первая строка входных данных содержит число N – количество точек на карте гор Авалона. Следующие N строк содержат информацию о высоте гор в данных N точках при движении с запада на восток. Все числа натуральные, не превосходящие 10⁵.
Программа должна вывести два числа – номер точки начала маршрута и номер точки окончания маршрута. Точки нумеруются от 1 до N. Если маршрута, удовлетворяющего
условиям, не существует, программа должна вывести одно число 0.

Примеры

№	Входные данные	Выходные данные	Пояснение
1	7 18 10 15 20 20 10 3	3 6	Дано 7 точек с высотами 18, 10, 15, 20, 20, 10, 3. Самый короткий маршрут, содержащий подъём и спуск, – это 15, 20, 20, 10. Он начинается в точке номер 3 и заканчивается в точке номер 6.
2	3 9 8 5	0	Высота гор монотонно убывает, поэтому искомого маршрута не существует.

Антонин, Бальбин и Цезарь играют в игру "Карты на троих", алгоритм которой следующий:
- сначала у каждого из трех игроков есть колода, состоящая из некоторого количества карт. На каждой карточке написана буква 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. Антонин делает следующий ход.
Колода Антонина пуста. Игра заканчивается, и Антонин выигрывает игру.