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