Алгоритмы

Знаменитый писатель Велепин очень продуктивен. Совсем недавно он подписал контракт с известным изданием, и теперь за \(i\)-й год ему нужно написать \(k_i\) романов. Для него это вообще не проблема: он может сколько угодно писать о самураях, космосе, пустоте, насекомых и оборотнях.

У него есть \(n\) постоянных читателей, каждый из которых в \(i\)-й год прочитает один из \(k_i\) романов, выпущенных Велепиным. Читатели очень любят обсуждать новинки, поэтому \(j\)-й из них будет доволен в течение года, если такой же роман, как и он, прочитают как минимум \(a_j\) человек, включая его самого.

Издание, с которым подписал контракт Велепин, очень современно: у него есть возможность контролировать, какое произведение прочитает каждый из поклонников. Оно не хочет издавать романы просто так, поэтому хотя бы один экземпляр каждого романа должен попасть в руки читателя. Издание надеется выиграть награду <<Издание \(q\)-летия>>, поэтому отдел маркетинга хочет узнать, какое максимальное количество постоянных читателей можно сделать довольными в течение каждого года, оптимально распределяя романы между ними. Так как в отделе маркетинга нет никого, кто мог бы это сделать, он обратился к вам за помощью.

Формат входных данных
В первой строке дано одно целое число \(n\) \((2 \leqslant n \leqslant 300\,000)\) — количество постоянных читателей Велепина.

Во второй строке дано \(n\) целых чисел \(a_1, a_2, \ldots, a_n\) \((1 \leqslant a_j \leqslant n)\) — количество людей, которые должны читать тот же роман, что и \(j\)-й, чтобы он был доволен.

В третьей строке дано одно целое число \(q\) (\(1 \leqslant q \leqslant 300\,000\)) — количество лет, которые нужно проанализировать.

В каждой из следующих \(q\) строк дано по одному целому числу \(k_i\) \((2 \leqslant k_i \leqslant n)\) — количество романов, которые Велепин должен написать в \(i\)-й год.

Формат выходных данных
Выведите \(q\) строк, в каждой из них ровно одно число — максимальное количество человек, которые могут быть довольны в \(i\)-й год, если Велепин выпустит \(k_i\) романов.

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

Как вы знаете, девочка Даша постоянно что-то ищет. На этот раз ей дали перестановку, и она хочет найти такой её подотрезок, что ни один из элементов на его концах не является ни минимумом, ни максимумом всего подотрезка. Более формально, вас просят найти такие числа \(l\) и \(r\) \((1 \leqslant l \leqslant r \leqslant n)\), что \(a_l \neq \min(a_l, a_{l + 1}, \ldots, a_r)\), \(a_l \neq \max(a_l, a_{l + 1}, \ldots, a_r)\) и \(a_r \neq \min(a_l, a_{l + 1}, \ldots, a_r)\), \(a_r \neq \max(a_l, a_{l + 1}, \ldots, a_r)\).

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

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

Формат входных данных
В первой строке входных данных вам дано одно целое число \(n\) (\(1 \leqslant n \leqslant 200\,000\)) — размер перестановки.

Во второй строке входных данных вам дано \(n\) целых чисел \(a_1, a_2, \ldots a_n\) (\(1 \leqslant a_i \leqslant n\)) — элементы перестановки.

Формат выходных данных
Если искомого подотрезка не существует, выведите \(-1\).

Иначе выведите такие два числа \(l\) и \(r\) \((1 \leqslant l \leqslant r \leqslant n)\), что \([a_l, a_{l + 1}, \ldots, a_r]\) удовлетворяет условиям задачи.

Если искомых подотрезков несколько, выведите любой из них.

Зимой обитателям Московского зоопарка очень скучно, в частности, это касается горилл. Вы решили развлечь их и принесли в зоопарк перестановку \(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\).

Квартира Максима еще не прошла реновацию, поэтому температура в ней сильно зависит от температуры на улице. Для поддержания комфортной температуры он купил обогреватель и установил систему <<Умный дом>>. В соответствующую программу Максим заложил два целых числа \(t_{min} \leq t_{max}\) и следующий алгоритм использования обогревателя:

