Информатика

Напишите программу, которая выполняет глобальное выравнивание двух ДНК-последовательностей, и выводит все выравнивания и их score (балл).

Формат входных данных
Две строки содержит две последовательности ДНК, далее вводятся настройки параметров:

• Балл за совпадение
• Балл за несовпадение
• Балл за открытие гэпа
• Балл за продолжение гэпа

Формат выходных данных
Выведите все выравнивания и их score (балл).

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

Формат входных данных
Первая строка входных данных содержит целое число n (1 ≤ n ≤ 2 · 10⁵ ) — количество мест в ряду.
Вторая строка содержит целое число k (1 ≤ k ≤ n) — количество приходящих людей.
Третья строка содержит строку s длины n, состоящую из символов «0» и «1» и задающую первоначальную рассадку. Занятые места обозначаются единицами, пустые — нулями. Гарантируется, что в строке s содержится не менее k нулей.
Формат выходных данных
Программа должна вывести k чисел — номера выбранных мест в порядке прихода новых людей.

Замечание
В первом примере первоначально заняты места 1, 2 и 6 (рисунок А).
Если первый пришедший будет двигаться с левой стороны ряда, он пройдёт мимо 1 и 2 места, прежде чем доберётся до свободного места с номером 3. Если же он будет двигаться с правой стороны ряда, то ему понадобится пройти мимо одного места с номером 6, после чего он сможет занять место 5. Именно это место он и выберет (рисунок Б).
Второй пришедший может занять либо место с номером 3, двигаясь с левой стороны и проходя мимо двух занятых мест 1 и 2, либо место с номером 4, двигаясь с правой стороны и проходя мимо двух занятых мест 6 и 5. Поскольку в обоих случаях ему нужно пройти мимо двух занятых мест, он будет двигаться с левой стороны и займёт место с номером 3.
Во втором примере в ряду 6 мест, второе и пятое места изначально уже заняты, заходят ещё 3 человека. Первый заходящий человек будет выбирать между первым и шестым местами, заходя с левого или правого края соответственно. В обоих случаях ему придётся пройти мимо нуля занятых мест, поэтому он решит зайти слева и сесть на 1 место. Второй человек будет выбирать между третьим и шестым местами. В первом случае ему придётся идти мимо двух занятых мест, во втором — мимо нуля, поэтому он выберет зайти справа — 6 место. Третий человек будет выбирать между третьим и четвертым местами. В обоих случаях ему придётся пройти мимо двух занятых мест, поэтому он выберет зайти слева — 3 место.

Фотографа попросили сделать фотосессию группы детей для выпускного альбома в детском саду. В числе прочих, он должен сделать групповой снимок, на котором должны присутствовать все дети одновременно. Фотограф считает, что для красивой фотографии группы требуется очень тщательно расставить детей в кадре. В частности, с его точки зрения, группа должна расположиться как можно компактнее по ширине, то есть количество людей в самом длинном ряду на фотографии должно быть как можно меньше.
Для гармоничного расположения детей фотограф размещает детей не более чем в четыре ряда. Девочек он располагает либо во втором ряду, сидящими на стульчиках, либо стоящими в третьем ряду. Мальчиков он размещает либо в первом ряду, сидящими на корточках, либо в четвёртом ряду, стоящими на стульчиках. Группа состоит из a мальчиков и b девочек. В студии есть стулья в количестве c штук. Какие-то ряды могут быть пустыми. Все стулья использовать не обязательно.
По заданным числам a, b и c требуется определить, какого наименьшего по ширине расположения группы сможет добиться фотограф.
Формат входных данных
Программа получает на вход три целых неотрицательных числа a, b и c, записанных в отдельных строках — количество мальчиков, девочек и стульев соответственно. Все числа не превосходят 10¹⁸ .
Обратите внимание, что значения переменных в этой задаче могут превышать возможные значения 32-битной целочисленной переменной, поэтому необходимо использовать 64-битные целочисленные типы данных (тип int64 в языке Pascal, тип long long в C++, тип long в Java и C#).
Формат выходных данных
Вывести одно целое число — минимальную ширину группы, которую сможет организовать фотограф.

Замечание
Во всех примерах в условии группа состоит из 9 мальчиков и 15 девочек.
В первом примере стульев нет, поэтому все девочки стоят, все мальчики сидят на корточках, общая ширина группы 15.
Во втором примере есть 4 стула. Можно посадить 4 девочек во втором ряду на эти стулья, остальные 11 девочек будут стоять в третьем ряду. Все мальчики будут сидеть на корточках в первом ряду. Общая ширина группы 11.
В третьем примере есть 7 стульев. Тогда есть два способа получить группу ширины 9. Например, можно посадить на все стулья девочек, тогда в первом ряду будет 9 мальчиков, во втором ряду будет 7 девочек, в третьем ряду 8 девочек. Либо можно посадить на стулья 6 девочек и поставить одного мальчика в четвёртый ряд. Тогда получим 8 мальчиков в первом ряду, 6 девочек во втором, 9 девочек в третьем и 1 мальчика в четвёртом. В любом из этих двух случаев ширина группы равна 9.
В четвёртом примере стульев много и есть несколько способов организовать группу ширины 8. Один из способов такой: посадим на корточки 4 мальчика в первом ряду, далее посадим 8 девочек на стулья во втором ряду, оставшиеся 7 девочек встанут в третьем и 5 мальчиков поставим на стульчики в четвёртом.

Аполлинария Прокофьевна и Белла Прокофьевна — две сестры-пенсионерки. Аполлинарии Прокофьевне каждый день необходимо принимать одну таблетку от забывчивости. К сожалению, этот режим она не соблюдает и вспоминает о лекарстве только раз в a дней (то есть приняв лекарство сначала в первый день, в следующий раз она примет его в день номер 1 + a). Белле Прокофьевне каждый день необходимо принимать одну таблетку от жадности. Ко всеобщему огорчению, и её болезнь сильнее лекарства, поэтому каждый день она глотает b таблеток. Внешне эти таблетки выглядят совершенно одинаково и каждая из сестёр считает, что вот этот пузырёк с n пилюлями именно её. На сколько дней им хватит этого количества лекарств?

Формат входных данных
Три строки входных данных содержат три целых числа a, b (1 ≤ a, b ≤ 100) и n (1 ≤ n ≤ 10¹⁸).
Обратите внимание, что значения переменных в этой задаче могут превышать возможные значения 32-битной целочисленной переменной, поэтому необходимо использовать 64-битные целочисленные типы данных (тип int64 в языке Pascal, тип long long в C++, тип long в Java и C#).
Формат выходных данных
Программа должна вывести одно число — ответ на задачу.

Замечание
В первом примере Аполлинария Прокофьевна принимает по одной таблетке раз в два дня (начиная с первого), Белла Прокофьевна принимает по три таблетки каждый день. В пузырьке 12 таблеток.
В первый день Аполлинария принимает одну таблетку, а Белла — три. В пузырьке осталось восемь пилюль.
Во второй день Аполлинария забывает принять таблетку, а Белла опять съедает три. В пузырьке осталось пять пилюль.
В третий день Аполлинария принимает одну таблетку, а Белла — три. В пузырьке осталась последняя пилюля, ещё на один день этого количества сёстрам не хватит.
Во втором примере начального количества таблеток не хватит даже на один день.

Успешно решив раньше времени контрольную работу по математике, Тимофей выбрал на клетчатой бумаге квадрат со стороной n клеток и стал заполнять его «змейкой» от левого верхнего угла так, как показано на рисунке. Определите длину проведённых линий.

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

В разведывательное управление доставили сейф с секретной информацией, кодовый замок на котором открывается комбинацией из n цифр, каждая цифра может принимать b различных значений от 0 до b − 1. Код неизвестен, однако разведчики передали несколько донесений о том, что сумма цифр кода в некоторых заданных позициях равна какому-то известному числу. Используя информацию из всех полученных донесений, определите, сколько существует возможных кодов, удовлетворяющих этим условиям.

Формат входных данных
Первая строка входных данных содержит число b — количество различных значений одной цифры кода, 2 ≤ b ≤ 10. Вторая строка содержит число n — количество цифр в коде, n \(\geq\) 1, bⁿ ≤ 60 000. Третья строка содержит число t – количество имеющихся донесений о сумме каких-то цифр кода, t \(\geq\) 1.
Следующие 2t строк содержат информацию об имеющихся донесениях. Каждое донесение состоит из двух строк. Первая из этих строк («маска цифр») содержит n символов, записанных слитно и равных «0» или «1», где цифра «1» обозначает, что в донесении говорится об этой цифре кода. Например, маска цифр «01011» означает сумму цифр, стоящих в коде на 2-й, 4-й и 5-й позициях. Во второй строке донесения записано число s, равное сумме цифр кода, стоящих на данных позициях. Гарантируется, что каждая маска цифр содержит хотя бы одну единицу и что все маски цифр различаются. Общее число донесений может быть любым, удовлетворяющим этим условиям.

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

Замечание
В примере из условия каждая цифра кода может принимать 8 различных значений от 0 до 7, код состоит из 3 цифр. Получены 2 донесения, из первого донесения известно, что сумма первой и второй цифры кода равна 7, из второго донесения известно, что сумма второй и третьей цифры кода равна 12. Существуют 3 кода, удовлетворяющие этим условиям: «075», «166», «257».

У Маши есть прямоугольная шоколадка, состоящая из m × n квадратных долек. Маша хочет разделить эту шоколадку между своими друзьями, разломив шоколадку по линиям на k кусочков, то есть каждому другу достанется прямоугольный кусочек шоколадки. У Юры сегодня день рождения, поэтому Маша хочет разделить шоколадку так, чтобы Юре достался самый большой кусок (содержащий как можно больше долек). Определите число долек в этом куске.

Формат входных данных
Программа получает на вход три натуральных числа, каждое в отдельной строке: m, n и k. Все числа — целые положительные, при этом m и n не превосходят 10⁶ , а k ≤ mn.
Обратите внимание на то, что значение mn, а, значит, и значение k в этой задаче может превышать возможное значение 32-битной целочисленной переменной, поэтому необходимо использовать 64-битные целочисленные типы данных (тип int64 в языке Pascal, тип long long в C++, тип long в Java и C#).
Формат выходных данных
Программа должна вывести одно целое число — максимально возможное количество долек в том прямоугольном куске, который получит Юра.

Замечание
В примере из условия нужно разделить шоколадку 4 × 5 на 4 кусочка. Самый большой кусочек будет состоять из 16 долек, как показано на картинке.
 

Красная Шапочка отправилась на болото для сбора клюквы, чтобы испечь пирожки для бабушки. Клюквенное болото представляет собой координатную прямую. Берег, на котором стоит девочка, имеет координату 0, а клюквенная поляна — координату N + 1. В точках с координатами 1, 2, . . . , N расположены кочки. Первоначально у девочки E единиц энергии. Красная Шапочка может прыгнуть из точки x в точку y (x < y), потратив на это (y − x) единиц энергии, то есть затраченная энергия равна расстоянию между кочками. После того, как девочка приземлится на кочке с координатой i, она получает ai единиц энергии (при этом значение ai может оказаться отрицательным, тогда энергия Красной Шапочки уменьшится при приземлении). Нельзя, чтобы энергия Красной Шапочки в какой-либо момент оказалась меньше нуля. Например, Красная Шапочка не может прыгнуть с кочки 1 на кочку 3, имея одну единицу энергии, вне зависимости от того, сколько энергии она получит на 3-й кочке, так как для осуществления такого прыжка необходимо две единицы энергии.
Так как Красной Шапочке ещё надо вернуться обратно, девочке интересно, какое максимальное количество энергии у неё может оказаться, когда она достигнет поляны (точки с координатой N +1).

Формат входных данных
Первая строка входных данных содержит целое число E — первоначальный запас энергии Красной Шапочки, 1 ≤ E ≤ 10⁹ . Вторая строка входных данных содержит целое число N — количество кочек на болоте, 1 ≤ N ≤ 10⁵ . Следующие N строк содержат по одному целому числу a_i — энергия, которую получает Красная Шапочка на i-й кочке, −2000 ≤ a_i ≤ 2000.
Формат выходных данных
Программа должна вывести одно число — максимальное количество единиц энергии, которое останется у Красной Шапочки после достижения клюквенной поляны. Если девочка не сможет достигнуть цели, выведите одно число «-1» (без кавычек).

Замечание
В первом примере три кочки и первоначально 2 единицы энергии у Красной Шапочки. Она прыгает на кочку 1, что требует 1 единицу энергии, и у неё остаётся 1 единица энергии. На кочке 1 девочка получает 1 единицу энергии, и у неё становится 2 единицы энергии. Затем она прыгает с кочки 1 на кочку 3, потратив 2 единицы энергии, и у неё становится 0 энергии. Приземлившись на кочку 3, Красная Шапочка получает 1 единицу энергии, этого достаточно, чтобы перепрыгнуть с кочки 3 на поляну в точке 4, после чего у Красной Шапочки останется 0 единиц энергии.
Во втором примере у Красной Шапочки первоначально только 1 единица энергии, поэтому она может прыгнуть только на кочку 1, но значение a1 = −1, то есть после приземления на кочку 1 у Красной Шапочки энергия станет отрицательной, и она не сможет продолжить свой путь.

Из нижеприведенных правил выберите правило с наибольшим приоритетом:

1) section.intro p:first-of-type
2) #content .text
3) p::first-letter
4) body > div

