Информатика

Зимой обитателям Московского зоопарка очень скучно, в частности, это касается горилл. Вы решили развлечь их и принесли в зоопарк перестановку \(p\) длины \(n\).

Напомним, что перестановкой длины \(n\) называется последовательность целых чисел от \(1\) до \(n\), в которой каждое такое число встречается ровно один раз. Например, последовательности \([3, 1, 2]\) и \([1, 4, 2, 3]\) являются перестановками, а последовательности \([3, 4]\) и \([1, 2, 2, 3]\) нет.

У горилл помимо вашей оказалась и своя перестановка \(q\) длины \(n\). Они предложили вам посчитать количество пар целых чисел \(l, r\) (\(1 \le l \le r \le n\)), таких что \(\operatorname{MEX}([p_l, p_{l+1}, \ldots, p_r])=\operatorname{MEX}([q_l, q_{l+1}, \ldots, q_r])\).

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

\(\operatorname{MEX}\) последовательности — это минимальное целое положительное число, отсутствующее в этой последовательности. Например, \(\operatorname{MEX}([1, 3]) = 2\), \(\operatorname{MEX}([5]) = 1\), \(\operatorname{MEX}([3, 1, 2, 6]) = 4\).

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

Вторая строка содержит \(n\) целых чисел \(p_1, p_2, \ldots, p_n\) (\(1 \le p_i \le n\)) — элементы перестановки \(p\).

Третья строка содержит \(n\) целых чисел \(q_1, q_2, \ldots, q_n\) (\(1 \le q_i \le n\)) — элементы перестановки \(q\).

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

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

Недавно Феде на день рождения подарили массив из \(n\) целых чисел, записаных по кругу, в котором для каждой пары соседних элементов (\(a_1\) и \(a_2\), \(a_2\) и \(a_3\), \(\ldots\), \(a_{n - 1}\) и \(a_n\), \(a_n\) и \(a_1\)) модуль их разности равен \(1\) (два соседних элемента отличаются ровно на \(1\)).

Назовём локальным максимумом элемент, который больше обоих соседних элементов. Также назовём локальным минимумом элемент, который меньше обоих соседних элементов. Обратите внимание, что элементы \(a_1\) и \(a_n\) являются соседними.

К сожалению, Федя потерял массив, но он запомнил в нём сумму локальных максимумов \(A\) и сумму локальных минимумов \(B\).

По заданным \(A\) и \(B\) помогите найти любой из подходящих массивов.

Формат входных данных
В первой строке вводится целое число \(A\) (\(-10^{18} \leqslant A \leqslant 10^{18}\)).

Во второй строке вводится целое число \(B\) (\(-10^{18} \leqslant B \leqslant 10^{18}\), \(B < A\)).

В третьей строке вводится целое число \(t\) (\(0 \leqslant t \leqslant 1\)) — если \(t = 0\), то от вас требуется вывести только длину массива.

Гарантируется, что при \(t = 1\) выполняется \(A - B \leqslant 10^{5}\).

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

Формат выходных данных
В первой строке выведите одно число \(n\) — длину массива. При \(t = 0\) должно быть верно, что найдется хотя бы один подходящий массив с такой длиной.

Если \(t = 1\), то выведите во второй строке \(n\) чисел \(a_1, a_2, \ldots, a_n\) (\(-10^{18} \leqslant a_i \leqslant 10^{18}\)) — элементы массива.

Гарантируется, что при \(t = 1\) существует массив, размер которого не превосходит \(4 \cdot 10^5\).

Если \(t = 0\), то во второй строке выводить ничего не нужно.

В первом примере локальными максимумами являются числа на позициях \(3\) и \(10\), а локальными минимумами числа на позициях \(6\) и \(8\).

На курсе машинного обучения вам выдали первое домашнее задание — вам предстоит проанализировать некоторый массив из \(n\) чисел.

В частности, вы интересуетесь так называемой равномерностью массива. Предположим, что в массиве число \(b_1\) встречается \(k_1\) раз, \(b_2\) — \(k_2\) раз, и т.д. Тогда равномерностью массива называется такое минимальное целое число \(c \ge 1\), что \(c \ne k_i\) для любого \(i\).

