SP14889 GOODC - Good Strategy

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 $ N $ ( $ 1 \leq N \leq 10^6 $ ) problems (conveniently numbered $ 1..N $ ), and runs for $ M $ ( $ 1 \leq M \leq 10^6 $ ) 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 $ i $ and $ j $ , $ i $ is considered easier than $ j $ if there are either more $ i $ balloons than $ j $ balloons in the room, or there are an equal number of balloons and $ i<j $ . At the start of the contest (at the 0th minute), there are no balloons in the room, of course. After that, during every minute $ i $ (for $ i=1..M $ ), problem $ p_i $ ( $ 1 \leq p_i \leq N $ ) 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 $ t_i=1 $ , and the latter by $ t_i=2 $ . In either case, a $ p_i $ balloon is brought into the room. However, in the former case, The Team will no longer care about problem $ p_i $ 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're 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** First line: 2 integers, $ N $ and $ M $ Next $ M $ lines: 2 integers, $ t_i $ and $ p_i $ , for $ i = 1..M $ **Output** $ M $ lines: Either 2 integers, the easiest followed by the hardest unsolved problem number after the first $ i $ minutes, or the string "Make noise" if all problems have bee solved by The Team, for $ i = 1..M $ .

N/A

N/A