18437번 - 회사 문화 5

문제

총 N명의 직원이 재직 중인 회사가 있고, 각 직원은 1번부터 N번까지 번호가 매겨져 있다. 이 회사는 수직적인 구조를 가지고 있고, 대표를 제외한 모든 직원은 한 명의 직속 상사를 갖고 있다. 직속 상사의 직속 상사도 상사이고, 직속 상사의 상사도 상사이다. 따라서, 대표를 제외한 모든 직원은 한 명 이상의 상사를 가지고 있고, 한 명의 직속 상사를 갖고 있다. 상사가 없는 사람은 대표이다.

이 회사가 가지고 있는 문화는 아래와 같은 쿼리로 나타낼 수 있다. 가장 처음에 컴퓨터는 켜져있는 상태이다.

• 1 i: i번 직원을 상사로 가지고 있는 모든 직원은 컴퓨터를 켠다.
• 2 i: i번 직원을 상사로 가지고 있는 모든 직원은 컴퓨터를 끈다.
• 3 i: i번 직원을 상사로 가지고 있는 직원 중에서 컴퓨터가 켜져있는 사람의 수를 출력한다.

입력

첫째 줄에 직원의 수 N (1 ≤ N ≤ 100,000)이 주어진다.

둘째 줄에는 각 직원의 상사 번호가 주어진다. i번째 정수는 i번 직원의 직속 상사 번호이다. 대표의 번호는 1번이고, 상사 번호로 0이 주어진다.

셋째 줄에 쿼리의 수 M (1 ≤ M ≤ 100,000)이 주어진다.

넷째 줄부터 M개의 줄에 쿼리가 주어진다. (1 ≤ i ≤ N)

출력

3번 쿼리의 결과를 한 줄에 하나씩 출력한다.

제한

힌트