A: Суммы на префиксе

Дан массив $A$ длины $N$, а также $M$ запросов вида $l$. Для каждого запроса найдите сумму первых $l$ элементов массива.

B: Суммы на подотрезках

Дан массив $A$ длины $N$, а также $M$ запросов вида $l$ $r$. Нужно найди сумму элементов массива с $l$ по $r$

C: Произведение на подотрезках

Дан массив $A$ длины $N$, а также $M$ запросов вида $l$ $r$. Нужно найди произведение элементов массива с $l$ по $r$ по модулю $10^9 + 7$. Гарантируется, что в массиве нет нулей.

D: Суммы на подпрямоугольнике

Дан двумерный массив $A$ размера $N \times M$, а также $Q$ запросов вида $x\ y\ x_1\ y_1$. Нужно найди сумму элементов подмассива с левым верхним углом в $(x, y)$ и правым нижним $(x_1, y_1)$

E: Суммы на подотрезках с единичным изменением

Дан массив $A$ длины $N$, а также $M$ запросов одного из 2х видов:

1. сумма на отрезке
2. единичное изменение

F: Произведение на подотрезках с единичным изменением

Дан массив $A$ длины $N$, а также $M$ запросов одного из 2х видов:

1. произведение на отрезке по модулю $10^9 + 7$
2. единичное изменение

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

G: Суммы на подотрезках с изменением на отрезке

Дан массив $A$ длины $N$, а также $M$ запросов одного из 2х видов:

1. сумма на отрезке
2. инкремент на отрезке

Требуется ответить на все запросы суммы на отрезке

H: Количество чисел меньших $k$ с инкрементом на отрезке

Для заданного массива требуется выполнить ряд запросов. Все запросы делятся на два типа. Запрос первого типа – вычислить количество элементов массива на отрезке от l до r меньших заданного числа x. Запрос второго типа – увеличить все элементы массива на отрезке от l до r на заданное число x.

1. 1 - найти количество чисел меньших $k$ и больших $l$ на отрезке
2. 2 - инкремент на отрезке на величину $x$

Требуется ответить на все запросы.

I: K-я порядковая статистика на отрезке с изменением на отрезке

Для заданного массива требуется выполнить ряд запросов. Все запросы делятся на два типа.

1. Вычислить $k$-тую порядковую статистику на отрезке с $l$ по $r$.
2. Увеличить все элементы массива на отрезке от $l$ до $r$ на заданное число x.

J: Покраска вершин

Вам дан граф с $N$ вершинами и $M$ ребрами. У каждой вершины есть свой цвет $v_i$. Вам дано $q$ запросов в виде пары $(v_i, c_i)$, означающий, что надо перекрасить вершину $v_i$ в цвет $c_i$. После каждого запроса нужно вывести количество ребер у которых вершины покрашены в разный цвет.

K: Количество соседних цветов

Дан неориентированный граф без петель и кратных ребер, у которого $n$ вершин и $m$ ребер. У каждой вершины есть цвет. Требуется ответить на $q$ запросов. Каждый запрос имеет один из двух типов:

1. $v$ $c$ – перекрасить вершину $v$ в цвет $c$
2. $v$ – вычислить количество различных цветов у соседей вершины $v$.

L: Количество циклов длины 3

Вам дан граф с $N$ вершинами и $M$ ребрами. Вам нужно найти количество циклов длины 3.

M: Очень простая сумма

Дано число $n$ до $10^{12}$, посчитайте сумму $\sum_{i=1}^n \lfloor\frac{n}{i}\rfloor$

N: Substring query

У Пупы есть $n$ строк $S_1,S_2,S_3,...,S_n$ Однажды его друг Лупа пришёл в бухгалтерию и попросил его ответить на $q$ вопросов: сколько строк среди $S_{l_i},S_{l_i + 1}, S_{l_i + 2},...,S{r}$ содержат $P_i$ как подстроку?

Но в бухгалтерии все перепутали, и ответить на запросы за Пупу придется Вам.

Суммарный размер строк $P_i\le200000$

O: Винни Пух и бочки меда

Малыш и Карлсон решили пойти на прогулку. Они знают, что прогулка будет совсем скучной, если перед ней не опустошить несколько банок варенья.
Малыш достал из кладовки N банок варенья и выставил их в ряд. В банке номер $i$ содержится ровно a $i$ грамм варенья. Карлсон немного подумал и решил, что в некоторых банках недостаточно варенья, и что в банке номер $i$ должно быть хотя бы $b_i$ грамм варенья.
Выходить из этой ситуации Карлсон хочет в $M$ этапов. На каждом этапе он выбирает числа $l$, $r$, $x$ и $y$, а затем выполняет следующие операции: в банку номер $l$ он добавляет x грамм варенья, в банку номер $l +  1$ — $x + y$ грамм варенья, в банку номер $l + 2$ — $x + 2· y$, и так далее. В банку номер $r$ наш герой добавит $x + y ·(r - l)$ грамм варенья.
Малышу хочется определить для каждой банки i наименьший номер операции, после которой в ней станет хотя бы b i грамм варенья. Помогите Малышу: найдите соответствующее число для каждой банки.

