题目背景

翻译自 ROI 2023 D2T1。

在爬上富士山的山顶后，蜗牛想要下山。在山坡上有一个类似二叉树的小径。

该树包含 $n$ 个被 $n-1$ 个小径连接的节点。树的根位于山顶。一些节点处的小径到头了，它们是树的叶子节点。除了叶子节点外，每个节点向下山坡延伸两条小径，其中一条向左，另一条向右。

蜗牛希望从根部开始沿着树向下爬并到达其中一个叶子节点。在路径上，蜗牛可以选择两个方向之一进行进一步下降：向左或向右。

刚开始在山顶，蜗牛可以往任意方向（左或右）开始下降。在每个后续节点中，如果它选择与前一个节点选择的方向不同的方向，则它要进行转弯。

由于蜗牛转弯不太方便，所以在从根到叶子的整个路径上，蜗牛最多只准备转弯 $k$ 次。

题目描述

将树的节点从 $1$ 到 $n$ 编号，其中根节点编号为 $1$。给定 $q$ 个查询。每个查询给出一个节点 $u_i$，要求找出蜗牛在从根开始下降时，最多转弯 $k$ 次，且通过节点 $u_i$ 的路径上能到达的叶子节点数量。

输入格式

第一行给出三个整数 $n,k,q$，分别表示树中节点的数量、蜗牛准备转动的最大次数，以及查询的数量。

接下来的 $n$ 行描述了树的结构。第 $i$ 行的第一个整数 $t_i$ 表示节点 $i$ 的小径（子树）数量（$t_i = 0$ 或 $2$）。如果 $t_i = 2$，则在同一行中给出两个整数 $l_i$ 和 $r_i$，分别表示从节点 $i$ 出发的左侧和右侧小径连接到的节点编号（$1 \le l_i,r_i \le n$）。保证输入符合要求。

接下来的 $q$ 行给出了查询。第 $i$ 行给出一个整数 $u_i$，表示蜗牛路径经过的节点编号（$1 \le u_i \le n$）。

输出格式

对于每一次询问，输出一行一个整数表示答案。

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

3
2
1
0

提示

样例的树长这样。

第一次询问（灰色为可到达的叶子节点，虚线为不可到达的节点）：

第二次询问：

第三次询问：

第四次询问（因为最多转一次弯，所以并没有合法的路线，故输出 $0$）：

对于 $100\%$ 的数据，$3 \le n \le 200000$，$0 \le k \le n$，$1 \le q \le 200000$。