Двадцятий вік починається#6637
Початок ХХ століття. З'являються нові, більш небезпечні злочинці, які замішані в політиці та міжнародних відносинах. Одного разу один з таких злочинців викрадає дуже важливий документ, що може спричинити велику війну. До розслідування залучають найкращих детективів — Шерлока Холмса та доктора Ватсона.
Шерлок Холмс разом із доктором Ватсоном прибувають на місце злочину. Викрадений документ зберігався в закритому сейфі. Злочинець, використовуючи спеціальний пристрій, зміг відкрити сейф, але в поспіху залишив пристрій. Холмс, вивчивши пристрій, з'ясував, що він має комірок для заповнення числами, а також дві функції:
збільшити p-й елемент на d, при цьому пристрій зберігає попередній стан, тобто інформація не втрачається;
обчислити суму чисел на проміжку [l, r].
Оскільки пристрій зберігає всі попередні стани, можна звертатися до будь-якого стану пристрою.
Пристрій працює дуже швидко, і Холмс вирішує, що якщо зрозуміти алгоритм, то можна буде виявити людину, яка створила цей прилад. Ваше завдання — написати цей алгоритм.
Перший рядок містить два числа (1 \leq n \leq 100000) і (1 \leq m \leq 100000), де — кількість комірок пристрою, — кількість запитів.
У наступних рядках задані запити двох типів:
1 x p d — з стану x утворити новий, у якому p-й елемент збільшено на d.
2 x l r — у стані x обчислити суму на проміжку [l, r];
Спочатку всі комірки пристрою заповнені нулями. Цей стан має номер . Усі позиції комірок пристрою починаються з одиниці. Запитів до неіснуючих станів не буде. При обробці запиту другого типу створюється новий стан, який отримує номер j + 1, де — номер останнього доданого стану, спочатку j = 0.
Для кожного запиту другого типу, в окремому рядку потрібно вивести відповідь.
Приклад 1