Having quietly climbed to the top of Mount Fuji, a snail wants to descend. On the mountain slope, there is a system of paths forming a rooted binary tree.

The tree contains $n$ vertices connected by $n - 1$ paths. The root of the tree is at the top of the mountain. In some vertices, the path ends; these are the leaves of the tree. From each vertex, except for the leaves, exactly two paths lead down the slope: one leads to the left, and the other to the right.

The snail wants to start at the root, descend through the tree, and reach one of the leaves. It will descend by moving down the paths. At each vertex along the way, the snail can choose one of two directions for further descent: left or right.

The snail can start its descent at the root in either of the two directions. In each subsequent vertex, the snail makes a turn if it chooses a direction different from the one chosen at the previous vertex.

The snail finds it uncomfortable to turn, so on the entire path from the root to a leaf, the snail is willing to make no more than $k$ turns.

Let us number the vertices of the tree from $1$ to $n$, with the root receiving the number $1$. You are given $q$ queries. Each query is described by a single vertex $u_i$. You need to find the number of leaves at which the snail can finish its descent if it starts from the root, makes no more than $k$ turns, and passes through vertex $u_i$ on its way.

Input

The first line contains three integers $n$, $k$, and $q$ — the number of vertices in the tree, the maximum number of turns the snail is willing to make, and the number of queries ($3 \le n \le 200\,000$; $0 \le k \le n$; $1 \le q \le 200\,000$).

The next $n$ lines contain the description of the tree. The first integer in the $i$-th line is $t_i$ — the number of paths leading out of the $i$-th vertex ($t_i = 0$ or $t_i = 2$). If $t_i = 2$, then the same line contains two integers $l_i$ and $r_i$ — the numbers of the vertices to which the left and right paths from vertex $i$ lead, respectively ($1 \le l_i, r_i \le n$). It is guaranteed that this description corresponds to a rooted binary tree with the root at vertex $1$.

The next $q$ lines contain the queries. The $i$-th line contains a single integer $u_i$ — the number of the vertex through which the snail must pass on its path ($1 \le u_i \le n$).

Output

For each query, output the answer on a new line — the number of leaves at which the snail can finish its route if it starts at the root, descends, makes no more than $k$ turns on its path, and passes through vertex $u_i$.

Subtasks

Note: In subtasks 1 and 5, the constraint "In all queries $u_i$ is a leaf" is specified.

Examples

Input 1

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

Output 1

3
2
1
0