You are in charge of adding cheese topping to a pizza prepared for a special customer. This pizza is a very long rectangular strip. It is divided into slices, numbered to from left to right. To add cheese topping to the pizza, you have a special machine that can add unit of cheese on each slice in a consecutive group of slices (for example, you can add unit of cheese on each slice between slice and inclusive, adding a total of units of cheese). Each slice can carry an unlimited amount of cheese.
You plan to run the machine times, each time adding unit of cheese to each slice in a given range.
The customer is on a diet. When he eats the section of pizza from slice to slice , inclusive, he would like to know how many units of cheese he is consuming.
NOTE FOR PYTHON USERS: If your program receives TLE (time limit exceeded), you should try submitting using the PyPy interpreter: when you are submitting your code, try using "PyPy 3" or "PyPy 2" as the language, instead of "Python 3" or "Python 2".
The first line will contain the integer , the length of your long pizza.
The second line will consist of two space-separated integers and , indicating that the customer is planning to eat every slice between slice and slice inclusive.
The third line will contain the integer , the number of times you plan to run the topping machine.
The following lines will each describe one planned run of the topping machine using 2 space-separated integers, and , indicating that the machine will add unit of cheese onto each slice between slices and , inclusive.
Please output the total number of units of cheese on all of the slices the customer is planning to eat.
Constraints and Partial Marks
For of the available marks, and .
For the remaining marks, and .
10 3 5 3 2 6 4 5 3 3
Explanation of Sample Output
After running the machine three times, the amount of cheese on each slice of pizza is as follows:
Slice #: 1 2 3 4 5 6 7 8 9 10 Cheese: 0 1 2 2 2 1 0 0 0 0
Therefore, slices to have a total of units of cheese.