시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 82 41 20 55.556%

문제

총 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번 쿼리의 결과를 한 줄에 하나씩 출력한다.

예제 입력 1

3
0 1 2
8
3 1
2 1
3 1
1 1
3 1
2 2
3 1
3 2

예제 출력 1

2
0
2
1
0

출처