$N$개의 정점으로 이루어진 트리가 있다. 정점은 1부터 $N$까지의 정수로 번호가 매겨져 있으며, $i$번째 정점은 변수 $A_i$를 가지고 있다. 처음에 $A_i = 0$이다 ($1 \le i \le N$).

다음과 같은 $Q$개의 쿼리를 처리해야 한다.

• “1 $u$ $v$”: 트리의 루트를 $u$로 설정하고, 정점 $v$의 서브트리를 고려하여, $v$의 서브트리에 속한 모든 정점 $i$에 대해 $A_i$를 1씩 증가시킨다.
• “2 $u$ $v$”: $u$에서 $v$까지의 유일한 단순 경로에 있는 모든 정점 $i$에 대해 $A_i$를 1씩 증가시킨다.
• “3 $v$”: $\sum_{i=1}^{N} \text{dist}(v, i) \cdot A_i$를 출력한다. 여기서 $\text{dist}(x, y)$는 정점 $x$에서 정점 $y$까지의 경로에 있는 간선의 개수이다.

입력

첫 번째 줄에는 정점의 개수 $N$이 주어진다 ($1 \le N \le 2 \cdot 10^5$).

다음 $N - 1$개의 줄에는 트리에 대한 정보가 주어진다. 각 줄은 공백으로 구분된 두 정수 $u$와 $v$를 포함하며, 이는 $u$와 $v$를 잇는 간선이 있음을 의미한다 ($1 \le u, v \le N$). 주어진 그래프는 트리임이 보장된다.

다음 줄에는 쿼리의 개수 $Q$가 주어진다 ($1 \le Q \le 2 \cdot 10^5$).

다음 $Q$개의 줄에는 쿼리가 한 줄에 하나씩 주어진다. 각 쿼리는 위에서 설명한 형식 중 하나로 주어진다 ($1 \le u, v \le N$). “3”번 유형의 쿼리가 적어도 하나 존재한다고 가정해도 좋다.

출력

“3”번 유형의 각 쿼리에 대해, 결과를 한 줄에 하나씩 출력한다.

예제

입력 1

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

출력 1

1
5