Gats and the Cut Strings
Gats keeps his yarn castle as rooms connected by strings. The strings form a tree, so when every string is intact there is exactly one route between any two rooms.
Each room initially contains drops of milk. Gats has a notebook containing records, applied one by one in the order written. Each record is one of the following:
C e: the string with index is cut. If it has already been cut, nothing changes.D v: all milk in room is drunk, changing its amount to . If room already has drops, nothing changes.Q v: Gats asks for the total number of milk drops currently in all rooms reachable from room using only intact strings.
Your task is to output the answer to every report record.
Input
The first line contains two integers and (, ), the number of rooms and records.
Output
Let be the number of records of type Q.
For the -th record of type Q in chronological order, print one line containing a single integer: the total number of milk drops currently in all rooms reachable from the room named in that record, using only intact strings.
Therefore, output exactly lines. If , print nothing.
Samples
Sample 1
Input
5 7 4 2 7 1 3 1 2 2 3 2 4 4 5 Q 3 D 2 Q 5 C 3 Q 5 D 5 Q 4
Output
17 15 4 1
Initially all rooms are connected, so the first report is . After D 2, room is empty. After C 3, the string between rooms and is cut, so from room only rooms and are reachable, with drops. After , the last report is .