Linux and OS X users are certainly no strangers to package managers. Through a package manager, you can install a software package with a single command, and the package manager will help you download the package from a software source while automatically resolving all dependencies (i.e., downloading and installing other packages that the current package depends on) and completing all configurations. The apt-get used by Debian/Ubuntu, the yum used by Fedora/CentOS, and the homebrew available on OS X are all excellent package managers.

You have decided to design your own package manager. Inevitably, you must solve the dependency problem between packages. If package $A$ depends on package $B$, then package $B$ must be installed before package $A$ can be installed. At the same time, if you want to uninstall package $A$, you must first uninstall package $B$. You have now obtained the dependency relationships between all packages. Furthermore, due to your previous work, except for package 0, every package in your manager depends on exactly one other package, and package 0 does not depend on any package. There are no cycles in the dependency relationships (if there are $m$ ($m \ge 2$) packages $A_1, A_2, A_3, \dots, A_m$, where $A_1$ depends on $A_2$, $A_2$ depends on $A_3$, $A_3$ depends on $A_4$, ..., $A_{m-1}$ depends on $A_m$, and $A_m$ depends on $A_1$, then these $m$ packages are said to form a cycle), and of course, no package depends on itself.

Now you need to write a dependency resolution program for your package manager. According to feedback, users want to quickly know how many packages will actually have their installation status changed when installing or uninstalling a certain package (i.e., how many uninstalled packages will be installed by an install operation, or how many installed packages will be uninstalled by an uninstall operation). Your task is to implement this part. Note that installing an already installed package or uninstalling an uninstalled package will not change the installation status of any package; in this case, the number of packages whose installation status changes is 0.

Input

Read data from the file manager.in.

The first line of the input file contains one integer $n$, representing the total number of packages. Packages are numbered starting from 0.

The next line contains $n-1$ integers, separated by single spaces, representing the package IDs that packages $1, 2, 3, \dots, n-2, n-1$ depend on, respectively.

The next line contains one integer $q$, representing the total number of queries.

Following this are $q$ lines, each containing one query. Queries are of two types:

• install x: Install package $x$.
• uninstall x: Uninstall package $x$.

You need to maintain the installation status of each package; initially, all packages are in the uninstalled state. For each operation, you need to output how many packages will have their installation status changed by this operation, and then apply this operation (i.e., change the installation status you are maintaining).

Output

Output to the file manager.out.

The output file includes $q$ lines.

The $i$-th line of the output file should output one integer, representing the number of packages whose installation status changes in the $i$-th operation.

Examples

Input 1

7
0 0 0 1 1 5
5
install 5
install 6
uninstall 1
install 4
uninstall 0

Output 1

3
1
3
2
3

Note 1

Initially, all packages are in the uninstalled state. Installing package 5 requires installing packages 0, 1, and 5. After that, installing package 6 only requires installing package 6. At this point, packages 0, 1, 5, and 6 are installed. Uninstalling package 1 requires uninstalling packages 1, 5, and 6. At this point, only package 0 remains in the installed state. After that, installing package 4 requires installing packages 1 and 4. At this point, 0, 1, and 4 are in the installed state. Finally, uninstalling package 0 will uninstall all packages.

Input 2

10
0 1 2 1 3 0 0 3 2
10
install 0
install 3
uninstall 2
install 7
install 5
install 9
uninstall 9
install 4
install 1
install 9

Output 2

1
3
2
1
3
1
1
1
0
1

Examples 3

See manager/manager.in and manager/manager.ans in the contestant's directory.

Constraints