
ZOJ Problem Set  3324
Mee is the only genius engineer in country Nii who is fond of making machines. One day, when he was working with his research, an amazing idea thrilled through his head and he decided to make a powerful machine which seemed to be able to solve an important problem in his research. As the picture shown above, the machine is made up of n blocks in a line numbered from 0 to n  1. Each moment there is one of the two possible actions.
The following picture is the situation after a pressure from 0 to 2 and a pressure from 2 to 3. The following picture is the situation after releasing the first pressure. During the progress, the blocks in the original position are considered to promise something and are called Hblocks. The consecutive one or more Hblocks even form an Hgroup. Mee knew that recording the number of Hgroups would be extremely helpful. So after each moment, the number of Hgroups should be recorded. But soon he was facing a serious problem. n could be large and there may be no enough material to finish the machine. What's more, it was impossible to manually calculate the number of Hgroups. So he wants a program to simulate the machine and record the number of Hgroups for him. Input The first line is the number of test cases T (T <= 10). In each case the first line is n and m (1 <= n <= 10^{8}, 0 <= m <= 20000), where n is the number of blocks and m is the number of actions. The following m lines are the m actions. Two kinds of expressions exist.
Output For each case, first print a line "Case #?:" where ? is the case number starting from 1. Then print the number of Hgroups after each action. Sample Input 2 6 6 p 2 2 r 2 2 p 3 3 p 2 3 p 2 2 r 2 3 10 3 p 2 7 p 3 6 p 4 5 Sample Output Case #1: 2 1 2 2 2 2 Case #2: 2 2 2 Author: ZHUANG, Junyuan Source: The 7th Zhejiang Provincial Collegiate Programming Contest 