Двадцатый век начинается
Начинается ХХ век. Появляются новые, более опасные преступники, замешанные в политике и международных отношениях. Однажды, один из таких преступников, похищает очень важный документ, который может вызвать большую войну. К этому делу были привлечены лучшие детективы Шерлок Холмс и доктор Ватсон.
Шерлок Холмс с доктором Ватсоном прибывают на место преступления. Похищенный документ находился в закрытом сейфе, преступник с помощью специального устройства смог открыть сейф, но в спешке забыл устройство. Холмс, взяв устройство выяснил, что он имеет n ячеек для заполнения числами, а также две функции:
увеличить p-й элемент на d, но при выполнении этой операции устройство каким-то образом запоминало предыдущее состояние, т.е. предварительная информация не терялась;
посчитать сумму чисел на промежутке [l, r].
Поскольку устройство хранило все предыдущие состояния, поэтому этими функциями было можно обратиться к любому состояния устройства.
Так как устройство очень быстро работало, Холмс подумал, если понять алгоритм, то он сможет установить человека, который изготовил прибор. Ваша задача заключается в написании этого алгоритма.
Входные данные
Первая строка содержит два числа n (1 ≤ n ≤ 100000) и m (1 ≤ m ≤ 100000), где n — количество ячеек прибора, m — количество запросов.
В следующих m строках заданы запросы двух типов:
1 x p d - из состояния x, образовать новое, p-й элемент которого увеличить на d.
2 x l r - в состоянии x посчитать сумму на промежутке [l, r];
Сначала все ячейки устройства заполнены нулями. Это состояние имеет номер 0. Все позиции ячеек устройства начинаются с единицы. Запросов к несуществующим состояниям не будет. При обработке запроса второго типа, создается новое состояние, которое получает номер j + 1, где j - номер последнего добавленного состояния, сначала j = 0.
Выходные данные
Для каждого запроса первого типа, в отдельной строке нужно вывести ответ.