eolymp
Competitions

Пятёрка за неделю 23 (2013-2014)

Двадцатый век начинается

Начинается ХХ век. Появляются новые, более опасные преступники, замешанные в политике и международных отношениях. Однажды, один из таких преступников, похищает очень важный документ, который может вызвать большую войну. К этому делу были привлечены лучшие детективы Шерлок Холмс и доктор Ватсон.

Шерлок Холмс с доктором Ватсоном прибывают на место преступления. Похищенный документ находился в закрытом сейфе, преступник с помощью специального устройства смог открыть сейф, но в спешке забыл устройство. Холмс, взяв устройство выяснил, что он имеет n ячеек для заполнения числами, а также две функции:

  • увеличить p-й элемент на d, но при выполнении этой операции устройство каким-то образом запоминало предыдущее состояние, т.е. предварительная информация не терялась;
  • посчитать сумму чисел на промежутке [l, r].

Поскольку устройство хранило все предыдущие состояния, поэтому этими функциями было можно обратиться к любому состояния устройства.

Так как устройство очень быстро работало, Холмс подумал, если понять алгоритм, то он сможет установить человека, который изготовил прибор. Ваша задача заключается в написании этого алгоритма.

Входные данные

Первая строка содержит два числа n (1n100000) и m (1m100000), где n — количество ячеек прибора, m — количество запросов.

В следующих m строках заданы запросы двух типов:

  • 1 x p d- из состояния x, образовать новое, p-й элемент которого увеличить на d.
  • 2 x l r - в состоянии x посчитать сумму на промежутке [l, r];

Сначала все ячейки устройства заполнены нулями. Это состояние имеет номер 0. Все позиции ячеек устройства начинаются с единицы. Запросов к несуществующим состояниям не будет. При обработке запроса второго типа, создается новое состояние, которое получает номер j + 1, где j - номер последнего добавленного состояния, сначала j = 0.

Выходные данные

Для каждого запроса первого типа, в отдельной строке нужно вывести ответ.

Time limit 1 second
Memory limit 128 MiB
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
Author Александр Цицюра