Query on a tree

Source: SPOJ

Version: Phuoc Hung OJ Extended

Problem

You are given an edge-weighted tree. Support changing the weight of one edge and querying the maximum edge weight on the path between two vertices. This PHOJ version contains exactly one tree per input; the command sequence ends with DONE.

Input

The first line contains $n$. The next $n-1$ lines contain u v w; the $i$-th such line describes edge $i$. Then follow commands:

• CHANGE i x: set the weight of edge $i$ to $x$.
• QUERY a b: query the maximum edge weight on the path from $a$ to $b$.
• DONE: end the command sequence.

Output

For each QUERY, print the maximum edge weight on the requested path. If $a=b$, the path contains no edge and the answer is 0.

Subtasks

Subtask 1 (20%)

• The tree size and number of operations are at most 20.
• All other conditions are the same as Subtask 3.

Subtask 2 (30%)

• The tree size and number of operations are at most 2000.
• All other conditions are the same as Subtask 3.

Subtask 3 (50%)

• $1\le n\le10000$.
• Edge weights are at most $10^6$.
• The PHOJ version uses one test case.

Example

Input

1
QUERY 1 1
QUERY 1 1
QUERY 1 1
QUERY 1 1
QUERY 1 1
QUERY 1 1
QUERY 1 1
QUERY 1 1
QUERY 1 1
QUERY 1 1
QUERY 1 1
QUERY 1 1
QUERY 1 1
QUERY 1 1
DONE

Output

0
0
0
0
0
0
0
0
0
0
0
0
0
0

Explanation

The tree has one vertex and no edge, so every path from vertex 1 to itself has maximum edge weight 0.