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 ~N~ slices, numbered ~1~ to ~N~ from left to right. To add cheese topping to the pizza, you have a special machine that can add ~1~ unit of cheese on each slice in a consecutive group of slices (for example, you can add ~1~ unit of cheese on each slice between slice ~2~ and ~4~ inclusive, adding a total of ~3~ units of cheese). Each slice can carry an unlimited amount of cheese.
You plan to run the machine ~R~ times, each time adding ~1~ 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 ~x~ to slice ~y~, 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 ~N~, the length of your long pizza.
The second line will consist of two space-separated integers ~x~ and ~y~, indicating that the customer is planning to eat every slice between slice ~x~ and slice ~y~ inclusive.
The third line will contain the integer ~R~, the number of times you plan to run the topping machine.
The following ~R~ lines will each describe one planned run of the topping machine using 2 space-separated integers, ~l~ and ~r~ ~(l \le r)~, indicating that the machine will add ~1~ unit of cheese onto each slice between slices ~l~ and ~r~, 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 ~4~ of the ~10~ available marks, ~R \le 1000~ and ~N \le 10^5~.
For the remaining ~6~ marks, ~R \le 4000~ and ~N \le 10^7~.
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 ~3-5~ have a total of ~6~ units of cheese.