Accept за 150 секунд
В непослушном королевстве решили проверить, или не обманули их программисты, писавшие программное обеспечение для продажи трамвайных билетов онлайн. Онлайн продажа билетов происходит следующим образом: каждый пассажир заказывает собе билет от станции А до станции B. А программа этих горе-программистов сообщает начальству только количество пассажиров, которые вошли на каждой остановке (In), и количество вышедших на остановке пассажиров (Out).
Для контроля этой информации управление транспорта отправило контролёров на маршрут, которые от станции L до станции R контролируют всех входящих и выходящих из транспортных средств пассажиров. Они насобирали информацию о том, сколько билетов фактически было продано от станции L до станции R включительно, но по дороге к управлению потеряли её. Чтобы начальство их не ругало, они просят Вас быстро её посчитать и отправить полученные данные в управление транспора.
Трамвайный маршрут - это прямая линия, вдоль которой размещены остановки. Остановки нумеруются с единицы, но ехать можно только от остановки с меньшим номером, к остановке с большим номером.
Входные данные
В первой строке заданы 2 натуральных числа: N – количество остановок, M – количество контролёров на линии (N ≤ 10^5, M ≤ 10^5). В последующих N строках строка i+1 описывает пару чисел для i-ой остановки: In – сколько людей войшло на станции i, и Out – сколько людей вышло на станции i (0 ≤ In, Out ≤ 10^4, Out[1] = 0, In[N] = 0, на конечной остановке (N) из трамвая выходят все пассажиры). В последующих M строках также две пары чисел L, R - номера станций, между которыми работают контролёры (1 ≤ L < R ≤ N).
Выходные данные
Для каждого контролёра, в том порядке в котором они заданы, вывести сколько билетов было продано между остановками L и R включительно.