SP14891 GOODE - 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 \leq N \leq 10^6 $ ) 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 \leq L \leq 10^6 $ ) buggy lines. The Team will make $ M $ ( $ 1 \leq M \leq 10^6 $ ) attempts to debug the program. The $ i $ th attempt will consist of modifying every line in the inclusive range of lines $ a_i..b_i $ ( $ 1 \leq a \leq b \leq 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?

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

$ 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 $ .