SPUTNIK

  • Спутник
    SPUTNIK

Описание
Секретная корпорация, занимающаяся поиском инопланетных жизненных форм обнаружила на одной из планет созвездия Альфа удивительные живые организмы (даже не плоские, а одномерные). Она приняла решение вести наблюдение за развитием и изменением численности организмов, с этой целью на орбиту планеты был послан спутник - наблюдатель, который мог следить за изменениями численности организмов. Недостаток этого "наблюдателя" в том, что он может отслеживать изменения только на той территории планеты, которая находиться непосредственно под ним.

С этой целью его траектория была разбита на равные интервалы. Они пронумерованы от 1 до N. По запросу с Земли о количестве живых форм в интервале с L по R (L<=R) - спутник должен, пролетая над ними (L, L+1, …,R-1, R интервалами) произвести подсчет и затем, в ответ на запрос, отправить полученные данные. Но количество организмов постоянно изменяется: в некоторое время в X интервале на Y единиц.

Задача
Помогите написать программу для спутника, которая будет отвечать на запросы и отслеживать количество единиц жизни в каждом интервале.

Технические требования:

Входной файл: INPUT.TXT
Выходной файл: OUTPUT.TXT
Ограничение по времени на каждый тест: 2 секунды

Формат входных данных:
Во входном файле первым записано число N (1<=N<=213=8192). Затем записана последовательность событий:

Событие

Параметры

Описание

    1

X, Y

Изменение количества организмов в интервале с номером X на Y единиц.(-215<=Y<=215-1 =32767)

2

L, R

Запрос суммарного количества организмов с L по R интервал.

0

 

Завершение работы.

Количество событий не превосходит 100000.

Формат выходных данных:
В выходной файл записывать только ответы на запросы

Примеры:

 INPUT.TXT  OUTPUT.TXT

2
1  1  4
2  1  1
2  1  1
0

4
4

 INPUT.TXT  OUTPUT.TXT

4
2  1  4
1  1  3
1  4  2
2  2  4
2  1  2
1  4  -2
1  2  8
2  1  4
0

0
2
3
11