Начинается ХХ век. Появляются новые, более опасные преступники, замешанные в политике и международных отношениях. Однажды, один из таких преступников, похищает очень важный документ, который может вызвать большую войну. К этому делу были привлечены лучшие детективы Шерлок Холмс и доктор Ватсон. Шерлок Холмс с доктором Ватсоном прибывают на место преступления. Похищенный документ находился в закрытом сейфе, преступник с помощью специального устройства смог открыть сейф, но в спешке забыл устройство. Холмс, взяв устройство выяснил, что он имеет 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 Для каждого запроса первого типа, в отдельной строке нужно вывести ответ.