Accept in 150 seconds#4461
In the naughty kingdom they decided to verify the work of software engineers, whether they had been cheated by the programmers. The engineers were writing a software for selling online tram tickets. The selling occurred in such a way: each passenger was ordering a ticket from station to station . But the program of these unfortunate engineers informs the government only the number of passengers who took a tram on each station () and the number of passengers who leave the tram (). The transport authority sent the inspectors to control the information. The inspectors were checking all passengers who took the tram from station and left it at station . They collect the information about how many tickets were really sold from station to station . However on 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 is a straight line along which there are stations. The stations are numbered from , but it is possible to travel only from the station with smaller number to a bigger one.
First line of input contains positive integers: – number of stops, – number of inspectors on a line (N \le 10^5, M \le 10^5). In a next lines, line i+1 describes a pair of number for -th stop: – how many people took a tram at station and – how many people left the tram at a station (0 \le \text{In}, \text{Out} \le 10^4, \text{Out}_1 = 0, \text{In}_N = 0, on a last stop () all the passengers leave the tram). In the next lines, each containing two pairs of numbers , – the numbers of station, where the inspectors were working (1 \le L < R \le N).
For each inspector in the order in which they were given, write how many tickets were sold between stops and inclusively.
Example 1