E - Good Debugging

Any good coder knows that writing a program is only half the battle - and each member of The Team is most certainly a good coder. Maybe you're not a good coder, though, and you're wondering what the other half is. Debugging, of course!

The Team has a program with N (1 ≤ N ≤ 10⁶) lines (conveniently numbered 1..N) - and, unfortunately, every single line happens to initially have a bug in it. The programming language they're using will run the program from the start, line by line, and will always crash as soon as it encounters a total of L (1 ≤ L ≤ 10⁶) buggy lines.

The Team will make M (1 ≤ M ≤ 10⁶) attempts to debug the program. The ith attempt will consist of modifying every line in the inclusive range of lines a_i..b_i (1 ≤ a ≤ b ≤ N). In particular, these coders are so amazing that, every single time they modify a buggy line, it becomes perfect! However, every time they modify a perfect line, they instead introduce a bug into it. After every debugging attempt, The Team will run their new program, and observe how many lines of code it gets through before crashing. Sometimes, the program may even terminate successfully! The modified code will then carry over for future modifications.

Now, the members of The Team would like to know how their program will fare throughout the debugging session. Are your debugging skills good enough to figure that out?

Input

First line: 3 integers, N, M and L.
Next M lines: a_i and b_i, for i = 1..N

Output

M lines: Either 1 integer, the number of lines the program executes before crashing after the first i modifications, or the string "AC?" if it doesn't crash at all, for i = 1..M.

Sample Input

6 4 2
2 4
4 6
1 1
1 2

Sample Output

5
4
AC?
2

Explanation of Sample

The following table shows the status of each line of code after every modification, with newly-changed lines shown in bold font. Buggy lines represented by 1s, and correct ones by 0s.

After 1 modification, then, the program will encounter its second bug at line 5, at which point it will crash. Similarly, after 2 modifications, it will crash after 4 lines, and after 4 modifications, it will crash after just 2. After 3 modifications, however, it will not crash at all, as the program will contain only 1 bug at that point.

All Submissions
Best Solutions

Point Value: 30
Time Limit: 8.00s
Memory Limit: 64M
Added: Jun 01, 2012
Author: SourSpinach

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, TEXT, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)