Bajtazar 在一家物流公司工作，负责将建筑材料从 Bajtocja 首都的仓库运送到周边城市的商店。Bajtocja 有 $n$ 个城市（编号为 $1$ 到 $n$），由 $n-1$ 条道路连接成一个连通的网络。每条道路的中间都设有一个加油站。

Bajtazar 的工作日总是这样开始的：他从首都（城市 $1$）出发，沿着最短路径前往某个城市 $x$，然后再沿原路返回。

Bajtazar 的儿子 Bitek 是“Biciaki 帮”的粉丝——这是一种在加油站出售的毛绒玩具。总共有 $m$ 种 Biciaki（为了简化起见，我们用 $1$ 到 $m$ 的数字对它们进行编号）。每个加油站只提供一种 Biciaki，因此为了收集所有的 Biciaki，需要多跑一些地方。

每天早上，Bajtazar 都会思考他当天能买到多少种不同的 Biciaki。由于加油站的库存会发生变化，这个问题变得复杂起来。请帮助 Bajtazar 编写一个程序来解决他的困扰。

输入格式

输入的第一行包含三个整数 $n, m$ 和 $z$ ($2 \le n \le 100\,000, 1 \le m, z \le 150\,000$)，分别表示 Bajtocja 的城市数量、Biciaki 的种类数和查询次数。

接下来的 $n-1$ 行描述了道路网络：每行包含三个整数 $a, b$ 和 $c$ ($1 \le a, b \le n, 1 \le c \le m$)，表示连接城市 $a$ 和城市 $b$ 的道路，该道路上的加油站提供种类为 $c$ 的 Biciaki。

接下来的 $z$ 行包含查询。每行以一个字符开头，后跟一个或两个整数：

• Z x 表示 Bajtazar 询问如果他前往城市 $x$ ($2 \le x \le n$)，他可以买到多少种不同的 Biciaki；
• B i c 表示位于第 $i$ 条道路上的加油站（$1 \le i < n$；道路顺序与输入顺序一致）现在开始出售种类为 $c$ 的 Biciaki ($1 \le c \le m$)。注意，执行此操作时，该加油站可能已经在出售种类为 $c$ 的 Biciaki（此时该操作不改变任何东西）。

输入中至少会出现一个 Z 类型的查询。

输出格式

你的程序应输出与输入中 Z 类型查询数量相同的行数。对于每个查询，输出一个整数，即 Bajtazar 问题的答案。

样例

样例输入 1

6 3 5
1 2 3
1 3 2
3 4 3
5 3 1
6 4 2
Z 5
Z 6
B 2 1
Z 5
Z 6

样例输出 1

2
2
1
3

说明

样例说明：前往城市 6 的路径经过城市 1 - 3 - 4 - 6。起初，路径上可以买到种类为 2, 3 和 2 的 Biciaki（总共 2 种）。在改变了道路 1 - 3 上加油站的库存后，路径上可以买到种类为 1, 3 和 2 的 Biciaki（总共 3 种）。

子任务

测试集分为以下子任务。每个子任务的测试由一组或多组独立的测试用例组成。