1. Если в течение последних пяти дней до текущего дня включительно обогреватель каждый день был выключен, и в каждый из этих дней температура на улице была строго меньше \(t_{min}\), то надо включить обогреватель в этот день и считать, что он был включен весь день. Обогреватель остается включенным и в последующие дни до тех пор, пока программа его не выключит.

2. Если в течение последних пяти дней до текущего дня включительно обогреватель каждый день был включен, и в каждый из этих дней температура на улице была строго больше \(t_{max}\), то надо выключить обогреватель в этот день и считать, что он был выключен весь день. Обогреватель остается выключенным и в последующие дни до тех пор, пока программа его не включит.

Из-за кратковременного отключения электроэнергии программу необходимо настроить заново. Сами значения \(t_{min}\) и \(t_{max}\) Максим забыл, зато у него остались записи программы о температуре и состоянии обогревателя в каждые из \(n\) дней использования системы.

Максим помнит, что \(t_{min}\) и \(t_{max}\) были целыми числами, по модулю не превосходящими \(10^9\) и \(t_{min} \leq t_{max}\), также он помнит, что программа не учитывала дни до первого дня использования системы и не включала обогреватель в течение первых четырех дней. Наконец, Максим помнит, что он выбирал \(t_{min}\) и \(t_{max}\) как можно более близкими друг к другу.

Помогите найти два подходящих значения \(t_{min}\) и \(t_{max}\), не превосходящих \(10^9\) по абсолютной величине, таких, что выполняются правила использования обогревателя в каждые из \(n\) дней, \(t_{min}\) не превосходит \(t_{max}\) и величина \(t_{max} - t_{min}\) минимальна.

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

Формат входных данных
В первой строке задано целое число \(n\) (\(5 \leq n \leq 10^5\)) — количество дней, в течение которых работала система.

Во второй строке входных данных задаются \(n\) целых чисел \(t_1, \dots, t_n\) (\(-10^9 \leq t_i \leq 10^9\)) — температуры на улице в каждый из \(n\) дней.

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

Формат выходных данных
В единственной строке выведите два целых числа \(t_{min}\) и \(t_{max}\) (\(t_{min} \leq t_{max}\)), по модулю не превосходящих \(10^9\) — значения температур, при вставке которых в программу обогреватель будет включен и выключен в те же дни, в которые он был включен и выключен при исходных значениях, а значение \(t_{max} - t_{min}\) минимально.

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

В первом тестовом примере первые пять дней температура строго меньше \(7\) градусов, при этом до пятого дня обогреватель был в каждый из четырех дней выключен, следовательно в пятый день программа его включила. На данный тест корректен любой ответ удовлетворяющий условию \(6 \leq t_{min} = t_{max} \leq 10^9\).

В развлекательном центре Е-города был установлен игровой автомат нового поколения. В автомат можно бросить монету и следить за её продвижением сверху вниз по разветвляющемуся лабиринту из трубок. В лабиринте есть \(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:

Алина выписала на доске \(n + 1\) цифру, каждая из которых от \(1\) до \(9\). Даша поставила между каждой парой соседних цифр знак одной из арифметических операций <<+>>, <<->>, <<*>> и <</>> (плюс, минус, умножить, целочисленное деление). Затем девочки отправились в столовую на обед.

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

Они просят вас зная последовательность знаков, расставить цифры от \(1\) до \(9\) между ними так, чтобы итоговый результат был минимальным.

Формат входных данных
В первой строке входного файла дано число \(n\), число знаков, которые написала Даша (\(1 \le n \le 1000\)).

Во второй строке находится \(n\) знаков арифметических операций <<+>>, <<->>, <<*>> и <</>> (без кавычек).

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

Если возможных решений несколько, разрешается вывести любое.

После того как Данил сдал всю сессию на 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), без кавычек).

 

Поле в игре <<Речной бой>> представляет собой полоску длины \(n\) клеток и шириной в одну клетку. Где-то на поле расположен корабль из \(k\) клеток (\(k \le n\)). Какое наименьшее число выстрелов необходимо, чтобы гарантированно потопить корабль? После каждого выстрела сообщается его результат: <<мимо>>, <<ранен>> или <<убит>>.

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

