Tanaka 最近解决了一个经典问题：给定一棵有 $N$ 个节点且边上带有权值的树，他求出了树上 $K$ 条路径的最大值或最小值。有趣的是，所有这些结果都是不同的！然而不幸的是，原始树上的权值丢失了。

给定 Tanaka 的结果以及原始树的结构，你能找到一种合理的边权分配方案吗？如果能，Groot 将会爱上这棵树，而你将获得 100 分。

输入格式

第一行包含一个整数 $N$。

接下来的 $N - 1$ 行，每行包含一对空格分隔的整数 $(x, y)$，其中 $1 \le x, y \le N$，表示树中存在一条连接节点 $x$ 和节点 $y$ 的边。树的节点编号从 $1$ 到 $N$。

下一行包含一个整数 $K$。

接下来的 $K$ 行包含 Tanaka 的查询结果描述，每行一个结果。如果结果表示从节点 $x$ 到节点 $y$ 的路径上的最大值为 $z$，则编码为 "M x y z"；如果表示最小值为 $z$，则编码为 "m x y z"。

保证给定的边构成一棵树，且所有的 $z$ 值各不相同。

输出格式

输出文件应包含 $N - 1$ 行，每行包含三个整数 $x, y, w$，表示在你的权值分配方案中，节点 $x$ 和节点 $y$ 之间存在一条权值为 $w$ 的边。这些边应与输入文件中的边相同，忽略顺序。此外，边内节点 $x$ 和 $y$ 的顺序无关紧要。这些权值应能导出上述结果。此外，$w$ 应能用有符号 32 位整数表示。

保证存在某种权值分配方案能导出上述结果。

数据范围

• $1 \le N \le 70.000$
• $1 \le K \le 70.000$
• $1 \le z \le 1.000.000.000$

子任务

子任务 1（7 分） $1 \le N \le 1.000$ $1 \le z \le 1.000$

子任务 2（22 分） * Tanaka 只求出了最大值

子任务 3（29 分） Tanaka 求出最大值的路径中，任意两条路径不相交。 同时，Tanaka 求出最小值的路径中，任意两条路径不相交。

子任务 4（42 分） * 无额外限制

样例

输入 1

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

输出 1

3 2 100
1 2 1
4 3 0