Tartarus is where the souls of the wicked go after death to be tormented for eternity. Among the unfortunate beings were the Danaïdes, daughters of Danaus. These unfortunate women are condemned to fill a barrel with pitchers of water until the end of time. Not only are their pitchers perforated, but the barrel they are trying to fill is as well.
It is the middle of summer and as Persephone roams above the Earth, Hades gets more and more irritable with each passing day. When taking some time off from managing the dead, Hades has decided to amuse himself by monitoring the punishment of the Danaïde sisters (labelled from to ).
All of the events which occur in the punishment will take one of the following forms:
F pThe Danaïde sister completely fills her jug with water.
D pThe Danaïde sister has her jug entirely drained of water.
R qThe states of all of the pitchers are reverted to what they were immediately after the operation was performed, undoing all of their hard work.
XThe states of all pitchers are inverted (empty becomes full and vice-versa).
The pitchers of all of the Danaïdes are initially empty.
After watching operations, Hades realizes he needs to return to his work. However, for each operation, Hades would like to know the number of pitchers which were filled along with the maximum number of pitchers within the most recent operations. The latter query is to ensure the morale of the Danaïdes is never too high.
Can you write a program to help Hades?
The first line of input will contain three space-separated integers and , representing the number of sisters, the number of operations to be performed, and the value chosen by Hades respectively.
The next lines will each contain either just a character , or a character and an integer or , depending on the value of . The character denotes which operation is taking place, and the integers and represent the index of the sister and the index of the previous command respectively.
X , ,
Subtask 1 [20%]
Subtask 2 [80%]
After every operation, output two space separated integers on a single line:
The number of pitchers which are currently filled, and the maximum number of pitchers filled after the current operation takes place within the most recent operations (including the current one).
Note: Even though the states of the pitchers may be reverted to an earlier command, the order of the operations (and thus the last operations) are not affected.
Sample Input 1
5 9 2 F 1 F 5 F 2 D 5 F 1 D 1 R 2 R 0 F 3
Sample Output 1
1 1 2 2 3 3 2 3 2 2 1 2 2 2 0 2 1 1
The pitcher is already filled, so this command has no effect upon it.
The number of pitchers filled after the operation
F 2 would be considered the command away, and as such its value does not contribute to the maximum of pitchers filled in the past operations.
The states of the pitchers are reverted to being all empty. This is because the "" command takes place prior to any of the actual operations.
The states of the pitchers considered for the maximum are the
R 2, and
R 0 commands. Note the final ordering of the commands is unaffected by the reversion of the state of the pitchers.
Sample Input 2
10 7 3 F 1 X D 1 D 9 R 2 D 3 R 4
Sample Output 2
1 1 9 9 9 9 8 9 9 9 8 9 8 9