The ACM-ICPC World Finals have begun! However, let's not be too hasty - even though The Team features three of the best coders to have ever coded, they know the importance of first determining what to code.
The contest features problems (conveniently numbered ), and runs for minutes. Every problem is associated with a distinct colour - and each time a team solves a problem, they receive a balloon of its corresponding colour, which is visible to all. Obviously, easier problems will be solved by more teams, and so more of their balloons will be floating around in the contest room. Additionally, The Team has found that earlier problems in the set tend to be easier. Therefore, given 2 problems and , is considered easier than if there are either more balloons than balloons in the room, or there are an equal number of balloons and .
At the start of the contest (at the 0th minute), there are no balloons in the room, of course. After that, during every minute (for ), problem is either solved by The Team (which will only happen if they have not solved it previously), or by some opposing team. The former possibility is represented by , and the latter by . In either case, a balloon is brought into the room. However, in the former case, The Team will no longer care about problem in the slightest.
At the end of every minute after the 0th one, the members of The Team want to get their bearings on what they should be working on (and what they should be staying away from). Specifically, out of problems that they haven't yet solved, they want to know what the single easiest and the single hardest problems are, given the information that can be gleaned from the balloons. These two values may be the same, if The Team has only one problem left to solve. If they've solved all of the problems already, they can instead commence the process of making distracting noises. Are you smart enough to figure out what The Team's strategy throughout the contest will be?
Input Specification
First line: 2 integers, and
Next lines: 2 integers, and , for
Output Specification
lines: Either 2 integers, the easiest followed by the hardest
unsolved problem number after the first minutes, or the string
Make noise
if all problems have been solved by The Team, for .
Sample Input
3 8
2 2
2 1
1 1
2 3
2 3
1 2
1 3
2 1
Sample Output
2 3
1 3
2 3
2 3
3 2
3 3
Make noise
Make noise
Explanation of Sample
After the first minute, we've seen 1 balloon for problem 2, and 0 balloons for problems 1 and 3. Therefore, the easiest problem is 2, since it has the most balloons, and the hardest problem is 3, since it's the last problem with the least balloons.
After the second minute, the counts for the 3 problems are 1, 1, and 0. The easiest problem is now 1, since it's the first problem with the most balloons, while the hardest is still 3.
After the third minute, the counts for the 3 problems are 2, 1, and 0, but problem 1 has now been solved by The Team. The easiest remaining problem is 2, and the hardest is 3.
After the fourth minute, the counts for the 3 problems are 2 (solved), 1, and 1. The easiest unsolved problem is 2, and the hardest is 3.
After the fifth minute, the counts for the 3 problems are 2 (solved), 1, and 2. The easiest unsolved problem is 3, and the hardest is 2.
After the sixth minute, the counts for the 3 problems are 2 (solved), 2 (solved), and 2. The only unsolved problem is 3.
After the seventh and eighth minutes, all 3 problems have been solved by The Team, so noise should be made.
Comments
I think it should be noted that the input actually does give a scenario where the team is given a problem to solve which they already solved. Not sure if I just misinterpreted this statement or if there is an inconsistency with the problem statement and the input data.
Thanks for pointing that out! That issue affects case #4, and we'll get it corrected.