Из нижеприведенных правил выберите правило с наибольшим приоритетом:

1) a.button:hover
2) nav > ul li
3) #menu .item
4) *

В файле приведён фрагмент базы данных «Кондитерские изделия» о поставках товаров в магазины районов города. База данных состоит из трёх таблиц.

Таблица «Движение товаров» содержит записи о поставках товаров в магазины в течение первой половины июня 2023 г., а также информацию о проданных товарах. Поле Тип операции содержит значение Поступление или Продажа, а в соответствующее поле Количество упаковок, шт. внесена информация о том, сколько упаковок товара поступило в магазин или было продано по итогам дня.
Таблица «Товар» содержит информацию об основных характеристиках каждого товара. 
Таблица «Магазин» содержит информацию о местонахождении магазинов.
На рисунке приведена схема указанной базы данных.

Испольщуя информацию из приведённой базы данных, определите общую масу (в кг) всех видов пастилы, проданных магазинами на улице Металлургов за период с 9 по 20 августа включительно. В ответе запишите целую часть полученного числа.

Файл к заданию

Логическая функция F задаётся выражением  На рисунке приведён частично заполненный фрагмент таблицы истинности функции F, содержащий неповторяющиеся строки. Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных x, y, z, w. 

?	?	?	?	F
0			1	0
	1			0
