Tree Major GPA Operations

You are given a rooted tree with n students (nodes), each having a GPA. The tree structure is defined as follows: the root has depth \(0\) and for any node \(w\), its depth is defined as \(dep[w]=dep[parent(w)]+1\). The tree is undirected but has a designated root.

A student's major is defined as the connected component that the student belongs to in the following subgraph: from the original tree, retain only those edges whose two endpoints have the same GPA. In other words, if you consider the subgraph of the tree in which an edge exists between nodes \(u\) and \(v\) if and only if \(gpa[u]=gpa[v]\), then the major of a student is the connected component (in this subgraph) that contains that student.

The resentment value of a major is defined as \[ \max_{a, b \text{ in major}} \{dep[a]-dep[b]+1\} \] which is equivalent to \(\max(\text{depth}) - \min(\text{depth}) + 1\) over all nodes in that connected component.

You need to process the following operations:

• Operation 1: 1 x y — set the GPA of student \(x\) to \(y\).
• Operation 2: 2 x y — set the GPA of every student in the major (connected component) of student \(x\) to \(y\).
• Operation 3: 3 x — output three values for student \(x\): its current GPA, the number of students in its major, and the major's resentment value.

Note: The tree is given as follows. The first line contains two integers \(n\) and \(q\). The second line contains \(n\) integers representing the GPA of each student (1-indexed). The third line contains \(n-1\) integers: for \(i=2\) to \(n\), the \(i^{th}\) integer is the parent of student \(i\) (the tree is rooted at 1). Then follow \(q\) lines, each representing one operation in the format described above.

inputFormat

The input is given in the following format:

 n q
 gpa[1] gpa[2] ... gpa[n]
 p2 p3 ... pn
 [q lines of operations]

Each operation is one of the following:

• 1 x y — update GPA of student \(x\) to \(y\).
• 2 x y — update GPA of all students in the same major as \(x\) to \(y\).
• 3 x — query the GPA, the number of students in the major, and the resentment value for student \(x\).

outputFormat

For every operation of type 3, output three space-separated integers in one line: the GPA of student \(x\), the size of the major (number of students in the connected component), and the resentment value of the major (i.e. \(\max(depth)-\min(depth)+1\)).

sample

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

3 4 3
3 5 3
4 5 3