Возвращение к домашней работе

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

Вам дается строка $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