After thousands of years repeating the title of this problem statement, always with an excited and inviting tone, Nathan finally persuaded his colleagues to go to the karaoke. He is feeling radiant with this achievement.
But there is a problem. After so much time trying to make his friends go to the karaoke, Nathan is afraid of embarrassing himself when he goes to sing the following classics of Brazilian music:
To avoid the humiliation, and to not discourage his fellows in future hang outs at the karaoke, Nathan decided to print all the song’s ciphers that are available in the karaoke, to check while he sings. However, this resulted in a colossal amount of paper, that he is not able to carry.
But the perseverance and ingenuity of an envious programmer is not something you should underestimate.
Nathan realized that, after all, there were only 7 musical notes. The specialists in this matter used to represent this notes with the letters A, B, C, D, E, F and G. Even more, it’s common that the same note appears several times in sequence. He decided then, to compress the songs, changing every occurrence of repeated notes with the note followed by how many times it occurs.
For instance, given the sequence
[(A,A,A,B,B,B,C,G,G,G,G,G,G,G,G,G,G,G)] the compressed version is [A3B3C1G11]
Unfortunately, Nathan also needs to pack his floral suit and to comb his beard – two homeric jobs – and he is out of time to compress the notes. Help him to not embarrass himself by writing a program that can solve this task.
Each input consist of a single line, a sequence of caracteres S such as |S| ≤ 105, formed only by the letters A, B, C, D, E, F and G.
For each input, print in a single line, such as each sequence of similar notes are replaced by the note that occurs and how many times it occurs, as showed in the example.
## Input
Each input consist of a single line, a sequence of caracteres S such as |S| ≤ 105, formed only by the letters A, B, C, D, E, F and G.
## Output
For each input, print in a single line, such as each sequence of similar notes are replaced by the note that occurs and how many times it occurs, as showed in the example.
[samples]
**Definitions**
Let $ N, Q \in \mathbb{Z}^+ $ denote the number of objects and number of changes, respectively.
Let $ P = (p_1, p_2, \dots, p_N) \in \{0, 1, \dots, N\}^N $ be the parent array, where $ p_i $ is the parent of object $ i $, and $ p_i = 0 $ means object $ i $ is root-level.
Let $ T = (t_1, t_2, \dots, t_Q) \in \{1, 2, \dots, N\}^Q $ be the sequence of toggle operations, where $ t_j $ is the object toggled at step $ j $.
Let $ \text{children}(i) = \{ j \in \{1, \dots, N\} \mid p_j = i \} $ denote the set of direct children of object $ i $.
Let $ \text{subtree}(i) $ denote the set of all objects in the subtree rooted at $ i $, including $ i $ itself.
Let $ s_i \in \{ \text{expanded}, \text{collapsed} \} $ be the state of object $ i $, initially all $ s_i = \text{expanded} $.
Let $ R_j $ be the total number of visible rows in the panel after the $ j $-th toggle.
**Constraints**
1. $ 1 \leq N \leq 3 \times 10^5 $
2. $ 1 \leq Q \leq 5 \times 10^5 $
3. $ p_i = 0 $ or $ 1 \leq p_i \leq N $ for all $ i \in \{1, \dots, N\} $
4. $ 1 \leq t_j \leq N $ for all $ j \in \{1, \dots, Q\} $
5. Each toggle operation is on an object that is currently visible and has at least one child.
**Objective**
For each $ j \in \{1, \dots, Q\} $:
- Toggle $ s_{t_j} $: if $ s_{t_j} = \text{expanded} $, set to $ \text{collapsed} $; else set to $ \text{expanded} $.
- Compute $ R_j = \left| \bigcup_{\substack{i=1 \\ s_i = \text{expanded}}}^N \text{subtree}(i) \right| $, i.e., the total number of objects in all expanded subtrees.
- Output $ R_1, R_2, \dots, R_Q $.