Информатика

Входные данные
Вводятся 2 числа: x и d.

Выходные данные
Подсчитайте и выведите одно число - сколько раз встречается в записи натурального числа x цифра d.

Напишите рекурсивную функцию, возводящую число a в степень n. Гарантируется, что все числа "помещаются" в стандартные вещественные (a и ответ) и целые (n) типы.

Входные данные
Вводится 2 числа - a и n (число n может быть отрицательным).

Выходные данные
Необходимо вывести  значение aⁿ

Однажды Юрик оказался в лесу у костра, где собрались \(n\) человек. Оказалось, что некоторые из них знакомы друг с другом. Для удобства пронумеруем людей целыми числами от \(1\) до \(n\). Обозначим как \(d_i\) количество людей, сидящих у костра, с которыми знаком \(i\)-й человек. Неожиданно оказалось, что два человека с номерами \(i\) и \(j\) (\(i \ne j\)) знакомы друг с другом тогда и только тогда, когда \(d_i = d_j\).

Вернувшись домой, Юрик задумался, какое минимальное количество пар людей могли быть знакомы, чтобы выполнялось это условие?

Формат входных данных
Единственная строка содержит одно целое число \(n\) (\(1 \le n \le 5\,000\)) — количество людей.

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

Замечание
Рассмотрим первый пример из условия. Возможны следующие варианты:

1. Любые два человека знакомы друг с другом. В этом случае количество пар знакомых людей равно \(\frac{4 \cdot 3}{2} = 6\).

2. Некоторые три человека попарно знакомы друг с другом, четвертый человек не знаком ни с кем. В этом случае количество пар знакомых людей равно \(3\).

Профиль Уральских гор задается ломаной (x₁, y₁), (x₂, y₂), …, (x_N, y_N), для координат вершин которой верны неравенства x₁ < x₂ < … < x_N. Начальные и конечные точки профиля расположены на уровне моря (y₁ = y_N = 0).

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


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

Формат входных данных
Первая строка входных данных содержит два целых числа N и L — количество вершин ломаной (2 ≤ N ≤ 100 000) и максимальную длину моста (1 ≤ L ≤ 10⁶) соответственно. Вторая строка  содержит координаты точки A, третья строка — координаты точки B. Точки A и B различны.

Последующие N строк содержат координаты вершин ломаной (x₁, y₁), (x₂, y₂), …, (x_N, y_N). Координаты вершин ломаной, а также точек A и B, задаются парой целых чисел, не превосходящих по абсолютному значению 106. Гарантируется, что x₁ < x₂ < … < x_N и y₁ = y_N = 0, а также, что точки A и B принадлежат ломаной.

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

Перед выпуском VK Messenger’а разработчики из компании IT-компании <<VK>>, как и положено, убеждаются в корректности работы приложения. Проверкой корректности работы систем занимаются тестировщики и QA-инженеры.

Часть функциональных тестов для тестирования смены ников выглядит следующим образом:

1. генерируется случайный сценарий взаимодействия пользователей с приложением;

2. в приложении симулируется выполнение этого сценария;

3. проверяется корректность итогового состояния приложения.

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

Каждый сценарий состоит из трех наборов событий.

1. Первый набор состоит из событий вида <<в момент времени \(t_i\) поступил запрос регистрации нового пользователя с ID \(\mathtt{id}_i\) и ником \(\mathtt{handle}_i\)>>.

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

2. Второй набор описывает события вида <<в момент времени \(t_i\) пользователь с ником \(\mathtt{handle}_{i,1}\) отправляет запрос на смену ника на \(\mathtt{handle}_{i,2}\)>>.

   Гарантируется, что для каждого такого запроса ник \(\mathtt{handle}_{i,1}\) кому-то принадлежит. Если \(\mathtt{handle}_{i,2}\) уже занят каким-либо пользователем, запрос отклоняется, иначе пользователь успешно меняет ник. При успешной смене ника старый ник перестает ассоциироваться с каким-либо пользователем, пока кто-то снова его не займет.

