% Автор: Сергей Копелиович
% Источник: ЛКШ.2015.Июль.AS

\begin{problem}{Машенька и её интерес}
{treap.in}{treap.out}
{1 секунда}{256 мегабайт}{}

Есть $n$ мальчиков и девочка Маша.
Изначально каждый мальчик стоит сам по себе и с точки зрения Маши имеет нулевую интересность.
Девочка Маша хочет провести некоторый эксперимент, в течение которого каждый мальчик стоит в некоторой шеренге.
Мальчики несговорчивые, участвовать в эксперименте не хотят, поэтому Маша собирается прибегнуть к математическому моделированию.
Для этого ей нужно научиться быстро обрабатывать следующие запросы:

\begin{itemize}
  \setlength{\parskip}{0pt}
  \setlength{\itemsep}{4pt}
  \item \t{link(a, b)} -- взять мальчиков с номерами $a$ и $b$, если они стоят в разных шеренгах, то объединить шеренгу в одну:  в начале шеренга мальчика $a$, затем шеренга мальчика $b$.
  \item \t{split(a, k)} -- взять шеренгу, в которой стоит мальчик с номером $a$ и разбить её на две: первые $k$ мальчиков и все остальные.
    Если размер шеренги не больше $k$, ничего делать не нужно.
  \item \t{interest(a, x)} -- сделать интересность мальчика $a$ равной $x$ (целое от $0$ до $10^9$).
  \item \t{sum(a)} -- суммарная интересность мальчиков в шеренге, в которой стоит мальчик $a$.
\end{itemize}

\InputFile

В первой строке $n$ ($1 \le n \le 100\,000$) -- количество мальчиков и $m$ ($1 \le m \le 250\,000$) -- количество запросов.
Далее $m$ строк. Для понимания формата смотри пример. Мальчики нумеруются числами от $1$ до $n$.

\OutputFile

Для каждого запроса ``\t{sum}'' на отдельной строке одно число -- суммарная интересность.

\Examples

\begin{example}
\exmp{
5 12
sum 1
interest 5 10
sum 5
interest 3 7
link 3 1
link 3 5
sum 1
interest 1 20
sum 1
split 1 2
sum 3
sum 5
}{
0
10
17
37
27
10
}%
\end{example}

\end{problem}
