$N$개의 정점으로 이루어진 트리가 있다. 정점은 1번부터 $N$번까지 번호가 매겨져 있고, $i$번 정점에는 정수 $A_i$가 저장되어 있다. 처음 상태에서 $A_i=0$이다. ($1 \le i \le N$)

당신은 다음과 같은 쿼리를 총 $Q$번 수행해야 한다.

• 1 u v: 트리의 루트를 정점 $u$라 하였을 때, 정점 $v$를 루트로 하는 서브트리의 모든 정점 $i$의 $A_i$에 1을 더한다.
• 2 u v: 정점 $u$에서 정점 $v$로 가는 유일한 경로에 있는 모든 정점 $i$의 $A_i$에 1을 더한다.
• 3 v: $\sum_{i = 1}^{N} A_i \times dist(v, i)$를 출력한다. $dist(x, y)$는 정점 $x$에서 정점 $y$로 가는 경로에 있는 간선의 수를 의미한다.

입력

첫째 줄에 $N$이 주어진다. ($1 \le N \le 200{,}000$)

다음 $N-1$개 줄에 트리의 간선이 주어진다. 각 줄에는 공백으로 구분된 두 수 $u$와 $v$가 주어지고, $u$와 $v$를 연결하는 간선이 있다는 것을 의미한다. ($1 \le u, v \le N$)

다음 줄에는 쿼리의 개수 $Q$가 주어진다. ($1 \le Q \le 200{,}000$)

다음 $Q$개의 줄에는 한 줄에 하나씩 다음과 같은 형식 중 하나로 쿼리가 주어진다.

• 1 u v ($1 \le u, v \le N$)
• 2 u v ($1 \le u, v \le N$)
• 3 v ($1 \le v \le N$)

3번 쿼리는 한 번 이상 주어진다.

출력

각각의 3번 쿼리의 결과를 순서대로 한 줄에 하나씩 출력한다.

Sample

Input

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

Output

1
5