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 включно.