В рамках вашего исследования вы хотите последовательно проделать \(q\) операций.

• Операция \(t_i = 1\), \(l_i\), \(r_i\) задаёт запрос исследования. Необходимо вывести равномерность массива, состоящего из элементов на позициях от \(l_i\) до \(r_i\) включительно.

• Операция \(t_i = 2\), \(p_i\), \(x_i\) задаёт запрос уточнения данных. Начиная с этого момента времени \(p_i\)-му элементу массива присваивается значения \(x_i\).

Формат входных данных
Первая строка содержит \(n\) и \(q\) (\(1 \le n, q \le 100\,000\)) — размер массива и число запросов соответственно.

Во второй строке записаны ровно \(n\) чисел — \(a_1\), \(a_2\), \(\ldots\), \(a_n\) (\(1 \le a_i \le 10^9\)).

Каждая из оставшихся \(q\) строк задаёт очередной запрос.

Запрос первого типа задаётся тремя числами \(t_i = 1\), \(l_i\), \(r_i\), где \(1 \le l_i \le r_i \le n\) — границы соответствующего отрезка.

Запрос второго типа задаётся тремя числами \(t_i = 2\), \(p_i\), \(x_i\), где \(1 \le p_i \le n\) — позиция в которой нужно заменить число, а \(1 \le x_i \le 10^9\) — его новое значение

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

Первый запрос состоит из ровно одного элемента — \(1\). Минимальное подходящее \(c = 2\).

Отрезок второго запроса состоит из четырёх \(2\), одной \(3\) и двух \(1\). Минимальное подходящее \(c = 3\).

Отрезок четвёртого запроса состоит из трёх \(1\), трёх \(2\) и одной \(3\). Минимальное подходящее \(c = 2\).

 

На рисунке справа схема дорог N-ского района изображена в виде графа. В таблице звёздочкой обозначено наличие дороги из одного населенного пункта в другой. Отсутствие звёздочки означает, что дороги нет.

          

Каждому населенному пункту на схеме соответствует его номер в таблице, но неизвестно, какой именно номер.
Определите, какие номера населенных пунктов в таблице могут соответствовать населенным пунктам B и F на схеме.

В ответе запишите эти два номера в возрастающем порядке без пробелов и знаков препинания.

В развлекательном центре Е-города был установлен игровой автомат нового поколения. В автомат можно бросить монету и следить за её продвижением сверху вниз по разветвляющемуся лабиринту из трубок. В лабиринте есть \(n\) узлов, которые пронумерованы числами от 1 до \(n\). При бросании монета попадает в первый узел. Каждый узел лабиринта, кроме первого, имеет одну входящую сверху трубку, по которой монета может в него попасть. Из каждого узла выходит не более двух трубок, идущих вниз, одна из которых ведет налево, а другая "— направо. Каждая трубка имеет некоторую ширину. Монета проваливается в более широкую трубку, а в случае равенства ширины трубок "— в левую.

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

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

Панкрату понравилась игрушка, которая находится в узле с номером \(v\).

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

Формат входных данных
В первой строке задано число \(n\) — количество узлов в лабиринте. В последующих \(n\) строках заданы описания всех узлов, в \(k\)-й из этих строк описан узел с номером \(k\).

Описание \(k\)-го узла состоит из четырех целых чисел: \(a_k\), \(u_k\), \(b_k\), \(w_k\). Если из \(k\)-го узла выходит левая трубка, то \(a_k\) — номер узла, в который она ведет (\(k < a_k \leqslant n\)), а \(u_k\) — её ширина. Если левой трубки нет, то \(a_k = u_k = 0\). Если из \(k\)-го узла выходит правая трубка, то \(b_k\) — номер узла, в который она ведет (\(k < b_k \leqslant n\)), а \(w_k\) — её ширина. Если правой трубки нет, то \(b_k = w_k = 0\).

В последней строке задано целое число \(v\) (\(1 \leqslant v \leqslant n\)) — номер узла, в котором находится игрушка, понравившаяся Панкрату.

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

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

 

В первом примере первая монета пройдет лабиринт по следующему пути, и игрок получит игрушки из вершин 1, 3 и 4:

Вторая монета пройдет лабиринт по следующему пути, и игрок получит игрушки из вершин 2 и 6:

Третья монета пройдет лабиринт по следующему пути, и игрок получит игрушки из вершин 5 и 7:

Вадим работает в ЖКХ и сегодня он крайне озабочен вопросов сосулек. А именно он наблюдает за домом по адресу — проспект Программистов, дом 404. В доме \(n\) этажей, на каждом этаже по \(m\) окон, включая первый. Окна на каждом этаже пронумерованы слева направо от \(1\) до \(m\). \(i\)-e окно \(j\)-го этажа находится ровно под \(i\)-м окном \(j + 1\)-го этажа. Под некоторыми окнами свисают сосульки.

Вадим руководит установкой на дом козырька, который будет установлен ниже первого этажа и проходить под \(d\) окнами. То есть, если начало козырька находится под окном с номером \(i\), то он проходит под всеми окнами с номерами от \(i\) до \(i + d - 1\). Вадим хочет выбрать такую позицию для козырька, чтобы над ним находилось наименьшее возможное количество сосулек и из всех подходящих вариантов выбрать такой, что начало козырька будет находиться как можно левее.

Помогите Вадиму выбрать нужное окно.

Формат входных данных
В первой строке содержатся числа \(n\), \(m\), \(d\), \(k\) — количество этажей, количество окон на каждом этаже, длина козырька и количество окон, под которыми есть сосульки, соответственно (\(1 \le n, m \le 100\),\(1 \le d \le m\), \(0 \le k \le n \cdot m\)).

В следующих \(k\) строках заданы тройки чисел \(x\), \(y\), \(z\) — номер этажа, номер окна на этаже и количество сосулек под ним (\(1 \le x \le n\), \(1 \le y \le m\), \(1 \le z \le 10\)).

Гарантируется, что каждая пара \(x\), \(y\) встречается не более одного раза.

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

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

Во втором примере козырек имеет длину один и если его поставить под окнами с номерами \(1\), \(2\) или \(3\), над ним будет соответственно \(1\), \(0\) или \(2\) сосульки.

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

Однажды, девочка Аня записала несколько целых чисел лежащих в диапазоне от \(-1000\) до \(1000\) в некоторую изначально пустую строку \(S\), разделив каждые два пробелом. Но стоило ей отвернуться, как злой хулиган Гриша заменил все пробелы в строке на подстроки из строчных латинских букв. Тем не менее и этого ему показалось мало, поэтому он мог дописать латинских строчных букв еще и в начало и конец строки \(S\).

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

Формат входных данных
В первой строке содержится одно натуральное число \(n\) — количество символов в строке \(S\) (\(1 \le n \le 100\)).

Во второй строке содержится строка \(S\), состоящая из латинских строчных букв, цифр и знаков <<->>.

Гарантируется:

• В данной строке содержится хотя бы одна цифра

• В следующей позиции после каждого знака <<->> находится цифра

• В числах, изначально записанных в строку не было ведущих нулей, а также каждое из них не превосходило \(1000\) по модулю.

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

Обратите внимание, что \(0\) следует выводить без знака <<->>.

У Фили есть квадратная матрица \(A\) размера \(N \times N\), но она кажется ему слишком большой. Ему гораздо больше нравятся матрицы размера \(k \times k\) (\(k < N\)).

Филя хочет получить матрицу нужного размера взяв некоторую подматрицу исходной матрицы. Подматрицей \(k \times k\) матрицы \(A\) в данном случае Филя считает матрицу \(B\) такую, что \(b_{i, j} = a_{i + x, j + y}\), для всех \(i\), \(j\) от \(1\) до \(k\). Из данного определения можно заметить, что подматрица исходной матрицы задается парой чисел (\(x\), \(y\)).

Для того, чтобы выбрать наиболее интересную для себя подматрицу, Филя хочет узнать, сколько есть способов выбрать из исходной матрицы две различные (характеризующие пары (\(x\), \(y\)) отличаются хотя бы в одной позиции) неравные подматрицы \(k \times k\). Две матрицы \(Q\) и \(P\) размера \(k \times k\) считаются равными, если для любых \(i, j: 1 \le i, j \le k\) выполняется \(q_{i, j} = p_{i, j}\). Если условия равенства не выполняется, матрицы считаются неравными.