1	0			0

В ответе напишите буквы x, y, z, w в том порядке, в котором идут соответствующие им столбцы. Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.

 

На рисунке справа схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о длинах этих дорог (в километрах). Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе.

Дано натуральное число N. Фрагмент алгоритма 

int M, N;
cin >> N;
M = 0;
while (N != 0) {
    if ((N % 10) % 2 != 0) M++;
    N = N / 10;
}
cout << M;

1. находит количество четных цифр в числе;

2. находит количество нечетных цифр в числе;

3. находит сумму четных цифр числа;

4. находит произведение нечетных цифр числа.

В известной школе прошёл урок физкультуры. Как полагается, всех построили в шеренгу и попросили рассчитаться на <<первый–\(k\)-й>>, где \(k > 1\).

Как известно, расчёт на <<первый–\(k\)-й>> происходит следующим образом: первые \(k\) человек имеют номера \(1, 2, 3, \ldots, k\), следующие \(k - 1\) человек имеют номера \(k - 1, k - 2, \ldots, 1\), следующие \(k - 1\) человек имеют номера \(2, 3, \ldots, k\) и т.д. Таким образом, расчёт повторяется через каждые \(2k - 2\) позиции. Примеры расчёта приведены в разделе <<Замечание>>.

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

Обратите внимание, что не существует расчёта для \(k = 1\).