3. Третий набор описывает события вида <<в момент времени \(t_i\) пользователь с ником \(\mathtt{handle}_{i,1}\) отправляет сообщение пользователю с ником \(\mathtt{handle}_{i,2}\).

   Гарантируется, что и \(\mathtt{handle}_{i,1}\) и \(\mathtt{handle}_{i,2}\) на момент времени \(t_i\) соответствуют каким-то зарегистрированным пользователям.

Также гарантируется, что никакие два события не происоходят в одно и то же время, то есть все \(t_i\) уникальны.

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

Формат входных данных
В первой строке ввода дано единственное целое число \(T\) — количество сценариев, которое вам необходимо обработать (\(1 \le T \le 100\)).

Далее следуют \(T\) описаний сценариев. Описание каждого сценария начинается с пустой строки, после чего следуют три набора событий. В первой строке описания \(q\)-го набора (\(q\) от \(1\) до \(3\)) дано единственное целое число \(n_q\) — количество событий в наборе, после чего следуют \(n_q\) строк в указанном ниже формате (\(1 \le n_1 + n_2 + n_3 \le 1000\); \(0 \le n_q\)).

1. События первого набора задаются в формате <<REG \(\mathtt{id}_i\) BY \(\mathtt{handle}_i\) AT \(t_i\)>>.

2. События второго набора задаются в формате <<CHANGE \(\mathtt{handle}_{i,1}\) TO \(\mathtt{handle}_{i,2}\) AT \(t_i\)>>.

3. События третьего набора задаются в формате <<SEND FROM \(\mathtt{handle}_{i,1}\) TO \(\mathtt{handle}_{i,2}\) AT \(t_i\)>>.

Моменты событий \(t_i\) — целые числа от \(1\) до \(10^9\). Также все \(\mathtt{id}_i\) — целые числа от \(1\) до \(10^9\), а \(\mathtt{handle}_i\) — строки из маленьких латинских букв длины не более \(10\).

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

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

В первой строке статистики выведите целое число \(q\) — количество зарегистрированных пользователей. В следующих \(q\) строках выведите статистику для каждого пользователя в порядке возрастания их ID в формате <<<\(\mathtt{id}\)> RECEIVED <\(\mathtt{total}\)> TOP <\(\mathtt{count}_\mathrm{top}\)> FROM <\(\mathtt{id}_\mathrm{top}\)>>>, где \(\mathrm{total}\) — суммарное количество полученных пользователем сообщений, \(\mathtt{id}_\mathrm{top}\) — ID пользователя, от которого он получил больше всего сообщений, а \(\mathtt{count}_\mathrm{top}\) — само количество сообщений, полученных от пользователя \(\mathtt{id}_\mathrm{top}\).

Если у некоторого пользователя есть несколько собеседников, отправивших ему максимальное число сообщений, выведите в качестве \(\mathtt{id}_\mathrm{top}\) минимальный из их ID. Если пользователь не получал сообщения, считайте \(\mathtt{count}_\mathrm{top}\) равным \(0\).

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

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

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

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

Входные данные:
В первой строке дана строка s (1 <= |s| <= 5000000).

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

Примеры:
 

Входные данные	Выходные данные
abbabbbab	3
aabb	1

Пояснения:
В первом примере исследователи могут разбить цепочку 'abbabbbab' на фрагменты 'abb', 'abb', 'bab', тогда вождю каждого встреченного ими племени достанется по одной стекляшке типа 'a' и по две стекляшки типа 'b'.

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

Ужасная болезнь поражает коров. Фермер Джон хочет их защитить.
Амбар ФД - это узкое длинное здание, содержащее N стойл в ряд (2≤N≤105). Некоторые из этих стойл уже заняты коровами, некоторые - свободны. Прочитав о необходимости социального дистанцирования, ФД хочет максимизировать D, где D, это расстояние между двумя ближайшими занятыми стойлами. Например, если стойла 3 и 8 ближайшие, которые заняты, тогда D=5.

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