Формат входных данных
В первой строке входного файла содержатся два натуральных числа \(N\) и \(k\) — размеры исходной и нужной матрицы. (\(1 \le k < N \le 10\)). В следующих \(N\) строках заданы через пробел по \(N\) натуральных чисел \(a_{i, j}\) — элементы исходной матрицы (\(1 \le a_{i, j} < 10\)).

Формат выходных данных
В единственной строке выходного файла выведите одно число — количество способов выбрать из исходной матрицы две различные неравные подматрицы размера \(k \times k\).

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

Для некоторого числа \(m\) назовём \(m\)-разбиением массива такое его разбиение на непересекающиеся отрезки, что на каждом из этих отрезков медиана больше либо равна \(m\). Вам дан массив \(a\) длины \(n\) и \(q\) запросов двух видов:

1. присвоить элементу с индексом \(i\) значение \(x\);

2. найти наибольшее число \(k\) такое, что для подотрезка массива с индексами от \(l\) до \(r\) существует \(m\)-разбиение на \(k\) отрезков.

Формат входных данных
В первой строке дается число \(n\) (\(1 \le n \le 2 \cdot 10^5\)) - размер массива. В следующей строке вводятся \(n\) чисел \(a_{i}\) (\(1 \le a_{i} \le 10^9\)) - элементы массива, на следующей строке вводится число \(q\) (\(1 \le q \le 2 \cdot 10^5\)) - количество запросов. В следующих \(q\) строках даются запросы, каждый в одном из следующих форматов:

• \(1\) \(i\) \(x\) —  запрос 1 типа (\(1 \le i \le n, 1 \le x \le 10^9\));

• \(2\) \(m\) \(l\) \(r\) —  запрос 2 типа (\(1 \le m \le 10^9, 1 \le l \le r \le n\)).

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

В задаче присутствуют 6 групп:

1. \(n \le 5, q \le 5\), такие решения будут набирать не менее 10% баллов

2. \(n \le 100, q \le 100\), такие решения будут набирать не менее 20% баллов

3. \(n \le 10000, q \le 10000\), такие решения будут набирать не менее 30% баллов

4. \(m\) - одно и тоже для всех запросов, такие решения будут набирать не менее 25% баллов

5. нет запросов изменения, такие решения будут набирать не менее 35% баллов

6. Ограничения, как и в задаче

Есть шарики, пронумерованные от \(1\) до \(n\). Также поступают \(q\) запросов:

• \(add\) \(x\) - добавить в дек шарик с номером \(x\). Вы можете положить шарик либо сверху, либо снизу дека.

• \(del\) \(x\) - удалить из дека шарик с номером \(x\). Вы находите шарик с номером \(x\) в деке, достаете все шарики НИЖЕ \(x\), удаляете шарик \(x\), потом кладете достанные шарики (без \(x\)) обратно в том же порядке.

На запросы \(1\)-го типа вы тратите \(1\) действие, а на запросы \(2\)-го типа - \(2k + 1\) действий, где \(k\) - количество шариков, которые лежат ниже удаляемого (то есть вы сначала достаете \(k\) шариков, потом удаляете нижний, потом кладете достанные \(k\) шариков обратно в том же порядке).

Посчитайте, какое минимальное количество действий вы можете потратить.

Формат входных данных
Первая строка содержит числа \(n\) и \(q\) (\(1 \leq n, q \leq 2 \cdot 10^5\)) - максимальный номер шарика и количество запросов. Далее следуют \(q\) строк в формате:

• \(add\) \(x\) - добавить шарик с номером \(x\) (\(1 \leq x \leq n\)) в начало или конец дека.

• \(del\) \(x\) - удалить шарик с номером \(x\) (\(1 \leq x \leq n\)) из дека.

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

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

Замечание

В тесте 1 независимо от того, как вы добавите шарики, вы потратите 4 действия (на удаление и на добавление каждого из шариков).