Формат входных данных
Первая строка содержит одно целое число \(n\) (\(2 \leq n \leq 10^9\)) — позиция Васи в ряду в нумерации, начинающейся с \(1\).

Вторая строка содержит одно целое число \(x\) (\(1 \leq x < n\)) — номер, который Вася получил при расчёте.

Формат выходных данных
Выведите единственное целое число — количество различных \(k > 1\), которые подходят под данные ограничения.

Можно доказать, что при данных ограничениях ответ является конечным.

Примечание
В первом примере подходят \(k\) равные \(2, 3, 5, 6\).

Пример расчёта для этих \(k\):

Аня занимается рукоделием. Сегодня она решила связать платок из полупрозрачных ниток. Каждая нитка характеризуется единственным целым числом — коэффициентом прозрачности.

Платок делается по следующей схеме: выбираются горизонтальные нитки с коэффициентами прозрачности \(a_1, a_2, \ldots, a_n\) и вертикальные с коэффициентами прозрачности \(b_1, b_2, \ldots, b_m\). Затем они переплетаются между собой, как показано на картинке снизу, и образуют кусок ткани размера \(n \times m\), состоящий ровно из \(nm\) узлов:

После того, как сплетение затянется и не будет видно зазоров между нитками, каждый узел, образованный горизонтальной ниткой с номером \(i\) и вертикальной ниткой с номером \(j\), превратится в клетку, которую мы будем обозначать как \((i, j)\). Клетка \((i, j)\) будет иметь коэффициент прозрачности \(a_i + b_j\).

\(^{\dagger}\)Подквадратом куска ткани называется множество всех его клеток \((i, j)\), таких что \(x_0 \le i \le x_0 + d\) и \(y_0 \le j \le y_0 + d\) для некоторых целых чисел \(x_0\), \(y_0\) и \(d\) (\(1 \le x_0 \le n - d\), \(1 \le y_0 \le m - d\), \(d \ge 0\)).

Интересностью полученного платка будем называть количество его подквадратов\(^{\dagger}\), в которых нет пары соседних по горизонтали или по вертикали клеток с одинаковыми коэффициентами прозрачности.

Аня ещё не решила, из каких ниток плести платок, поэтому вам будут даны также \(q\) запросов изменения коэффициентов прозрачности ниток на некотором отрезке, после каждого из которых надо вывести интересность полученного платка.

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

Вторая строка содержит \(n\) целых чисел \(a_1, a_2, \ldots, a_n\) (\(-10^9 \le a_i \le 10^9\)) — коэффициенты прозрачности для горизонтальных ниток, нитки пронумерованы сверху-вниз.

Третья строка содержит \(m\) целых чисел \(b_1, b_2, \ldots, b_m\) (\(-10^9 \le b_i \le 10^9\)) — коэффициенты прозрачности для вертикальных ниток, нитки пронумерованы слева-направо.

В последующих \(q\) строках указаны запросы изменения. Каждый из запросов описывается четверкой целых чисел \(t\), \(l\), \(r\) и \(x\) (\(1 \le t \le 2\), \(l \le r\), \(-10^9 \le x \le 10^9\)). В зависимости от параметра \(t\) в запросе требуется сделать следующее:

• \(t=1\). Коэффициенты прозрачности для горизонтальных ниток на отрезке \([l, r]\) увеличиваются на \(x\) (иными словами, для всех целых \(l \le i \le r\) значение \(a_i\) увеличивается на \(x\));

• \(t=2\). Коэффициенты прозрачности для вертикальных ниток на отрезке \([l, r]\) увеличиваются на \(x\) (иными словами, для всех целых \(l \le i \le r\) значение \(b_i\) увеличивается на \(x\)).

Формат выходных данных
Выведите \((q+1)\) строку. В \((i + 1)\)-й строке (\(0 \le i \le q\)) выведите одно целое число — интересность платка после применения первых \(i\) запросов.