Входные данные
Первая строка ввода содержит N. Следующая строка содержит строку длиной N из 0 и 1, описывающая последовательность стойл в амбаре. 0 означает пустое стойло, 1 означает занятое стойло. В строке имеется как минимум два нуля, что достаточно для размещения двух коров.
Выходные данные
Выведите наибольше значение D (наименьшее расстояние между двумя занятыми стойлами), которое ФД может получить добавлением двух новых коров оптимальным образом.

Примеры

№	Входные данные	Выходные данные
1	14 10001001000010	2	В этом примере ФД может добавить коров так: 10x010010x0010 где x показывает новых коров. В этом случае D=2. Невозможно разметить коров так, чтобы получить D больше.

Громозека имеет последовательность целых чисел A длины N. Он свободно выбирает целое число b. Здесь ему станет грустно, если Ai и b+i находятся далеко друг от друга. Точнее, печаль Громозеки рассчитывается следующим образом:
\(abs(A_1-(b+1))+abs(A_2-(b+2))+...+abs(A_N-(b+N))\).
Здесь \(abs(x) \)- это функция, которая возвращает абсолютное значение x. Найдите минимально возможную печаль Громозеки.

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

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

Примеры

№	Входные данные	Выходные данные	Пояснение
1	5 2 2 3 5 5	2	Если мы выберем b = 0, печаль Громозеки будет \(\)  abs (2- (0 + 1)) + abs (2-(0 + 2))+ abs (3-(0 + 3)) + abs (5- (0 + 4)) + abs(5-(0 + 5)) = 2. Любой другой выбор b не делает печаль Громозеки меньше 2, поэтому ответ - 2.
2	9 1 2 3 4 5 6 7 8 9	0
3	6 6 5 4 3 2 1	18
4	7 1 1 1 1 2 3 4	6

Вам дано положительное целое число 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 учащихся класса, удобно пронумеровали числами от 1 до N. На линейке 1 сентября они стояли в ряд, но теперь не уверены в том, в каком порядке они стояли. Однако каждый запомнил следующий факт: абсолютную разницу между количеством учащихся, стоявших слева от этого человека, и количеством учащихся, которые стояли справа от этого человека. Согласно их отчетам, разница для человека i равна Ai . На основании этих отчетов, найдите количество возможных расстановок, в которых они стояли. Поскольку ответ может быть очень большим, выведите его по модулю \(10^9+7\). Обратите внимание, что отчеты могут быть неправильными и, следовательно, не может быть согласованного порядка. В таком случае выведите 0.

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

Выходные данные
Выведите количество возможных расстановок по модулю \(10^9+7\).
 

 

Примеры

№	Входные данные	Выходные данные	Пояснение
1	5 2 4 4 0 2	4	Возможны 4 расстановки учащихся, а именно: 2 ,1 ,4 ,5 ,3 2 ,5 ,4 ,1 ,3 3 ,1 ,4 ,5 ,2 3 ,5 ,4 ,1 ,2
2	7 6 4 0 2 4 0 2	0	Любая расстановка не совместима с отчетами. Поэтому ответ 0.
3	8 7 5 1 1 7 3 5 3	16

 

– Это что за остановка – Бологое иль Поповка? – А с платформы говорят: – Это город Ленинград.
«Вот какой рассеянный», Самуил Маршак
Пытаясь спастись от мира спортивного программирования, Алина сбежала на вокзал и уехала прочь на ночной электричке. Минуты медленно уплывали в даль, и уставшую девочку клонило в сон. Ей снился город-сказка, где не надо программировать, а можно гулять, мечтать и наслаждаться жизнью. Внезапно дождь из интерактивных задач разрушил эту идиллию.

Проснувшись и открыв окно, Алина задалась вопросом весьма философского свойства: «Где я?». С перрона потерявшейся девочке сообщили, что этот город, не похожий ни на что вокруг, представляет собой неориентированный граф на n вершинах и m ребрах. Сeй невероятный факт, однако, нисколько не удивил Алину. Она давно мечтала побывать в одном таком городе — Петербурге. Его уникальной отличительной особенностью является то, что хотя бы половина его ребер — мосты (определение дано в конце условия). Так как никакие другие города Алине не интересны, она решила ограничиться расспросом находящихся на платформе эрудированных путешественников. Любой из их них может по данной вершине v сообщить любое ещё не названное ребро, исходящее из нее, или же заявить об отсутствии таковых.

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