В тесте 2 вам необходимо добавить шарик 5 вниз, шарик 8 вверх, шарик 1 вниз, шарик 4 вверх, тогда вы потратите ровно 6 действий.

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

На каждом уровне игры генерируется новый проспект из небоскребов, где каждая высотка задается уникальной положительной координатой относительно начала проспекта. После этого Похпид выбирает здание, с которого он начинает свой путь, при этом он может прыгать только на здание, координата которого больше текущей. Трудность этой игры заключается в том, что после каждого прыжка Похпид устает и уже не может прыгать также далеко как раньше. Формально говоря, на каждом уровне генерируется \(n\) зданий, координаты которых равны \(a_1, a_2, \ldots, a_n\). Игрок выбирает стартовый небоскреб и с него может прыгнуть на любое здание, которое находится правее, при этом длина первого прыжка может быть любой. Для всех последующих прыжков должно быть выполнено условие: если сейчас игрок находится на здании с координатой \(a_i\), а до этого был на позиции \(a_j\), то он может перепрыгнуть на здание с координатой \(a_k\), если \(a_i - a_j > a_k - a_i\).

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

Формат входных данных
В первой строке входных данных дается число уровней \(t\) \((1 \leq t \leq 1000)\).

В следующих строках каждый уровень задается числом зданий \(n\) \((1 \leq n \leq 5\,000)\) в одной строке и позициями этих зданий \(a_1, a_2, \ldots, a_n\) \((0 \leq a_i \leq 10 ^ {18}, \, a_i \neq a_j\) если \(i \neq j)\) в следующей строке. Гарантируется, что сумма \(n\) по всем уровням не превосходит \(30\,000\).

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

Решения, работающие при \(n \leq 10\) и \(t = 1\) будут получать не меньше 25% баллов.

Решения, работающие при \(n \leq 100\) и \(t \leq 10\) будут получать не меньше 50% баллов.

Решения, работающие при \(n \leq 2500\) и \(t \leq 10\) будут получать не меньше 75% баллов.

В первом примере оптимальный выбор небоскребов \(3, 5, 4, 1\) их координаты соответственно будут равны \(3, 6, 8, 9\).

Во втором примере ответы для уровней получаются выбором следующих 3 наборов индексов соответственно:
1) \(2, 1, 3\)
2) \(3, 2, 8, 7, 5\)
3) \(5, 1, 4, 2\)

Миша сидел на занятиях математики в Высшей школе экономики и решал следующую задачу: дано \(n\) целых чисел и нужно расставить между ними знаки \(+\) и \(\times\) так, чтобы результат полученного арифметического выражения был нечётным (например, между числами \(5\), \(7\), \(2\), можно расставить арифметические знаки следующим образом: \(5 \times 7 + 2 = 37\)). Так как примеры становились все больше и больше, а Миша срочно убегает в гости, от вас требуется написать программу решающую данную задачу.

Формат входных данных
В первой строке содержится единственное число \(n\) (\(2 \leq n \leq 10^5\)). Во второй строке содержится \(n\) целых чисел \(a_i\), разделённых пробелами (\(-10^9 \leq a_i \leq 10^9\)). Гарантируется, что решение существует.

Формат выходных данных
В одной строке выведите \(n - 1\) символ \(+\) или \(\times\), в результате применения которых получается нечётный результат. (Для вывода используйте соответственно знаки <<+>> (ASCII код—43) и <<x>> (ASCII код—120), без кавычек).

 

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

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

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

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

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

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

 

Маша, Даша, Миша и Саша играют с числами. Каждый из них написал некоторое множество целых чисел. Затем они выполнили следующие операции. 
1) Ребята нашли разницу между Машиным и Дашиным множествами.
2) Затем, они объединили множества чисел Миши и Саши.
3) В конце, они нашли общие элементы двух множеств, полученных в результате первой и второй операции. 

Выведите на экран в порядке возрастания числа, которые получились у Маши, Даши, Миши и Саши в результате выполнения третьей операции.

Формат входных данных
Программа получает на вход четыре пары строк (всего восемь строк), в каждой паре строк первая строка содержит целое число Ni - количество чисел в i-й строке (1 <= N <= 106, 1 <= i <= 4), вторая строка каждой пары строк содержит множество целых чисел, разделенных одним пробелом. Во второй строке записано множество чисел Маши, во четвертой - Даши, в шестой - Миши, в восьмой - Саши. Каждое число по модулю не превышает 10⁵.

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

