eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Accept за 150 секунд

Accept за 150 секунд

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB

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

Для контролю цієї інформації транспортне відомство відправило контролерів на маршрут, які від станції L до станції R контролюють усіх пасажирів, що заходять та виходять з транспорту. Вони назбирали інформацію про те, скільки квитків фактично було продано від станції L до станції R включно, але по дорозі до відомства загубили її. Щоб начальство їх не сварило, вони просять Вас швидко її порахувати і відправити ці дані у транспортне відомство.

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

Вхідні дані

У першому рядку подається 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).

Вихідні дані

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

Приклад

Вхідні дані #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
Вихідні дані #1
6
21
18
9
Автор Остап Столярчук
Джерело Дистанційна Літня Комп`ютерна Школа - літо 2013 року