Вторая строка входных данных содержит целое число \(k\) (\(1 \le k \le n\)).

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

Замечание

В первом примере поле состоит из \(n=4\) клеток, корабль имеет длину \(k=2\). Первый выстрел нужно сделать в одну из двух центральных клеток. Если результатом будет <<ранен>>, то вторая клетка корабля находится в одной из двух соседних клеток, и за два выстрела мы гарантированно потопим корабль Если результатом первого выстрела будет <<мимо>>, то корабль занимает две единственные свободные смежные клетки, которые тоже можно подбить двумя выстрелами. Итого нужно 3 выстрела. Двух выстрелов недостаточно, так как всегда есть шанс промахнуться первым выстрелом.

Всего во Флатландии \(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\).

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

Дети с интересом восприняли идею и вырезали из бумаги \(a\) звездочек и \(b\) снежинок. Теперь они планируют отправить их Санте Клаусу по почте. Им так понравились вырезанные ими украшения, что они, возможно, решат оставить себе часть. Таким образом, дети могут отправить Санте \(x\) звездочек и \(y\) снежинок, где \(0 \le x \le a\) и \(0 \le y \le b\). Чтобы Санта не расстроился, дети должны отправить ему хотя бы одно украшение. То есть должно выполняться также условие \(x + y > 0\).

Чтобы все олени выглядели красиво, на каждом должно оказаться одинаковое количество украшений. Известно, что у Санты \(n\) оленей, поэтому если будут отправлены \(x\) звездочек и \(y\) снежинок, величина \(x+y\) должна делиться на \(n\).

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

Формат входных данных

В одном наборе входных данных содержатся несколько тестов. Каждый тест следует решить независимо.
Первая строка входных данных содержит целое число \(t\) — количество тестов (\(1 \le t \le 10^5\)).

Следующие строки описывают тесты, по одному на строке. Описание теста состоит из трех целых чисел \(n\), \(a\) и \(b\) — количество оленей у Санты, количество звездочек и количество снежинок, вырезанных детьми (\(4 \le n \le 10^9\); \(0 \le a, b \le 10^9\)).

Формат выходных данных
Выведите \(t\) чисел. Для каждого теста выведите одно число: количество способов составить посылку для Санты Клауса.

Замечание
В первом тесте у Санты \(4\) оленя, а дети вырезали \(2\) звездочки и \(2\) снежинки. Здесь подходит только один набор — нужно отправить все вырезанные украшения.

Во втором тесте у Санты также \(4\) оленя, но дети вырезали \(4\) звездочки и \(4\) снежинки. Здесь подходит 6 наборов: 0 звездочек и 4 снежинки, 1 звездочка и 3 снежинки, 2 звездочки и 2 снежинки, 3 звездочки и 1 снежинка, 4 звездочки и 0 снежинок, а также 4 звездочки и 4 снежинки.

Тимофей готовится к ЕГЭ. Для отработки навыка скорости и точности поиска ответов на задания по теме «Системы счисления» ему часто приходится решать примеры типа «сколько значащих нулей (или единиц) содержит двоичная запись значения выражения 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.

На доске написано число \(n\), с которым несколько раз производят следующую операцию: если в записи числа на доске есть хотя бы одна нечётная цифра, то очередной мальчик вычитает из него 1, в противном случае — делит на 2. Сколько мальчиков нужно вызвать, чтобы на доске получился ноль?

Формат входных данных
Единственная строка входного файла содержит натуральное число \(n\) (\(1 \le n \le 10^{18}\)).

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

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

 

В примере дано \(n = 25\). Число имеет в своей записи нечётную цифру \(5\), поэтому после первой операции \(n\) уменьшится на \(1\) и станет равно \(24\).

Число \(24\) не имеет в своей записи нечётных цифр, поэтому после второй операции \(n\) уменьшится в \(2\) раза и станет равно \(12\).

Далее \(n\) будет принимать значения: \(11\), \(10\), \(9\), \(8\), \(4\), \(2\), \(1\) и \(0\). Всего потребуется \(10\) операций.

