КОЛОНИЗАЦИЯ

Име: COL

Далеч в бъдещето, организация от софтуерни компании решила да закупи цяла гигантска планета, за да строи градчета, в които да развива бизнеса си и да настанява програмистите си. Oрганизацията е разделила обитаемата територия на планетата (която по случайност има форма на квадрат) на DxD малки квадрата и желае да разполага с информационна система за нивото на колонизация (т.е. брой програмисти) във всеки малък квадрат. Очаква се голяма вълна на заселници и, за свръхсекретни цели, организацията се нуждае от възможността да извършва две неща:

- да подава на системата информация за нови заселници от типа: в район с координати (x,y) се заселиха още C програмиста.

- в даден момент да замрази подаването на данни. След този момент, на базата на подадената информация, да получава отговори на запитвания от типа: колко жители има в район с координати (x,y) ?

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

В началото програмата ви ще получи N актуализации на брой жители в различни квадрати. След това ще следват M запитвания, на които трябва да се даде отговор.

Разбира се, в самото начало всички райони имат по 0 жители.

Вход (стандартен вход):

Ред 1: числата N и М, разделени с интервал

Ред 2..N+1: три цели числа x_i, y_i, и C_i (разделени с интервали) – указват, че в районa с координати (x_i, y_i) са се заселили нови C_i програмиста.

Ред N+2…N+M+1: две числа x_i, y_i, разделени с интервал, сочещи координатите на района, за който трябва да се изведе броят жители

Изход (стандартен изход):

M на брой цели числа (всяко на нов ред), даващи отговори на M-те запитвания във входа. Реда на отговорите в изхода съответства на реда на запитванията във входа.

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

1 <= N <= 100 000

1 <= M <= 100 000

0 <= x_i, y_i <= D <= 10 000

0 <= краен брой жители в район <= 2 000 000 000

Време за работа: 1s

Пример:

Вход:

5 5

10 10 3

2 10 4

10 23 21

10 10 5

1 17 100

10 10

1 17

10 10

2 22

1 9

Изход:

8

100

8

0

0