在 RUN 国，有 $n$ 个城市，编号为 $1$ 到 $n$。某些城市对之间由一条双向道路相连。总共存在 $n-1$ 条道路，且任意两个城市之间都存在唯一的一条路径。

$1$ 号城市是首都。最初，所有道路都没有颜色。RUN 国的国王 Alex 要求你执行以下操作 $Q$ 次：

• u c m：给定一个城市 $u$、一种颜色 $c$ 和一个整数 $m$，将从 $u$ 到首都的唯一路径上的所有道路染成颜色 $c$。即使某条道路已经有了颜色，也将其颜色更改为 $c$。染色完成后，计算有多少种颜色，满足恰好有 $m$ 条道路染上了该颜色。

给出总共 $Q$ 次操作，计算每次操作后第二部分的答案。

输入格式

第一行包含三个整数 $n, C, Q$ ($1 \le n, C, Q \le 2 \times 10^5$)，用单个空格分隔，分别表示 RUN 国的城市数量、可能颜色的数量以及操作的数量。

接下来的 $n - 1$ 行，每行包含两个整数 $u, v$ ($1 \le u, v \le n$)，表示有一条双向道路直接连接编号为 $u$ 和 $v$ 的城市。

接下来的 $Q$ 行，每行包含一个操作，其中包含 3 个整数 $u, c, m$，如题目描述中所述。($1 \le u \le n, 1 \le c \le C, 0 \le m \le n - 1$)

输出格式

输出 $Q$ 行，每行对应一次操作。每行必须包含一个整数，即对应操作的答案。

样例

样例输入 1

6 5 5
1 3
2 3
1 4
6 3
5 2
5 1 3
6 2 2
2 3 1
4 4 1
1 5 0

样例输出 1

1
2
2
3
1

说明

对于最后一次操作，答案为 1，因为颜色 5 被用于 0 条道路。