Ипполит Матвеевич Воробьянинов ходит вдоль улицы из \(n\) домов, пронумерованных числами от \(1\) до \(n\), и расклеивает афиши. Сначала он наклеил афиши на каждый дом, номер которого делился без остатка на \(a\). Поскольку афиш осталось еще много, вторым проходом он наклеил афиши на каждый дом, номер которого делился без остатка на \(b\). При этом, если на доме уже была наклеена афиша, новую Воробьянинов не клеил. Сколько всего афиш расклеил бывший предводитель дворянства?

Формат входных данных
Три строки содержат три натуральных числа: \(n\) — количество домов на улице, \(a\) и \(b\) — выбранные Воробьяниновым числа. Все числа не превосходят \(10^9\).

Формат выходных данных
Выведите одно неотрицательное целое число — количество расклеенных афиш.

Замечание
В первом примере на улице \(10\) домов. Ипполит Матвеевич первым проходом расклеил пять афиш на дома, номера которых делятся на \(2\), то есть на дома с номерами \(2\), \(4\), \(6\), \(8\), \(10\). Вторым проходом он расклеил две афиши на дома, номера которых делятся на \(3\), то есть на дома с номерами \(3\) и \(9\). Дом номер \(6\) он пропустил — на нем афиша уже висит. Всего наклеено \(7\) афиш.

Во втором примере Воробьянинов не наклеит ни одной афиши.

Кай работает в лаборатории изучения массивов, он экспериментирует с двумя массивами натуральных чисел: \(A = [a_1, a_2, \ldots, a_n]\) длины \(n\) и \(B = [b_1, b_2, \ldots, b_m]\) длины \(m\).

Эксперимент, который проводит Кай, устроен следующим образом. У каждого из массивов отбрасывается произвольный, возможно пустой, префикс, а также произвольный, возможно пустой, суффикс, таким образом, чтобы оставшиеся части массивов имели равную длину. Обозначим получившиеся массивы как \(A'\) и \(B'\), а их длину как \(k\). Затем Кай суммирует поэлементно получившиеся массивы, итоговый массив Кай обозначает как \(C = [c_1, c_2, \ldots, c_k]\).

Пусть, например, \(n = 5\), \(A = [4, 3, 3, 2, 1]\), \(m = 6\), \(B = [4, 1, 5, 1, 3, 2]\), от массива \(A\) отбрасывается первый и последний элемент, от массива \(B\) три первых. После этого массивы имеют вид \(A' = [3, 3, 2]\), \(B' = [1, 3, 2]\), результат их поэлементного суммирования \(C = [4, 6, 4]\).

Задача Кая заключается в том, чтобы получать такие \(C\), которые являются массивами-палиндромами, то есть если числа на первой и последней позиции совпадают, числа на второй и предпоследней позиции совпадают, и так далее, для всех \(i\) числа на позициях \(i\) и \(k - i + 1\) совпадают.

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

Формат входных данных
В первой строке ввода даны два целых числа \(n\) и \(m\) — количество элементов в первом и во втором массиве, соответственно (\(1 \leqslant n, m \leqslant 100\,000\)).

Во второй строке ввода даны \(n\) целых чисел \(a_{i}\) — массив \(A\) (\(1 \leqslant a_i \leqslant 100\)).

В третьей строке ввода даны \(m\) целых чисел \(b_{j}\) — массив \(B\) (\(1 \leqslant b_j \leqslant 100\)).

Формат выходных данных
Выведите единственное целое число — максимальное \(k\), что Кай в результате эксперимента может получить массив-палиндром длины \(k\).

 

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

Треугольники не должны пересекаться, в объединении они должны давать треугольник. Ровно по одному из выбранных треугольников должны находиться в углах, а один треугольник должен располагаться в центре.

Треугольники лежат на столе, их можно свободно вращать и двигать, но нельзя зеркально отражать.

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

Формат входных данных
В первой строке дано одно целое число \(t\) — номер теста.

В второй строке дано одно целое число \(n\) — количество треугольников в головоломке (\(4 \le n \le 30\)).

В следующих \(n\) строках дано описание треугольников. Один треугольник описывается координатами трех своих углов, данных в порядке обхода треугольника против часовой стрелки. Все координаты целые и по модулю не превышают \(10^5\). Гарантируется, что треугольники не являются вырожденными. В исходном расположении треугольники могут пересекаться.

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

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

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

