给定一棵包含 $n$ 个顶点的树。由于你觉得无事可做，你想在这棵树上玩一个游戏。

在游戏开始前，你需要为每个顶点 $u$ 分配一个标签 $\ell_u \in \{0, 1, 2, \dots, m - 1, m\}$。

游戏包含 $m + 1$ 个阶段，编号从 $0$ 到 $m$。在第 $i$ 个阶段，所有满足 $\ell_u \le i$ 的顶点 $u$ 将被涂成黑色。此时，如果对于每一对未涂色的顶点 $x$ 和 $y$，都存在一条从 $x$ 到 $y$ 且不经过任何黑色顶点的路径，则游戏继续。否则，你将输掉游戏，游戏立即结束。如果你能让游戏在所有阶段结束后继续，你就赢了。

你发现你赢得游戏的能力仅取决于你最初如何为树上的顶点分配标签。在接下来的 $q$ 天里，你想要重新标记顶点并玩游戏。在第 $i$ 天，你首先给顶点 $a_i$ 分配标签 $b_i$。然后，你想要计算有多少种方式为剩余的顶点分配标签，使得你能赢得游戏。由于数字可能很大，你只需要输出答案对 $998\,244\,353$ 取模的结果。

输入格式

第一行包含三个整数 $n, m$ 和 $q$ ($1 \le n, q \le 10^5, 1 \le m \le 30$)。

接下来的 $n - 1$ 行，每行包含两个整数 $x$ 和 $y$ ($1 \le x, y \le n, x \neq y$)，表示顶点 $x$ 和 $y$ 之间有一条边。保证给定的图是一棵树。

接下来的 $q$ 行，每行包含两个整数 $a_i$ 和 $b_i$ ($1 \le a_i \le n, 0 \le b_i \le m$)，表示一次查询。

输出格式

对于每次查询，输出一行，包含一个整数，表示答案对 $998\,244\,353$ 取模的结果。

样例

样例输入 1

3 2 5
1 2
3 2
3 1
1 0
2 0
2 1
2 2

样例输出 1

7
9
5
8
9

样例输入 2

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

样例输出 2

896
2820
2433
1218
2433
2272