HAPPYTL - Happy Telephones

no tags 

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 taps all phone conversations.

The police wants to hire the appopiate number of operators to listen to all conversations in a given period of time. Unfortunately, each of their operators can listen to one conversation only before needing a really long break to rest from the effort.

As a contractor of 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 be put in jail as well, 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 N (1 ≤ N < 10 000) and the number of intervals M (1 ≤ M < 100). This is followed by N lines describing the telephone calls, each one consisting of four integers Source, Destination, Start and Duration. Source and Destination identify the pair of telephone numbers establishing the connection (0 ≤ Source, Destination ≤ 10 000 000). Start and Duration are the start time and duration of the call in seconds (1 ≤ Duration ≤ 10 000 and Start ≥ 0). You can safely assume that the sum of Start and Duration fits into a 32-bit signed integer.

Afterwards follow M lines containing the time intervals the police are interested in, each described by two integers Start and Duration, in the same format and with the same meaning and constraints as those in the telephone calls. The last test case is represented by N = M = 0 and must not be processed.


For each of the M intervals of each test case, print the number of calls that are active during at least one second of the interval.

Sample Input

3 2
3 4 2 5
1 2 0 10
6 5 5 8
0 6
8 2
1 2
8 9 0 10
9 1
10 1
0 0

Sample Output


Problemsetter: Manuel Freire 

hide comments
Rishav Goyal: 2014-04-14 18:58:40

Naive Approach is too fast.!

Nurav: 2012-12-25 11:15:40

the intervals are exclusive, 1st and last second of interval not included.

David adroy: 2012-09-26 10:03:34

hey any tricky cases???...plzz giv some more test cases....

Mitch Schwartz: 2011-11-27 12:41:11

That sounds good. Since this situation is rare, it's probably too much trouble to let AC users of TTREAT know they can resubmit their code here. I'll leave a comment on TTREAT as a courtesy; it can be removed if there seems to be a better solution.

David García Soriano: 2011-11-27 12:41:11

I agree with [Trichromatic] XilinX.

[Rampage] Blue.Mary: 2011-11-27 12:41:11

I'd like to remove that one. Removing this one will mutilate the whole SWERC contest problem set.

Last edit: 2011-11-24 14:32:52
David García Soriano: 2011-11-27 12:41:11

I see. Although there may be some confussion, as TTREAT looks like it should be problem "Trick or treat", not "Happy telephones".

Last edit: 2011-11-24 12:58:44
Mitch Schwartz: 2011-11-27 12:41:11

This problem is already on SPOJ, see TTREAT.

Added by:David García Soriano
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Southwestern Europe Regional, SWERC 2009