Во втором примере все треугольники имеют одинаковую форму прямоугольного треугольника с длинами катетов равными \(1\). Из любых четырех треугольников можно собрать один.

Председатель жюри чемпионата по устному счету Иван Владимирович Треугольников придумал новое задание для участников чемпионата. Исходно на доске выписывается \(n\) целых чисел: \(a_1, a_2, \ldots, a_n\). После этого участник должен выполнять команды двух типов:

1. Стереть \(i\)-е число с доски и записать вместо него число \(x\). То есть, если на доске были записаны числа \(a_1, a_2, \ldots, a_n\), то после выполнения команды числа будут равны: \(a_1, \ldots, a_{i - 1}, x, a_{i + 1}, \ldots, a_n\).

2. Циклически сдвинуть последовательность чисел на \(k\) вправо. То есть, если на доске были записаны числа \(a_1, a_2, \ldots, a_n\), то после выполнения команды числа будут равны: \(a_{n - k + 1}, a_{n - k + 2}, \ldots, a_n, a_1, a_2, \ldots, a_{n - k}\).

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

Формат входных данных
В первой строке записано целое число \(n\) — количество чисел, изначально записанных на доске (\(2 \leq n \leq 10^5\)).

Во второй строке через пробел записаны \(n\) целых чисел: \(a_1, a_2, \ldots, a_n\) — числа, изначально выписанные на доске (\(-10^9 \leq a_i \leq 10^9\)).

В третьей строке записано целое число \(q\) — количество команд, которые необходимо выполнить (\(1 \leq q \leq 10^5\)).

В каждой из следующих \(q\) строк записана очередная команда в следующем формате:

• \(1~i~x\) — это означает, что участник должен заменить \(i\)-е число последовательности на число \(x\) (\(1 \leq i \leq n\); \(-10^9 \leq x \leq 10^9\)).

• \(2~k\) — это означает, что участник должен циклически сдвинуть последовательность чисел на \(k\) вправо (\(1 \leq k < n\)).

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

В \(i\)-й строке должна быть записана сумма чисел на доске после выполнения первых \(i\) команд.

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

Замечание
Рассмотрим пример из условия. Изначально последовательность записанных на доске чисел равна: \(4,~1,~2,~1,~5,~3\).

После первой команды последовательность циклически сдвигается на \(3\) элемента вправо. Новая последовательность: \(1,~5,~3,~4,~1,~2\). Сумма чисел равна: \(1 + 5 + 3 + 4 + 1 + 2 = 16\).

После второй команды необходимо заменить третий элемент последовательности на число \(10\). Новая последовательность: \(1,~5,~10,~4,~1,~2\). Сумма чисел равна: \(1 + 5 + 10 + 4 + 1 + 2 = 23\).

После третьей команды заменить четвертый элемент на число \(4\). Так как четвертый элемент уже равен \(4\), последовательность не изменяется. Сумма чисел также равна \(23\).

После четвертой команды последовательность циклически сдвигается на \(1\): \(2,~1,~5,~10,~4,~1\). Сумма чисел не изменилась.

Наконец, после пятой команды последовательность становится равна: \(-10,~1,~5,~10,~4,~1\). Сумма чисел в итоговой последовательности равна \(-10 + 1 + 5 + 10 + 4 + 1 = 11\).

Профессор Селезнев передает Алисе зашифрованную информацию, которая представляет собой последовательность целых чисел.  Все числа данной последовательности не превышают 10⁷. Каждое число передается в течении одной секунды. Чтобы понять, что данные переданы правильно, Алисе необходимо определить контрольное значение, которое вычисляется по следующему правилу,
- берутся три переданных значения из последовательности таким образом, чтобы между какими-либо двумя моментами передачи прошло ровно K секунд;
- вычисляется сумма выбранных чисел, которая должна быть минимальной. Данная сумма является контрольным значением.
Помогите Алисе определить контрольное значение.


Формат входных данных
В первой строке записано количество чисел N (1 ≤ N ≤ 2·105) и целое число K (1 ≤ K < 105, K < N). Каждая из следующих N строк содержит одно целое число, по модулю не превышающее 107.


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