Command Frequency Counter

Each entry is one of cmd1, cmd2, cmd3, or !j, which means executing the command represented by the j-th entry. Count how many times each of the three commands is ultimately executed over all entries. Valid input on this site guarantees that every reference chain eventually reaches an actual command; forward and backward references are allowed, but there are no reference cycles.

This site's standard input/output is stated explicitly.

输入格式

The first line contains n, followed by n command tokens, 1≤n≤100000 (this site's range); the j in !j is 1..n.

输出格式

Output the execution counts of cmd1, cmd2, and cmd3, separated by spaces.

样例 1

输入：

7
cmd1
cmd2
cmd3
!1
!2
cmd3
cmd1

输出：

3 2 2

样例 2

输入：

3
!3
!1
cmd2

输出：

0 3 0

样例 3

输入：

1
cmd3

输出：

0 0 1

样例说明

Example 1: cmd1, cmd2, and cmd3 are executed 3, 2, and 2 times respectively. Example 2: the first two entries both eventually reference the third entry, cmd2, so the output is 0 3 0. Example 3: there is only one cmd3, so the output is 0 0 1.