Background

Translated from ROI 2023 D2T1.

After climbing to the top of Mount Fuji, the snail wants to go down. On the slope there is a trail system that looks like a binary tree.

The tree contains $n$ nodes connected by $n-1$ trails. The root of the tree is at the summit. For some nodes, the trails end there; these nodes are the leaves of the tree. Every non-leaf node has two trails going downhill: one to the left and one to the right.

The snail wants to start at the root and go down along the tree to reach one of the leaves. Along the way, at each node it can choose one of the two directions to continue descending: left or right.

At the beginning, at the summit, the snail may start descending in either direction (left or right). At each subsequent node, if it chooses a direction different from the direction chosen at the previous node, then it makes a turn.

Since turning is inconvenient for the snail, on the whole path from the root to a leaf, the snail is willing to make at most $k$ turns.

Problem Description

The nodes of the tree are numbered from $1$ to $n$, and the root has number $1$. You are given $q$ queries. Each query gives a node $u_i$. You need to find the number of leaf nodes that the snail can reach on a path that starts from the root, passes through node $u_i$, and makes at most $k$ turns while descending.

Input Format

The first line contains three integers $n, k, q$, representing the number of nodes in the tree, the maximum number of turns the snail is willing to make, and the number of queries.

The next $n$ lines describe the structure of the tree. On line $i$, the first integer $t_i$ denotes the number of trails (children) of node $i$ ($t_i = 0$ or $2$). If $t_i = 2$, then the same line contains two integers $l_i$ and $r_i$, denoting the node numbers connected by the left and right trails starting from node $i$ ( $1 \le l_i, r_i \le n$ ). It is guaranteed that the input satisfies the requirements.

The next $q$ lines contain the queries. Line $i$ contains one integer $u_i$, meaning the node that the snail's path must pass through ( $1 \le u_i \le n$ ).

Output Format

For each query, output one integer per line, the answer to that query.

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

3
2
1
0

Hint

The sample tree looks like this.

The first query (gray nodes are reachable leaves, dashed lines are unreachable nodes):

The second query:

The third query:

The fourth query (since at most one turn is allowed, there is no valid route, so the output is $0$):

For $100\%$ of the testdata, $3 \le n \le 200000$, $0 \le k \le n$, $1 \le q \le 200000$.

Translated by ChatGPT 5