Живот или смърт.

Въпреки че скоро идвала зима, селянинът Иван решил да даде шанс на своето любимо женско прасе Прасанда да се спаси от нещастната участ да стане зимнина. Като предприемчив селянин, той имал много кокошки номерирани последователно с числата от 1 до N (2<=N<=111000). За да спаси живота си, Прасанда трябва да може, когато я попита селянина Иван, да отговаря колко е сбора на яйцата снесени от кокошките с номера между X и Y включително. В началото всяка кокошка има снесени 0 яйца. Между някои от въпросите си, Иван съобщава на Прасанда по колко нови яйца са снесли някои от кокошките му. При следващия въпрос пресето трябва да има предвид и новите яйца. Сборът на снесените яйца от всички кокошки е по-малък от 2 на степен 31. И така вие трябва да помогнете на Прасанда да преживее и тази зима като напишете програма, която да отговоря на въпросите на Иван.

Вход:

Входните данни се четат от стандартния вход. На първия ред стоят естетвените числа N и М разделени с един интервал (2<М<100000). Всеки от следващите М реда съдържа 3 цели числа и може да е или въпрос или актуализация на броя на снесените яйца от дадена кокошка. Ако първото число на реда е 0 то този ред е актуализация и следвашите две числа X и Y означат, че кокошката с номер X е снесла нови Y яйца. Ако първото число е 1, то редът е въпрос и двете числа X и Y означат въпрос колко яйца общо са снесли кокошките с номера между X и Y включително.

Изход:

Изходът трябва да съдържа толкова редове, колкото са въпросите на Иван. Всеки ред трябва да съдържа единствено число - отговора на съответния въпрос. Редът на отговорите в изходния файл трябва да съвпада с реда на въпросите във входния файл.

Ограничения:

2<N<111000

2<M<100000

в 50% от тестовете N<9000

Примерен Вход:

3 5

0 1 4

0 3 2

1 1 3

0 2 10

1 1 2

Примерен Изход:

6

14