In a fast developing firm, new employees are often hired. Each new employee $p$ is assigned a direct superior, whose superiors (both direct and indirect) become indirect superiors of $p$.
We call the direct superior of $p$ a superior of degree 0. The superior of a superior of degree 0 has a degree equal to 1. In general, a superior of a superior of degree $k$ has degree $k+1$. In this way, an employee is a subordinate of his immediate superior and superiors of higher degree. This defines a hierarchy of all employees, which has the founder of the company on its top.
The history of all employees who have joined the company since the foundation is recorded. Some employees wonder for how many subordinates they are superiors of degree $k$. Would you mind writing a program, which will assist them in solving this problem, so that they could go back to work?
Input Format
In the first line of the standard input there is an integer $n$ ($1 ≤ n ≤ 10^{5}$), denoting the number of events. The following n lines contain descriptions of the events, one per line, given in chronological order.
An event of hiring a new employee is described by a character 'Z' and two integers $p_{i}$ and $s_{i}$ ($2 ≤ p_{i} ≤ 10^{5}$, $p_{i} ≠ p_{j}$ for $i ≠ j$), which represent the numbers of the new employee and his immediate superior, respectively. $s_{i}$ is equal to the number of some employee, who is currently hired. The founder is assigned number 1.
A question from an employee $q_{i}$ about the number of his subordinates, for whom he is a superior of degree $k_{i}$, is described by a character 'P' and two integers $q_{i}$ and $k_{i}$ ($1 ≤ q_{i} ≤ 10^{5}$, $0 ≤ k_{i} ≤ 10^{5}$).
Before the first event the founder was the only person working in the firm.
Output Format
For each question from an employee output one line to the standard output with one integer equal to the number of subordinates of this employee, for whom he is a superior of degree $k_{i}$.
Example
Input
8 Z 2 1 P 1 0 Z 3 1 Z 4 2 P 1 1 P 1 0 Z 5 2 P 2 0
Output
1 1 2 2