Примечание
В первом примере коэффициенты прозрачности клеток в получившемся платке равны:

Тогда есть следующие подквадраты, не содержащие двух соседних по вертикали или по горизонтали клеток с одинаковым коэффициентом прозрачности:

• Каждая из \(16\) клеток по отдельности;

• Подквадрат с левым верхним углом в клетке \((3, 1)\) и правим нижним углом в клетке \((4, 2)\);

• Подквадрат с левым верхним углом в клетке \((2, 3)\) и правим нижним углом в клетке \((3, 4)\);

• Подквадрат с левым верхним углом в клетке \((2, 1)\) и правым нижним углом в клетке \((3, 2)\);

• Подквадрат с левым верхним углом в клетке \((3, 3)\) и правим нижним углом в клетке \((4, 4)\).

Во втором примере после первого запроса коэффициенты прозрачности горизонтальных ниток равны \([1, 2, 2]\). После второго запроса коэффициенты прозрачности вертикальных ниток равны \([2, -4, 2]\).

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

Промоделируем тур олимпиады. Пусть на туре предложено \(n\) задач, \(i\)-я задача состоит из \(k_i\) подзадач, \(j\)-я подзадача \(i\)-й задачи приносит \(c_{i, j}\) баллов. Зависимостей между подзадачами нет, поэтому можно в каждой задаче выбрать любое множество подзадач и его решить. При этом нельзя выбрать пустое множество, ведь тогда по задаче будет \(0\) баллов, а это противоречит главному правилу написания личных олимпиад.

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

Первая строка содержит два целых числа \(n\), \(s\) (\(1 \le n \le 100\,000\), \(1 \le s \le 100\,000\)) — количество задач в контесте и необходимую сумму баллов, соответственно. Далее следуют описания задач. Описание каждой задачи состоит из двух строк.

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

Вторая строка описания \(i\)-й задачи содержит \(k_i\) целых чисел \(c_{i, 1}, c_{i, 2}, \ldots, c_{i, k_i}\) (\(1 \le c_{i, j} \le 100\,000\)) — баллы за подзадачи.

Гарантируется, что сумма \(k_1+k_2+\ldots+k_n\) по всем задачам не превосходит \(100\,000\).

Гарантируется, что произведение \((k_1+k_2+\ldots+k_n)\cdot s\) не превосходит \(10^7\).

Формат выходных данных
Если решения не существует, выведите <<No>>.

В противном случае в первой строке выведите <<Yes>>. Далее необходимо вывести описание решенных подзадач для каждой задачи.

Описание \(i\)-й задачи начинается с целого числа \(m_i\) (\(1 \le m_i \le k_i\)) — количества решенных подзадач \(i\)-й задачи. Далее следуют \(m_i\) различных целых чисел \(p_{i, 1}, p_{i, 2}, \ldots, p_{i, m_i}\) (\(1 \le p_{i, j} \le k_i\)) — номера решенных подзадач в \(i\)-й задаче.

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

На доске были выписаны два квадрата натуральных чисел: \(x^2\) и \(y^2\), где \(l \le y^2 < x^2 \le r\). Числа \(x^2\) и \(y^2\) стерли и выписали на доске их разность \(d\).

По заданным \(l\), \(r\) и \(d\) выясните, сколько различных пар натуральных чисел \(x^2, y^2\) могло быть выписано на доске.

Формат выходных данных
В первой строке даны три числа \(d\), \(l\) и \(r\) (\(1 \le d \le 10^9, 1 \le l \le r \le 10^{18}\)).

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

Примечание
В первом примере подходят числа 100 и 36. Во втором примере также подходят числа 256 и 196.

Для поиска полезных ископаемых ученые разработали специальный сканер.

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

Сканер работает следующим образом: он может быть запущен в столбце \(p\) и возвращает количество клеток в зоне сканирования, которые содержат полезные ископаемые. Зона сканирования включает все клетки столбца \(p\), верхние \(k-1\) клетку столбца \(p-1\), верхние \(k-2\) клетки столбца \(p-2\), и так далее. На рисунке показана зона сканирования для поля с \(k = 3\), \(n=5\) и всех значений \(p\).