Обратите внимание, что в графе могут присутствовать петли и кратные ребра.

Протокол взаимодействия
В первой строке стандартного потока ввода даны два целых числа n и m (1 ≤ n, m ≤ 100000 ) — число вершин и ребер в графе соответственно.

Для того, чтобы узнать очередное ребро, исходящее из u-й вершины (1 ≤ u ≤ n), нужно вывести « ? u  ». После этого ваша программа на вход получит целое число v (−2 ≤ v ≤ −1 или 1 ≤ v ≤ n)  — v=a+b−u, если существует ребро ab, которое инцидентно вершине u и ещё не было названо , −1, если такого ребра не существует и −2, если вы превысили допустимое число запросов. В последнем случае ваша программа должна немедленно завершиться, в ином случае жюри не гарантирует корректность полученного вами вердикта.

Вам разрешается задать не более 3n вопросов.

Чтобы сообщить, что ответ найден, требуется вывести « ! Yes » или « ! No », в зависимости от того, является ли загаданный граф Петербургом. В случае положительного ответа выведите \( {m \over 2}\) строк, по два целых числа u_i и v_i в каждой (1 ≤ u_i, v_i ≤ n), обозначающих, что ребро (u_i, v_i) является мостом. Любое ребро в приведенном списке должно встречаться не более одного раза (кратные ребра считаются различными).

Запрос на вывод ответа не входит в ограничение на 3n запросов.

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

Ввод-вывод в примерах демонстрирует пример взаимодействия вашей программы с проверяющей системой.

В первом примере был загадан граф на трех вершинах с ребрами (1, 2) , (2, 3)  и (3, 1) .

Во втором примере была загадан граф на четырех вершинах с ребрами (1, 2) , (2, 3) , (3, 4)  и (2, 3) .

Ребро, соединяющее вершины u и v, называется мостом, если после его удаления между вершинами u и v не существует пути.

Примеры

№	Входные данные	Выходные данные
1	3 3 2 2 -1 3 -1 -1	? 3 ? 1 ? 2 ? 1 ? 1 ? 3 ! No
2	4 4 2 3 2 -1 4 -1 -1 -1	? 1 ? 2 ? 3 ? 1 ? 3 ? 3 ? 2 ? 4 ! Yes 1 2 3 4

Некоторый заводской цех представляет собой прямоугольник размером 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».
 

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

Формат входных данных
В первой строке входного файла находятся целые числа n, m и t (1 ≤ n, m ≤ 100, 1 ≤ t ≤ 6) — размеры таблицы и количество секунд. Каждая из следющих n строк содержит m символов. Символ «.» означает, что в изначальной конфигурации клетка не заражена, а символ «*» — что заражена. Количество «*» в таблице не превышает 8. Гарантируется, что незараженных клеток в исходной конфигурации не меньше t.

Формат выходных данных
Выведите количество различных возможных конфигураций таблицы после t секунд.
 

Ввод	Вывод
2 2 1 *. ..	2
2 2 2 *. ..	3
2 2 3 *. ..	1

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

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

При отображении телефонного номера на экране телефона, части этого номера принято отделять друг от друга различными символами так, чтобы номер было проще прочитать и запомнить. Так, перед кодом страны обычно ставится символ «+», код региона или оператора берется в скобки, номер абонента разделяется символами «-» на несколько частей. При этом, то, на сколько частей он разбивается, напрямую зависит от количества цифр в нем:
• если номер абонента состоит из трех цифр, то он представляет собой одну часть, состоящую из трех цифр;
• если номер абонента состоит из четырех цифр, то он разбивается на две части, каждая из которых состоит из двух цифр;
• если номер абонента состоит из пяти цифр, то он разбивается на две части, первая из которых состоит из трех цифр, а вторая — из двух;
• если номер абонента состоит из шести цифр, то он разбивается на три части, каждая из которых состоит из двух цифр;
• если номер абонента состоит из семи цифр, то он разбивается на три части, первая из которых состоит из трех цифр, а все остальные — из двух.

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

