Happy Telephones#1259
In the land of Eden, all phone conversations are happy ones. People complaining on the phone are immediately put in jail. To enforce this law, the police tap all phone conversations.
The police want to hire the appropriate number of operators to listen to all conversations in a given period of time. Unfortunately, each operator can listen to only one conversation before needing a long break to rest from the effort.
As a contractor for the police department, you have been asked to provide a program capable of determining the required number of operators. If the program does not work correctly, you will also be put in jail along with all the unhappy complainers. Do you really want to end up there?
Each test case starts with two integers denoting the number of phone calls (1 \leq N < 10\,000) and the number of intervals (1 \leq M < 100). This is followed by lines describing the telephone calls, each with four integers: , , , and . and identify the pair of telephone numbers establishing the connection (0 \leq \textbf{Source}, \textbf{Destination} \leq 10\,000\,000). and are the call's start time and duration in seconds (1 \leq \textbf{Duration} \leq 10\,000, \textbf{Start} \geq 0). You can safely assume that the sum of and fits into a -bit signed integer.
Then lines follow, each containing two integers and , describing the time intervals the police are interested in (in the same format and with the same constraints as the telephone calls). The last test case is represented by N = M = 0 and must not be processed.
For each of the intervals of each test case, print the number of calls that are active during at least one second of the interval.
Example 1