Всего во Флатландии \(n\) городов, пронумерованных от \(1\) до \(n\), столица Флатландии имеет номер \(1\). Компьютерная сеть Флатландии устроена следующим образом: в каждом городе есть один центр подключения, который может быть связан с некоторыми другими центрами с помощью проводных каналов связи. При этом между любыми двумя городами есть ровно один маршрут по каналам связи, иначе говоря, сеть представляет собой дерево. Для города \(i\), где \(i > 1\), обозначим первый город на маршруте от города \(i\) до столицы как \(p_i\).

Запланирована модернизация сети Флатландии, в результате которой некоторые каналы связи будут заменены на более современные оптические. Оптические каналы могут быть проложены только вместо существующих проводных. Стоимость замены канала, который соединяет город \(i\) с городом \(p_i\), равна \(w_i\). Из-за ограничений технологии любой центр подключения может быть подключен оптическими каналами не более чем к \(k\) другим центрам.

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

Помогите специалистам министерства выбрать каналы для модернизации.

Формат входных данных
На первой строке ввода находятся два целых числа \(n\) и \(k\) (\(2 \le n \le 10^5\), \(1 \le k \le 100\)).

На следующих \(n - 1\) строках заданы описания каналов, \((i-1)\)-я из этих строк содержит два целых числа: \(p_i\) и \(w_i\) (\(1 \le p_i \le i\), \(0 \le w_i \le 10^9\)).

Формат выходных данных
Выведите два целых числа \(cnt\) и \(cost\): максимальное число каналов, которое удастся модернизировать и минимальную стоимость, за которую можно модернизировать такое число каналов.

Замечание
Конфигурация сети в первом примере до и после модернизации показана на рисунке ниже. Каналы, которые необходимо модернизировать, показаны жирными линиями. Максимальное число каналов, которое можно модернизировать, равно \(4\). Стоимость модернизации любого канала равна \(0\) и не показана.

Есть и другие подходящие решения, в которых модернизируется \(4\) канала.

Конфигурация сети во втором примере до и после модернизациии показана на рисунке ниже. Каналы, которые необходимо модернизировать, показаны жирными линиями. Максимальное число каналов, которое можно модернизировать, равно \(6\). Стоимость модернизации канала показана рядом с каналом, суммарная стоимость модернизации каналов в оптимальном решении равна \(27\).

Тимофей готовится к ЕГЭ. Для отработки навыка скорости и точности поиска ответов на задания по теме «Системы счисления» ему часто приходится решать примеры типа «сколько значащих нулей (или единиц) содержит двоичная запись значения выражения 2^a + 2^b − 2^c?». Значащими называются все цифры, кроме нулей в начале числа (которые обычно и не записываются). Например, десятичное число 20 в двоичной системе счисления записывается как 10100, и в этой записи две значащие цифры «1» и три значащие цифры «0».

Помогите Тимофею по известным a, b и c узнать ответ на задачу.

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

Программа получает на вход четыре целых неотрицательных числа: a, b, c и d, записанные в отдельных строках. Числа a, b и c соответствуют показателям степеней двоек в задании (0 ≤a, b, c, ≤10⁹). При этом гарантируется, что 2^a + 2^b − 2^c > 0 и a ≠ b.

Число d равно либо 0, либо 1 — цифра, количество которых в значении выражения нужно узнать.

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

Программа должна вывести одно неотрицательное целое число — ответ на задачу.

Пример

Ввод	Вывод	Пояснение
4 3 2 1	2	Нужно узнать количество единиц в двоичной записи значения выражения 24 + 23 − 22. Вычислим: 16 + 8 - 4 = 20. 2010 = 101002. Всего две единицы. Такой же результат можно получить, выполнив действия в столбик, не переводя числа в десятичную систему счисления (см. ниже).

 10000
+ 1000
 -----
 11000

 11000
-  100
 -----
 10100

