Problems
Двадцатый век начинается
Двадцатый век начинается
Начинается ХХ век. Появляются новые, более опасные преступники, замешанные в политике и международных отношениях. Однажды, один из таких преступников, похищает очень важный документ, который может вызвать большую войну. К этому делу были привлечены лучшие детективы Шерлок Холмс и доктор Ватсон.
Шерлок Холмс с доктором Ватсоном прибывают на место преступления. Похищенный документ находился в закрытом сейфе, преступник с помощью специального устройства смог открыть сейф, но в спешке забыл устройство. Холмс, взяв устройство выяснил, что он имеет n ячеек для заполнения числами, а также две функции:
\begin{itemize}
\item увеличить \textbf{p}-й элемент на \textbf{d}, но при выполнении этой операции устройство каким-то образом запоминало предыдущее состояние, т.е. предварительная информация не терялась;
\item посчитать сумму чисел на промежутке \textbf{\[l, r\]}.
\end{itemize}
Поскольку устройство хранило все предыдущие состояния, поэтому этими функциями было можно обратиться к любому состояния устройства.
Так как устройство очень быстро работало, Холмс подумал, если понять алгоритм, то он сможет установить человека, который изготовил прибор. Ваша задача заключается в написании этого алгоритма.
\InputFile
Первая строка содержит два числа \textbf{n} (\textbf{1} ≤ \textbf{n} ≤ \textbf{100000}) и \textbf{m} (\textbf{1} ≤ \textbf{m} ≤ \textbf{100000}), где \textbf{n} --- количество ячеек прибора, \textbf{m} --- количество запросов.
В следующих \textbf{m} строках заданы запросы двух типов:
\begin{itemize}
\item \textbf{1 x p d }- из состояния \textbf{x}, образовать новое, \textbf{p}-й элемент которого увеличить на \textbf{d}.
\item \textbf{2 x l r} - в состоянии \textbf{x} посчитать сумму на промежутке \[\textbf{l}, \textbf{r}\];
\end{itemize}
Сначала все ячейки устройства заполнены нулями. Это состояние имеет номер \textbf{0}. Все позиции ячеек устройства начинаются с единицы. Запросов к несуществующим состояниям не будет. При обработке запроса второго типа, создается новое состояние, которое получает номер \textbf{j + 1}, где \textbf{j} - номер последнего добавленного состояния, сначала \textbf{j = 0}.
\OutputFile
Для каждого запроса первого типа, в отдельной строке нужно вывести ответ.
Input example #1
5 7 1 0 1 5 1 1 2 4 1 2 3 3 1 3 4 2 1 4 5 1 2 4 1 5 2 5 1 5
Output example #1
14 15