Задано подвешенное дерево, содержащее n (1 ≤ n ≤ 100 000) вершин, пронумерованных от 0 до n - 1. Требуется ответить на m (1 ≤ m ≤ 10 000 000) запросов о наименьшем общем предке для пары вершин. Запросы генерируются следующим образом. Заданы числа a₁, a₂ и числа x, y и z. Числа a₃, ..., a_2m генерируются следующим образом: a_i = . Первый запрос имеет вид {a1, a2}. Если ответ на (i - 1)-й запрос равен v, то i-й запрос имеет вид {, a_2i}.

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

При интенсивном использовании домофона краска, нанесённая на цифровые клавиши, постепенно стирается. Одна из компаний, занимающихся установкой домофонов, заинтересовалась возможностью определить диапазон номеров квартир, расположенных в подъезде, по тому, насколько стёрлась краска с клавиш. Они уже обнаружили, что по состоянию клавиши можно определить, сколько раз эту клавишу нажимали. Теперь вам, программисту этой компании, поручили для начала решить простейший вариант задачи восстановления диапазона квартир по «затёртостям». А именно, вашей программе на вход даются 10 чисел — «затёртости» клавиш 0, 1, ..., 9,  т. е. количество раз, которое нажималась соответствующая клавиша. Считая, что за время использования домофона каждую квартиру набрали ровно один раз, и считая, что номера квартир в подъезде начинаются с 1 (т. е. в подъезде расположены квартиры с номерами 1, 2, ..., N при некотором N), определите диапазон квартир в этом подъезде (т. е., фактически, определите это N). Считайте, что посетители никогда не набирают ведущих нулей. Считайте, что N не может превосходить 10⁹.

Найти количество покрытий прямоугольника 2 * n фигурами в виде дощечек, каждая из которых представляет собой либо квадрат со стороной 1, либо два квадрата (2 * 1), либо “уголок” из трех квадратов:

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

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

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

В процессе развития сети коды городов регулярно меняются, при этом, коды различных городов обязательно различны. В остальном коды могут быть совершенно произвольными, в том числе код одного города может быть началом кода другого (например, код Нижнего Новгорода — 831, а код Сарова — 83130) и т. п. Если коды нескольких городов являются началом M-значного номера абонента, кодом города этого номера считается наидлиннейший из таких кодов. Так, если есть всего четыре города: Нижний Новгород, Балахна, Дзержинск и Саров с кодами, соответственно, 831, 83144, 8313 и 83130, и M = 9, то: телефоны 831123456 и 831412345 — телефоны Нижнего Новгорода, 831312345 — телефон Дзержинска, 831301234 — Сарова, а 831441234 — Балахны.

В этой задаче мы не будем учитывать различные другие ограничения на телефонные номера, существующие в реальности (например, в реальности никакой номер абонента в городе не может начинаться на 03, т. к. 03 — это телефон скорой помощи). Мы будем считать, что любой из 10^M возможных M-значных номеров является допустимым телефонным номером.

Нетривиальной задачей становится задача определения, сколько всего телефонных номеров может быть выдано в каждом городе. Например, в приведённом выше примере в Балахне и Сарове могут быть выданы 10 000 телефонных номеров (все четырёхзначные номера), в Дзержинске могут быть выданы 90000 телефонных номеров — все пятизначные телефонные номера, кроме начинающихся на ноль, а в Нижнем Новгороде могут быть выданы 890 000 номеров — все шестизначные номера, кроме тех, которые начинаются на цифру 3, а также на последовательность 44.

Напишите программу, которая решит эту задачу для произвольного набора кодов городов.