Кате нравятся целые числа, которые делятся без остатка на число K, а Маше — целые числа, которые делятся без остатка на число M. Сегодня подруги решили утроить соревнование и выяснить, чьи любимые числа лучше.

Для начала они выписали на лист бумаги все целые числа от A до B включительно. Затем Катя посчитала, сколько чисел среди выписанных делятся на число K без остатка, а Маша посчитала, сколько чисел делятся на число M без остатка.

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

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

Программа получает на вход четыре целых положительных числа, записанных в отдельных строках: K, M, A и B. Числа не превосходят 2×10⁹.

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

Программа должна вывести одно целое число — разность количества любимых чисел Кати и количества любимых чисел Маши.
 

Примеры

Ввод	Вывод	Пояснение
2 3 2 9	1	Выписаны числа 2, 3, 4, 5, 6, 7, 8, 9. Среди них есть четыре числа, которые делятся на 2: 2, 4, 6, 8, и три числа, которые делятся на 3: 3, 6, 9. Ответ: 4 - 3 = 1.
3 3 6 6	0	Выписано одно число 6 и оно является любимым числом как Кати, так и Маши.
10 2 1 5	-2	Среди чисел 1, 2, 3, 4, 5 нет ни одного любимого числа Кати, а у Маши любимыми являются 2 и 4.

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

Каждая елочка имеет свою красоту, равную количеству ветвей с одной стороны ствола и (так уж совпало) длине самой нижней ветви. Каждая следующая верхняя ветка на одну клетку короче предыдущей. Между ветвями, а также под самой нижней и над самой верхней ветвями, находится ствол дерева шириной ровно в одну клетку. На рисунке вы видите елки кисти Тимофея красотой от 0 до 5 включительно.

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

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

Программа получает на вход одно целое число n — красоту ёлки (0 ≤ n ≤ 2×10⁹).

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

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

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

Изба-пятистенка или пятистенок — жилая деревянная прямоугольная постройка, разделенная внутренней поперечной стеной на две неравные части: избу (горницу) и сени. Пятая стена связывает между собой две длинные стены и делает конструкцию более прочной — не даст разъехаться связанным стенам.

2100 год. Схема сборки избы осталась прежней, а вот дерево заменено более стойким к внешним воздействиям полимерным материалом. Строители из длинной заготовки длины c отрезают бревна нужной длины и укладывают их друг на друга. На фундамент кладут два длинных бревна длины b, на них — три коротких длины a, снова два длинных, опять три коротких, и так далее. Самый верхний ряд всегда делают из трех коротких бревен.

По данным значениям a, b и c определите максимальную высоту избы, которую можно построить из одной заготовки. Каждые пять уложенных брёвен (два длинных и три коротких) увеличивают высоту дома на 1.

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

Программа получает на вход три целых числа a, b и c — длины брёвен и заготовки (1 ≤ a < b < c ≤ 10¹⁸), записанных в отдельных строках.

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

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

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

Замечание
Cтроители уложат в первый ряд два продольных бревна, отрезав от заготовки длиной 29 ровно 10 единиц длины. Потом уложат три поперечных бревна, отрезав от заготовки еще 9 единиц длины. Уложено 5 бревен, высота избы 1. От заготовки осталось 10 единиц длины, их как раз хватит на ряд из длинных бревен, но на следующий ряд заготовки уже не хватит.

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

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

Формат входных данных
Программа получает на вход три целых положительных числа, не превосходящих \(10^5\) каждое, по одному в строке, в том порядке, в котором они шли на доске.

Формат выходных данных
В первой строке выведите число, которое Вове необходимо написать. Можно доказать, что это число обязательно должно быть целым. В записи этого числа не должно быть десятичной точки, то есть вывод <<\(13{.}0\)>> вместо <<13>> является неправильным.

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

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

В примере из условия Вова увидел на доске числа \(10\), \(16\) и \(19\). Если он напишет на доску между первым и вторым из них число \(13\), то в получившейся четверке чисел \(10~13~ 16~19\) разность между четвертым и третьим (\(19 - 16\)), третьим и вторым (\(16 - 13\)) и вторым и первым (\(13 - 10\)) окажется одна и та же, поэтому эта четверка будет арифметической прогрессией.