Description

Given a tree with $n$ nodes and $q$ operations, there are two kinds of operations.

$1$ $a$ $b$ : for a chain $<a, b>$, increase the value of $x^2$ to the x-th point on this chain for example the chain from a to b=($x1,x2,x3,x4,x5$),after the operation,$x1+=1,x2+=4,x3+=9,x4+=16,x5+=25$

$2$ $x$ :asks the value of x-th node

Format

Input

There is only one test case for this question.

The first line contains one integer $n(1≤n≤10^5)$ .

The next $n−1$ line contains two integers u,v,which means that there is an edge between $u$ and $v$.

The next line contains one integer $q(1≤q≤10^5)$ .

The i-th of the following $q$ lines is in one of the $2$ formats:

$1$ $a$ $b$ $(1 \leqslant a,b \leqslant n)$

$2$ $x$ $(1 \leqslant x \leqslant n)$

Output

Each line output one integer represents the answer.

Samples

3
1 2
2 3
5
1 1 2
2 1
1 2 1
2 2
2 3

1
5
0