情报传递

• 时间限制：3 秒
• 内存限制：512 MiB

题目描述

奈特公司有一个由 $n$ 名情报员组成的情报网络。除一名大头目外，每名情报员都有且仅有一名上线；任意两名情报员都能沿着唯一的联络路径传递情报。

公司每天恰好派发一个任务：

1. 指派 $T$ 号情报员开始搜集情报；
2. 将一条情报从 $X$ 号情报员传递给 $Y$ 号情报员。

所有情报员最初的危险值均为 $0$。一旦某名情报员开始搜集情报，他的危险值便持续增加：开始搜集当天仍为 $0$，一天后为 $1$，两天后为 $2$，依此类推。传递情报不会增加危险值。

每条待传递的情报都有风险控制值 $C$。在从 $X$ 到 $Y$ 的路径上，危险值严格大于 $C$ 的情报员会对该条情报构成威胁。

对于每个传递情报任务，请求出路径上的情报员总数以及其中构成威胁的情报员数量。

输入格式

第一行包含一个正整数 $n$，表示情报员数量。

第二行包含 $n$ 个非负整数 $P_1,P_2,\ldots,P_n$。$P_i$ 表示 $i$ 号情报员的上线编号；$P_i=0$ 表示 $i$ 号情报员是大头目。输入保证这些关系构成一棵树。

第三行包含一个正整数 $q$，表示任务数量，每天执行一个任务。

随后 $q$ 行按时间顺序描述任务：

• 1 X Y C：将情报从 $X$ 号情报员传递给 $Y$ 号情报员，风险控制值为 $C$；
• 2 T：指派 $T$ 号情报员开始搜集情报。

输出格式

对于每个传递情报任务输出一行两个整数，依次表示路径上的情报员总数和其中构成威胁的情报员数量。

样例输入 1

7
0 1 1 2 2 3 3
6
1 4 7 0
2 1
2 4
2 7
1 4 7 1
1 4 7 3

样例输出 1

5 0
5 2
5 1

数据范围

$1\le n,q\le 2\times 10^5$，$0\le P_i,C_i\le n$，$1\le T_i,X_i,Y_i\le n$。