Maintaining a Colorful Tree

You are given a tree that initially contains one vertex numbered (1) with color (C). You need to process (q) operations. After each operation, determine two vertices (u) and (v) (with (1 \le u, v \le n)) having \textbf{different} colors so that the distance between them is maximized. The distance between two vertices (u) and (v) is defined as the length of the unique shortest path between them in the tree.

There are two types of operations:

1. (0\ x\ c\ d): Add a new vertex with index (n+1) (if there are currently (n) vertices) with color (c). Connect this vertex to the vertex (x) with an edge of length (d).

2. (1\ x\ c): Change the color of vertex (x) to (c).

After each operation, if there exists at least one pair of vertices with different colors, output the maximum distance among all such pairs. Otherwise, output (0).

inputFormat

The first line contains a single integer (q), the number of operations.\nEach of the next (q) lines represents an operation in one of the following formats:\ • (0\ x\ c\ d) \— add a new vertex with color (c) and an edge of length (d) from vertex (x) to it.\ • (1\ x\ c) \— change the color of vertex (x) to (c).\ \nNote: Initially, the tree contains one vertex numbered (1) with color (C).

outputFormat

After each operation, output a single line containing the maximum distance between any two vertices that have different colors in the current tree. If no such pair exists (for example, when there is only one vertex), output (0).

sample

3
0 1 A 3
0 2 B 4
1 1 B

0
7
7