题目描述

Lora 的豪宅正在遭受老鼠入侵。豪宅中的房间可以看成一棵以 1 为根的有根树，共有 N 个结点，编号为 1..N。

初始时没有任何结点被感染。接下来会依次发生 Q 个事件，每个事件属于以下四类之一：

1. 1 X

结点 X 变为感染状态。

2. 2 X

Lora 在从根结点 1 到结点 X 的整条路径（含端点）上同时使用超声波。

• 这条路径上的所有结点在操作结束后都会变为未感染；
• 若其中某个结点原本被感染，则其中的老鼠会向外逃散到它的所有当前没有被使用超声波的直接相邻结点中，这些相邻结点会变为感染状态。

待老鼠扩散完成后，超声波停止。也就是说，被清除的结点将来仍然可能再次感染。

3. 3 X

Lora 雇佣专业人员清理结点 X 以及它的所有直接儿子。

事件结束后，结点 X 与它的所有直接儿子都变为未感染状态。

4. 4 X

询问结点 X 的子树中当前共有多少个感染结点。

这里，X 的子树定义为：包含 X 本身，以及它的所有直接或间接后代的结点集合。

请你处理所有事件，并输出所有类型 4 询问的答案。

输入格式

第一行一个整数 N，表示树的结点数。

第二行包含 N-1 个整数，其中第 i 个数（i = 1..N-1）表示结点 i+1 的父亲。

第三行一个整数 Q，表示事件个数。

接下来 Q 行，每行两个整数，表示一个事件。

输出格式

对于每个 4 X 事件，输出一行一个整数，表示答案。

数据范围

• 1 <= N, Q <= 3 × 10^5

子任务

随机树生成方式：对每个结点 i (i > 1)，其父亲 p_i 在区间 [1, i-1] 中均匀随机生成。

样例

输入

5
1 1 3 3
8
1 3
2 5
4 1
1 1
2 1
4 3
3 1
4 3

输出

1
2
1