题目描述

翻译自 BalkanOI 2018 Day1 T3「Minmaxtree」

有一棵有 $N$ 个结点的无权树，结点分别编号为 $1\dots N$。现在要给每条边赋一个权值，使之变为一棵带权树。这棵带权树满足 $K$ 个条件，条件分为两类：

• M x y z：从结点 $x$ 到结点 $y$ 的链上最大的边权为 $z$；
• m x y z：从结点 $x$ 到结点 $y$ 的链上最小的边权为 $z$。

保证这 $K$ 组条件的 $z$ 互不相同。

请构造出这棵树，并输出每条边的边权。

输入格式
第一行有一个整数 $N$。
在接下来的 $N-1$ 行中，每行两个整数，表示一条边连接的两个结点。
第 $N+1$ 行有一个整数 $K$。
在接下来的 $K$ 行中，每行开头有一个字母，字母为 M 或 m，接下来有三个整数 $x, y, z$。

输出格式
输出 $N-1$ 行，每行三个整数 $x, y, v$，用空格分隔，表示带权树的一条带权边。

样例

输入

4
1 2
2 3
3 4
3
M 1 2 1
m 1 4 0
M 2 3 100

输出

3 2 100
1 2 1
4 3 0

数据范围与提示

• 子任务 #1（7 分）：$1 ≤ N, z ≤ 1000$；
• 子任务 #2（22 分）：只有条件 1，没有条件 2。
• 子任务 #3（29 分）：所有条件 1 中给出的 $x$ 到 $y$ 的链互不相交；所有条件 2 中给出的 $x$ 到 $y$ 的链也互不相交。
• 子任务 #4（42 分）：没有其他限制。

对于所有数据，$1 ≤ N, K ≤ 70000$，$1 ≤ z ≤ 10^9$。