감염

Lora의 저택에 쥐가 침입했다. 다행히 저택의 방들은 루트가 있는 트리로 나타낼 수 있다. 트리는 $N$개의 노드로 이루어져 있고, 노드에는 1번부터 $N$번까지 번호가 붙어 있다. 루트는 1번 노드다.

처음에는 어떤 노드도 감염되어 있지 않다. 이후 네 종류의 이벤트가 차례로 일어난다.

• 1 X: 노드 X가 감염된다.
• 2 X: Lora가 1번 노드부터 X번 노드까지 경로 위의 모든 노드에 동시에 초음파를 사용해 쥐를 없애려 한다. 초음파를 사용하는 노드가 감염되어 있으면 그 안의 쥐가 흩어져, 초음파를 사용하지 않는 직접 이웃 노드가 감염된다. 초음파를 사용한 노드는 감염 상태가 풀린다. 쥐가 옮겨 간 뒤 초음파는 멈추므로, 정리된 노드는 나중에 다시 감염될 수 있다.
• 3 X: Lora가 전문가를 고용해 X번 노드와 그 직접 자식 노드를 정리한다. 이 이벤트 후 X번 노드와 직접 자식 노드는 더 이상 감염되어 있지 않다.
• 4 X: X번 노드의 서브트리에 있는 감염된 노드의 총 개수를 구한다.

X번 노드의 서브트리는 X번 노드와 그 직접 및 간접 후손으로 이루어진 노드 집합이다.

첫 줄에 노드 개수 $N$이 주어진다. 둘째 줄에는 $N-1$개의 정수가 주어지며, $i$번째 정수는 노드 $i+1$의 부모 $p_{i+1}$이다. 셋째 줄에는 이벤트 개수 $Q$가 주어진다. 이어지는 $Q$개의 줄에는 각각 이벤트를 나타내는 정수 두 개가 주어진다.

종류 4인 이벤트마다 서브트리에 있는 감염된 노드의 개수를 한 줄에 하나씩 출력한다.

$1 \le N, Q \le 3 \times 10^5$

이벤트 1 3은 노드 3을 감염시킨다. 이벤트 2 5는 1번 노드부터 5번 노드까지 경로인 노드 1, 3, 5에 초음파를 사용한다. 노드 3은 감염되어 있고, 초음파를 사용하지 않는 이웃 노드는 4번뿐이므로 노드 3은 감염이 풀리고 노드 4가 감염된다. 이벤트 4 1은 트리 전체를 조사하며, 감염된 노드는 4번뿐이다. 이벤트 1 1은 노드 1을 감염시킨다. 이벤트 2 1은 노드 1에 초음파를 사용하므로 노드 2와 3이 감염되고 노드 1은 감염이 풀린다. 이벤트 4 3은 노드 3, 4, 5를 조사하며, 그중 3번과 4번이 감염되어 있다. 이벤트 3 1은 노드 1, 2, 3을 정리해 더 이상 감염되지 않은 상태로 만든다. 이벤트 4 3은 노드 3, 4, 5를 조사하며, 감염된 노드는 4번뿐이다.