eolymp
bolt
Try our new interface for solving problems
Məsələlər

Accept за 150 секунд

Accept за 150 секунд

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

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

Для контроля этой информации управление транспорта отправило контролёров на маршрут, которые от станции L до станции R контролируют всех входящих и выходящих из транспортных средств пассажиров. Они насобирали информацию о том, сколько билетов фактически было продано от станции L до станции R включительно, но по дороге к управлению потеряли её. Чтобы начальство их не ругало, они просят Вас быстро её посчитать и отправить полученные данные в управление транспора.

Трамвайный маршрут - это прямая линия, вдоль которой размещены остановки. Остановки нумеруются с единицы, но ехать можно только от остановки с меньшим номером, к остановке с большим номером.

Giriş verilənləri

В первой строке заданы 2 натуральных числа: N – количество остановок, M – количество контролёров на линии (N10^5, M10^5). В последующих N строках строка i+1 описывает пару чисел для i-ой остановки: In – сколько людей войшло на станции i, и Out – сколько людей вышло на станции i (0In, Out10^4, Out[1] = 0, In[N] = 0, на конечной остановке (N) из трамвая выходят все пассажиры). В последующих M строках также две пары чисел L, R - номера станций, между которыми работают контролёры (1L < RN).

Çıxış verilənləri

Для каждого контролёра, в том порядке в котором они заданы, вывести сколько билетов было продано между остановками L и R включительно.

Nümunə

Giriş verilənləri #1
7 4
1 0
2 0
3 1
4 2
5 0
6 0
0 18
1 3
1 7
3 7
4 5
Çıxış verilənləri #1
6
21
18
9
Müəllif Остап Столярчук
Mənbə Дистанционная Летняя Компьютерная Школа - лето 2013 года