tree-1

Everyone is tired after searching for Mr. NU for hours after finally finding him in the Spiral Maze.

The NU-Tech team has N members. The members are numbered from 1 to N. The team has a superiority hierarchy. Every member has one immediate superior. The superior of a superior of a member is also a superior to that member. So, a member may have one or more superiors but only one immediate superior.

As an exercise to determine those worthy of Resting hours, the following procedure is adopted.

You are given a list of orders. Each order is of the form ""
where Type is either 1,2 or 3 and ID is a number S (1 ≤ S ≤ N) that denotes a soldier.

There are three types of orders:

Type 1: 
All the members who have S as one of their superior will wake up.

Type 2:
All the members who have S as one of their superior will go to sleep.

Type 3:
Count and output the number of members who are awake and have S as one of their superior.

NOTE: Among all members there is one senior most member who does not have any superior. He is the In-Charge of the whole Committee.

Input :

The first line contains N, the number of members. The next line contains N space separated integers. The ith integer represents the immediate superior of the ith member.
The immediate superior of the NU-Tech Committee In-Charge will be '0'.

The third line contains Q, the number of orders.
Each of the next Q lines contain two integers, the type of order and S.

Output :

For each Type-3 order, output the number of members who are awake and have the given member as their superior.

Constraints :

1 ≤ N ≤ 100000

1 ≤ Q ≤ 100000

1 ≤ Type ≤ 3

1 ≤ S ≤ N

A member cannot be his own superior.

SAMPLE INPUT
3
2 0 1
3
3 1
2 1
3 1

SAMPLE OUTPUT
1
0

Explanation

Initially all members are awake. 
There is only one member who has member 1 as his superior i.e. member 3. So the answer of the first Type 3 order is 1.
After the order "2 1", all members who have 1 as one of their superiors (here, only member 3) will go to sleep.
Therefore, the answer of the next order "3 1" is 0.

Source: hackerearth | Difficulty: UNKNOWN_DIFFICULTY


Solutions: