Accept in 150 seconds
In the naughty kingdom the minister decided to verify the work of software engineers, weather they did not cheat them. The engineers were writing a software for selling online tram tickets. The selling was occured in such way: each passenger was ordering a ticket from station A to station B. But the program of this unfortunate engineers inform the government only the number of passengers who took a tram on each station (In) and the number of passengers who leave the tram (Out). The transport authority sent the inspectors to control the information. The inspectors was checking all passengers who took the tram from station L and left it at station R. They collect the information about how many tickets was really sold from station L to station R. However in their way to department inspectors lost all of their information.
The inspectors are asking you to count quickly this data and send them to the transport authority.
The tram route it is a straight line along which there are stations. The stations are numbered from 1, but it is possible to travel only from the station with smaller number to bigger one.
Input
First line of input contains 2 positive integers: N – number of stops, M – number of inspectors on a line (N ≤ 10^5, M ≤ 10^5). In a next N lines, line i+2 describes a pair of number for i-th stop: In – how many people took a tram on station i and Out – how many people leave the tram on a station i. (0 ≤ In, Out ≤ 10^4, Out[1] = 0, In[N] = 0, on a last stop (N) all the passengers leave the tram). In next M lines also two pair of numbers L, R – the numbers of station, where the inspectors was working (1 ≤ L < R ≤ N).
Output
For each inspectors in the order in which they were set, write how many tickets were sold berween stops including L and R.