В первой строке входного файла задано одно число $N (1 ≤ n ≤ 10^{5})$ — количество банок. Во второй строке заданы $N$ чисел $a_i (0 ≤ a_i ≤ 2·10^{9})$ — изначальное количество варенья в банке номер $i$. В третьей строке заданы $N$ чисел $b_i$ $(0 ≤ b_i ≤ 2·10^{9})$ — минимальное количество варенья, которое должно быть в банке номер $i$.
В четвертой строке задано $M$ $(0 ≤ M ≤ 10^{5})$ — число этапов добавления варенья в банки, которые выполнит Карлсон. В следующих $M$ строках описаны сами этапы в хронологическом порядке. Каждый этап задан четырьмя числами $l$, $r$, $x$ и $y$ $(1 \le l \le r \le N, 0 \le x, y \le  10^{5})$.
Выходные данные
Выведите $N$ чисел в одной строке, разделенные пробелом. Число номер $i$ должно быть равно нулю, если в банке номер $i$ изначально было достаточно варенья, номеру этапа, после которого в ней станет хотя бы $b_i$ варенья, или $- 1$, если даже после выполнения всех этапов, в этой банке будет недостаточно варенья. Этапы нумеруются с единицы.

P: Мощные юнги

Имеется список из $n$ юнг, для каждого из которых известен его рост $a_1,a_2,a_3,...,a_n$. Рассмотрим некоторый его подсписок $a_l,a_{l+1},a_{l+2},...,a_r$, где $1\le l \le r \le n$, и для каждого натурального числа $s$ обозначим через $K_s$ число юнг с ростом $s$ в этом подсписке. Назовем мощностью подсписка сумму произведений $K_s \cdot K_s \cdot s$ по всем различным натуральным $s$. Так как количество различных чисел в массиве конечно, сумма содержит лишь конечное число ненулевых слагаемых.
Необходимо вычислить мощности каждого из $t$ заданных подсписков.

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

Первая строка содержит два целых числа $n$ и $t$ $(1 \le n, t \le 200000)$ — длина списка и количество запросов соответственно. Вторая строка содержит $n$ натуральных чисел $a_i$ $(1 \le a_i \le 10^{6})$ — рост юнг. Следующие $t$ строк содержат по два натуральных числа $l$ и $r$ $(1 \le l \le r \le n)$ — индексы левого и правого концов соответствующего подсписка.

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

Выведите $t$ строк, где $i$-ая строка содержит единственное натуральное число — мощность подсписка $i$-го запроса

Q: Инверсии на отрезке

Дана перестановка из $n$ элементов. Ответьте на m запросов про число инверсий для подотрезка перестановки от $l$ до $r$. Инверсией называется пара индексов $i, j$ такая, что $i \lt j$ и $a_i > a_j$ , где $a_i$ - это i-ый элемент перестановки.

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

В первой строке задано число $n$ $(1 \le n \le 10^{5})$. Во второй строке задана перестановка из $n$ элементов (элементы перестановки — попарно различные целые числа от 1 до $n$). В третьей строке задано число $m$ $(1 \le m \le 10^{5})$. В последующих $m$ строках содержится по два числа, $l$ и $r$, границы запроса $(1 \le l, r \le n)$.

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

Выведите $m$ строк, ответы на данные запросы.

R: MEX на пути в дереве

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

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

Первая строка входных данных содержит два числа $n$ и $q$ ($1 \le n, q \le 3 * 10^5$), количество вершин и количество запросов. Следующие $n − 1$ строк содержат по три числа $u_i$ ,$v_i$, $x_i$ ($1 \le u_i, v_i \le n; 0 \le x_i \le 10^9$) которые описывают ребро дерева ($u_i$, $v_i$), на котором написано число $x_i$. Следующие $q$ строк содержат по паре чисел $a_j$, $b_j$, которая обозначает запрос на пути от $a_j$ до $b_j$

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

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

S: Дима и массив

Диме не дарили массив $a$, состоящий из $n$ целых чисел на день рождения, он не покупал его, не находил на улице, а он у него просто есть и всегда был, и Диме не очень-то и интересно откуда. Дима не играет с массивом, не дарит его Пете, не режет на кусочки и не стремится его уничтожить. Дима просто выполняет операции двух видов со своим массивом:

1. $?$ $l$ $r$ — узнать MEX мультимножества $\{a_l, a_{l+1}, . . . , a_r\}$
2. $!$ $i$ $x$ — присвоить $a_i$ значение $x$ $(0 \le x \le n)$

MEX мультимножества чисел $\{a_1, a_2, . . . , a_k\}$ — это минимальное целое $t \ge 0$ такое, что $t \ne a_i$ для всех $1 \le i \le k$.

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

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

Первая строка содержит два целых числа $n$ и $q$ $(1 \le n \le 500\,000, 1 \le q \le 250\,000)$ — размер массива, который есть у Димы и количество операций, соответственно. Вторая строка содержит $n$ целых чисел $a_i$ $(0 \le a_i \le n)$ — массив Димы до начала операций. Каждая из следующих $q$ строк содержит описание одной операции в формате, описанном выше. Элементы массива пронумерованы, начиная с 1.

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

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

T: Машинное обучение

На курсе машинного обучения вам выдали первое домашнее задание — вам предстоит проанализировать некоторый массив из n чисел. В частности, вы интересуетесь так называемой равномерностью массива. Предположим, что в массиве число $b1$ встречается $k1$ раз, $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$ — размер массива и число запросов соответственно. Во второй строке записаны ровно $n$ чисел — $a_1, a_2, ..., 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$ — его новое значение

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

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