Формат входных данных
Первая строка файла содержит одно целое число n (1 ≤ n ≤ 100) — количество государств, информация про телефонные коды которых записана в память телефона. Далее следуют n описаний этих государств, разделенных переводами строк. Первая строка описания каждого государства содержит два целых числа c и k (1 ≤ c ≤ 999, 1 ≤ k ≤ 100) — телефонный код этого государства и количество операторов или регионов, существующих в этом государстве. Следующие k строк описания этого государства содержат целые числа, каждое из которых не меньше 100 и не больше 99999 — коды операторов или регионов, зарегистрированных в этом государстве.
Следующая строка входного файла содержит одно целое число m (1 ≤ m ≤ 10 000) — количество телефонных номеров, которые необходимо отформатировать. Следующие m строк содержат сами номера — строки, состоящие ровно из 11 цифр.
Гарантируется, что ни один данный вам номер невозможно разбить на код государства, код оператора или региона и номер абонента более, чем одним способом.

Формат выходных данных
Выведите номера, данные вам во входном файле, отформатированными по правилам, описанным в условии. Каждый номер необходимо вывести в отдельной строке. Номера необходимо выводить в том же порядке, в котором они были перечислены во входном файле. Вместо номеров, корректного разбиения которых на код государства, код оператора или региона и номер абонента не существует, необходимо вывести слово «Incorrect».
 

Ввод	Вывод
2 7 3 981 3517 812 351 3 34712 1234 963 8 79818266456 35196328463 78122472557 01234567890 73517960326 35134712239 35112342013 78120203040	+7(981)826-64-56 +351(963)284-63 +7(812)247-25-57 Incorrect +7(3517)96-03-26 +351(34712)239 +351(1234)20-13 Incorrect

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

Гномы разделились на два отряда, которые начали свои поиски с пещер u₀ и v₀, соответственно. Гномы каждого из отрядов перемещаются вместе. На обследование пещеры у отряда гномов уходит ровно одна минута, после чего каждый отряд быстро перемещается по переходу в одну из соседних пещер. При этом гномы никогда не заходят в пещеру, если они или другой отряд в ней уже побывали. Оба отряда никогда не заходят в одну и ту же пещеру. Если хотя бы один из отрядов гномов не может переместиться в соответствии с этими правилами, оба отряда сразу прекращают поиски сокровищ.

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

Формат входных данных
В первой строке число n (2 ≤ n ≤ 200 000) — число пещер в Одинокой горе. В следующих n−1 строках заданы переходы между пещерами. В каждой строке записаны номера двух пещер v и u, соединенных переходом (1 ≤ v, u ≤ n). В следующей строке заданы номера пещер v₀ и u₀, в которых исходно находятся два отряда гномов (1 ≤ v₀, u₀ ≤ n, v₀ != u₀).

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

Ввод	Вывод	Пояснение
6 1 2 2 3 3 4 4 5 5 6 4 5	2
8 1 2 2 3 3 4 2 5 5 6 3 7 7 8 1 8	4

Олег очень любит двоичные последовательности — последовательности из нулей и единиц. Совсем недавно он написал в тетради очередную двоичную последовательность из 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.
 

Ввод	Вывод
3 0 0 1	2
4 0 0 1 0	0
3 0 3 -1	0
3 -1 -1 -1	8

Пояснение
В первом примере подходят последовательности {0, 1, 0 }  и { 1, 0, 1 }.
Во втором примере не существует ни одной двоичной последовательности длины 4 с заданной Z-функцией.
В третьем примере z[2] = 3, что противоречит определению Z-функции, поэтому ответ 0.
В четвертом примере подходит любая двоичная последовательность длины 3.