28926번 - Возвращение к домашней работе 다국어

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

Вам дается строка $s_0$ --- начальное значение строки $s$, состоящей из символов 0, 1, 2 и 3. Далее, вам нужно обрабатывать запросы четырех типов:

1. Вам дается целое число $p_i$ и строка $w_i$. Вы должны вставить строку $w_i$ в текущую строку $s$ перед символом на позиции $p_i$, если $pos_i < |s|$ и после всех символов, если $p_i = |s|$.
2. Вам даются два целых числа $p_i$ и $l_i$. Вы должны удалить из текущей строки $s$ подстроку длины $l_i$, начинающуюся с символа на позиции $p_i$.
3. Вам даются два целых числа $p_i$ и $l_i$. Вы должны развернуть в обратном порядке подстроку строки $s$, начинающуюся с символа на позиции $p_i$, длины $l_i$.
4. Вам даются три целых числа $p_i$, $l_i$ и $k_i$. Вы должны $k_i$ раз продублировать подстроку, начинающуюся с символа на позиции $p_i$, имеющую длину $l_i$, сразу после этой подстроки. Иными словами, вы должны сразу после этой подстроки дописать эту подстроку $k_i$ раз.

Символы в строке нумеруются с $0$. Смотрите пояснение к примеру для лучшего понимания.

В каждый момент времени вас интересует длина наибольшей неубывающей подпоследовательности строки $s$. Наибольшей неубывающей подпоследовательность называется максимальное по размеру множество чисел $a_1 < a_2 < \dots < a_{m - 1} < a_m$, для которых верно, что $s_{a_1} \le s_{a_2} \le \dots \le s_{a_{m - 1}} \le s_{a_m}$.

В первой строке дана непустая строка $s_0$, состоящая из символов 0\dots3 --- начальное значение строки $s$ ($|s_0| \le 100\,000$). В следующей строке дано целое число $q$ --- количество запросов ($0 \le q \le 15\,000$). В следующих $q$ строках дано описание запросов. Если строка начинается с $1$, то это запрос первого типа, далее дано целое число $p_i$ и непустая строка $w_i$, состоящая из символов 0\dots3 ($0 \le p_i \le |s|$, $1 \le |w_i| \le 100\,000$). Если строка начинается с $2$, то это запрос второго типа, далее даны два целых числа $p_i$ и $l_i$ ($1 \le l_i < |s|$, $0 \le p_i \le |s| - l_i$). Если строка начинается с $3$, то это запрос третьего типа, далее даны два целых числа $p_i$ и $l_i$ ($1 \le l_i < |s|$, $0 \le p_i \le |s| - l_i$). Если строка начинается с $4$, то это запрос четвертого типа, далее даны три целых числа $p_i$, $l_i$ и $k_i$ ($1 \le l_i < |s|$, $0 \le p_i \le |s| - l_i$, $1 \le k_i \le 10^{15}$).

Гарантируется, что в любой момент времени строка $s$ не пуста, и ее длина не превышает $10^{15}$. Гарантируется, что сумма длин всех $w_i$ не превышает $100\,000$.

Выведите $q + 1$ целое число --- длину наибольшей неубывающей подпоследовательности $s$ до всех запросов и после каждого из запросов.

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

0103020

010300120

000120

002100

002002002100