You are given a rooted tree of $N$ nodes. Each node $i$ contains a value $a_i$. Initially, all values of the node are $0$, your task is to process $Q$ queries of the following two types:

•  $0$ $v$ $x$ for every node $u$ in a subtree of $v$ if $a_u < Y$ add $x$ to $a_u$
•  $1$ $v$ print the value $a_u$

The tree is rooted at $1$.

Input format

Each test contains multiple test cases.

• The first line contains $t$ denoting the number of test cases. 
• The first line of each test case contains two integers $N$, $Q$, and $Y$. These integers describe the size of the tree, the number of the queries, and the integer described in the statement respectively.
• The $i^{th}$ of the next $n-1$ lines contains two integers $u_i$ and $v_i$ ($1 \leq u_i, v_i \leq n$, $u_i\neq v_i$) which means that there is an edge between nodes $u_i$ and $v_i$.
• Each of the next $Q$ lines contains a query of the following two types:
  • $0$ $v$ $x$
  • $1$ $v$

Note

• It is guaranteed that the given graph is a tree.
• It is guaranteed that the sum of $N+Q$ over all test cases doesn't exceed $6 \cdot 10^5$.

Output format

For each query of type $1 v$, print $a_v$.

Constraints

$(1 \leq t \leq 5 \cdot 10^5)$

$(1 \leq Q, N \leq 10^5 )$

$(0\leq Y \leq 100)$

$(1 \leq v \leq N)$

$(1 \leq x \leq 10^5)$