Республиканская олимпиада по информатике 2021 года за 11 класс | Казахстанские олимпиады

Башни

В одном ряду последовательно расположили $n$ башен из кубиков. $i$-я башня состоит из $a_i$ кубиков, которые выставлены вертикально друг над другом. Гарантируется, что все башни состоят из не более чем $k$ кубиков.

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

BThero последовательно дает вам $q$ запросов трех видов.

1. Вам дается одно единственное число $y$, и все кубики стоящие на высоте $y$ превращаются в замороженные.

2. Вам дается одно единственное число $y$, и все кубики стоящие на высоте $y$ превращаются в обычные.

3. Вам дается одно единственное число $y$, и на высоте $y$ устанавливается новый лазер. Гарантируется, что на этой высоте ранее еще не был установлен никакой лазер. Номером этого лазера будет являться минимальное еще не занятое положительное число. Лазер можно представить как бесконечную горизонтальную линию на высоте y и он будет уничтожать все кубики которые его касаются. Может быть такое, что лазер уничтожил кубик, а сверху по закону гравитации на его место упал другой кубик обычного типа. Тогда тот кубик тоже уничтожится, и процесс может повториться снова.

Обозначим суммарное количество установленных лазеров как $m$. После всех запросов выведите количество уничтоженных кубиков для каждого лазера.

Формат входного файла

В первой строке входного файла даны три целых числа $n$, $q$ и $k$ — количество башен, количество запросов и ограничение на количество кубиков в башнях $(1 \leq n, q \leq 300000, 1 \leq k \leq 10^9)$.

Во второй строке даны $n$ целых чисел $a_1, . . . , a_n (1 \leq a_i \leq k)$.

В последующих $q$ строках даны все запросы в формате $t_i, y_i$ — тип $i$-го запроса и число, связанное с этим запросом $(1 \leq t_i \leq 3, 1 \leq y_i \leq k)$.

Формат выходного файла

Выведите $m$ целых чисел $c_1, . . . , c_m$ разделенные пробелами — количество уничтоженных клеток для каждого лазера. Гарантируется, что $m > 0$.

Примеры

Ввод

4 5 8
5 2 4 7
1 5
3 2
3 3
2 5
3 1

Вывод

10 4 4