Вам даны значения, которые вернул сканер для всех \(p\), обозначим за \(b_p\) значение в столбце \(p\). Будем называть таблицу, где для каждой клетки определено, находятся ли в ней полезные ископаемые, корректной, если для нее сканер возвращает верные значения. Например, если в примере выше сканер вернул значения \([2, 1, 2, 3, 2]\), то одна из корректных таблиц может выглядеть следующим образом (клетки, содержащие ископаемые, обозначены черным треугольником):

По заданным значениям, которые вернул сканер, определите количество корректных таблиц и выведите остаток от деления этого количества на число \(10^9+7\). Обратите внимание, что, возможно, сканер неисправен, и корректных таблиц вообще нет, тогда необходимо вывести \(0\).

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

Во второй строке даны \(n\) чисел \(b_1, b_2, \ldots, b_n\) — значения, которые вернул сканер (\(0 \le b_i \le k^2\)).

Формат выходных данных
Выведите единственное число — остаток от деления количества различных корректных таблиц на \(10^9 + 7\).

Для сборки лаборатории-поселения на Венеру доставлены \(n\) блоков. Блоки расположены в ряд, \(i\)-й блок имеет высоту \(h_i\).

Сборку будет осуществлять специальный робот. В процессе сборки последовательные сегменты блоков будут постепенно объединяться. При этом порядок блоков в ряду не будет меняться.

Исходно каждый блок представляет собой отдельный сегмент, сегменты пронумерованы от \(1\) до \(n\) в том же порядке, что и блоки. Если есть два соседних сегмента, составленных из блоков: сегмент из блоков \(A = [i, i+1, \ldots, i+p-1]\) и сегмент из блоков \(B = [i+p, i+p+1, \ldots, i+p+q-1]\), то после их объединения в один получается сегмент \(AB = [i, i+1, \ldots, i+p-1, i+p, i+p+1, \ldots, i+p+q-1]\).

Инструкция по сборке состоит из \(n-1\) инструкций. Каждая инструкция характеризуется одним числом, \(j\)-я инструкция характеризуется числом \(k_j\). После выполнения этой инструкции сегменты с номерами \(k_j\) и \(k_j + 1\) объединяются в один, получившийся сегмент занимает место в последовательности сегментов на месте двух объединенных сегментов, и вводится новая нумерация на сегментах в том порядке, в котором они расположены — номера сегментов, начиная с \(k_j + 2\), уменьшаются на один. После выполнения всех инструкций все сегменты окажутся объединены в один общий сегмент.

На Венере постоянно идут кислотные дожди, поэтому в процессе сборки важно для каждого сегмента блоков понимать, сколько жидкости может скопиться в этом сегменте. Пусть сегмент состоит из блоков высотой \(h_l, h_{l+1}, \ldots, h_r\). Для \(p\), где \(l \le p \le r\) определим глубину блока c высотой \(h_p\) в этом сегменте следующим образом. Посчитаем величины \(l_p = \max \{ h_l, \ldots, h_p \}\), \(r_p = \max \{ h_p, \ldots, h_r\}\). Это самые высокие блоки в сегменте слева и справа от \(p\)-го. Тогда глубина блока \(p\) в его сегменте равна \(d_p = \min(l_p, r_p) - h_p\), заметим, что \(d_p \ge 0\). Емкостью сегмента будем называть сумму глубин блоков этого сегмента, то есть \(w = d_l + d_{l+1} + \ldots + d_r\).

Задана последовательность объединений сегментов. После каждого объединения выведите емкость получившегося сегмента.

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

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

Во второй строке записано \(n\) чисел \(h_1, \ldots, h_n\) (\(1 \leq h_i \leq 10^9\)).

В третьей строке записаны \(n - 1\) чисел — инструкции по объединению сегментов. Каждая инструкция характеризуется одним числом \(k_j\) (\(1 \leq k_j \leq n - j\)).

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