News

Deni is the boss of a company with $N$ workers, numbered from $1$ to $N$. The company structure is strictly hierarchical: every worker except number $1$ has exactly one direct supervisor. So every worker has at least one subordinate (direct or indirect), including himself. For example, worker $1$ has exactly $N$ subordinates, including himself. Of course, there is no situation where some subordinate of a worker is his direct supervisor. For some worker $x$, call $x$ a $0$-level subordinate. Then his direct subordinates are called $1$-level subordinates of $x$. All of their direct subordinates (which are indirect subordinates of $x$) are called $2$-level subordinates of $x$, and so on.

Some of the workers know a breaking piece of news. Deni wants to inform all the company employees. So, multiple times she chooses worker $x$ and number $k$, and tells the news to all $0$-level, $1$-level (if they exist), ..., $k$-level (if they exist) subordinates of $x$. Call all these subordinates the $k$-subordinates of $x$. The problem with this type of announcement is that most of the time, many chosen subordinates already know the piece of news. That is why Deni wants a system that can tell her the number of workers among all the $k$-subordinates of $x$ that have already learned about the news. Write a program that can help her.

From the first line of the standard input read one integer $N$, the number of workers in Deni's company. From each of the next $N-1$ lines read two integers $x$ and $y$, which show that worker $y$ is a direct subordinate of worker $x$. From the next line read $N$ integers $b_1, b_2, \ldots, b_N$, where $b_i$ is $1$ if worker $i$ knows the news at the beginning and $0$ otherwise. From the next line read one integer $Q$, the number of queries. From each of the last $Q$ lines, read queries of two types:

• type $1$ (news announcement query): $1$ $x$ $k$ – Deni tells the news to all the $k$-subordinates of $x$.
• type $2$ (question query): $2$ $x$ $k$ – Deni asks for the number of workers that know the news among the $k$-subordinates of $x$.

For every query of type $2$, on separate lines in the same order as in the input, write one integer: the answer to the corresponding question.

• $2 ≤ N ≤ 2 × 10^5$
• $1 ≤ Q ≤ 2 × 10^5$
• $0 ≤ k ≤ N$

The picture above shows the hierarchy of the company, and the workers that know the news at the beginning are colored orange.

For the first query $2$ $4$ $4$:

The $0$-level subordinate of worker $4$ is $4$, the $1$-level subordinates of worker $4$ are workers $7$ and $8$, the $2$-level subordinates of worker $4$ are $9$ and $10$, and there are no $3$-level or $4$-level subordinates of worker $4$. Workers $4$, $8$, and $10$ know the news, so the answer to this question query is $3$.

For query $1$ $4$ $1$:

The $1$-subordinates of worker $4$ are workers $4$, $7$, and $8$. Workers $4$ and $8$ already know the news, so only worker $7$ learns the news at this time.

For the second query $2$ $4$ $4$:

The $4$-subordinates of worker $4$ are $4$, $7$, $8$, $9$, and $10$. Workers $4$, $7$, $8$, and $10$ know the news, so the answer to this query is $4$.