题目描述

给一棵 $n$ 个点的有根树，点从 $1$ 开始标号，其中 $1$ 号点为树根；每个点有一个颜色。

一个点在的同色连通块，指仅保留两端结点颜色相同的边时，这个点在的联通分量。

定义一个同色连通块的高度为 $\max(dep_a-dep_b+1)$，其中 $a,b$ 属于该同色连通块；$dep_x$ 是 $x$ 到根节点简单路径上的边数。

你需要支持以下 3 种操作：

1. 给出 $x$ 和 $y$，把点 $x$ 的颜色改成 $y$；
2. 给出 $x$ 和 $y$，把点 $x$ 所在的同色连通块中所有点颜色改为 $y$；
3. 给出 $x$，问点 $x$ 的颜色，$x$ 所在同色连通块的点数和高度。

输入格式

第一行一个整数 $n$；

第二行 $n-1$ 个整数，第 $i$ 个整数表示 $i+1$ 号点的父亲 $f_i$，保证 $f_i<i$；

第三行 $n$ 个整数表示每个点的初始颜色；

第四行一个整数 $m$，表示操作数；

之后 $m$ 行，每行若干个整数形如 1 x y 或 2 x y 或 3 x 表示题目中的操作。保证 $1 \le x \le n$.

保证至少会有一个 3 操作。

输出格式

对于每个 3 操作，输出一行三个整数，依次表示：点 $x$ 的颜色，$x$ 所在同色连通块的点数，$x$ 所在同色连通块的高度。

输入输出中相邻两个整数用空格隔开。

样例输入

10
1 1 1 3 4 2 4 2 3
16 20 29 16 23 6 29 21 1 22
10
3 4
3 4
2 6 20
2 1 8
2 2 8
1 9 21
3 6
3 2
1 3 11
1 4 17

样例输出

16 2 2
16 2 2
20 1 1
8 3 2

子任务

对所有数据保证，$1 \le n,m \le 10^5$，任意时刻所有点的颜色标号是 $[1,30]$ 中的整数。

1. $n,m \le 1000$（20 分）
2. 没有操作 2（30 分）
3. 任意时刻颜色只会为 $1$ 或 $2$（20 分）
4. 没有特殊性质（30 分）

时间限制：$\texttt{1s}$

空间限制：$\texttt{512MB}$