트리와 색깔과 쿼리

$N$개의 정점으로 구성된 트리가 주어진다. 각 정점에는 $1$번부터 $N$번까지 번호가 붙어 있고, $1$번 정점은 트리의 루트이다. 추가로 각 정점은 색깔 $A\_i$를 가지고 있다. 정점의 색깔은 $1$ 이상 $50\ 000$ 이하의 정수로 나타내어진다.

다음 세 가지 쿼리를 수행하는 프로그램을 작성하시오. $P = P\_0, P\_1, \cdots, P\_N$는 $0$부터 $N$까지의 정수가 한 번씩 등장하는 순열이며, 입력에서 주어진다.

• 1 $x$: 정점 $x$를 루트로 하는 서브트리에 색깔이 $i$인 정점의 수를 $C\_i$라고 할 때 $\sum i \cdot P\_{C\_i}$를 출력한다.
• 2 $x$ $y$: 두 정점 $x$와 $y$를 잇는 경로에 색깔이 $i$인 정점의 수를 $C\_i$라고 할 때 $\sum i \cdot P\_{C\_i}$를 출력한다.
• 3 $x$ $z$: 정점 $x$의 색깔을 $z$로 바꾼다.

첫 번째 줄에 정수 $N$, $Q$가 공백으로 구분되어 주어진다. $(2\le N, Q\le 50\ 000)$  

두 번째 줄에 $N$개의 정수 $A\_1, A\_2, \cdots, A\_N$이 공백으로 구분되어 주어진다. $(1\le A\_i\le 50\ 000)$  

세 번째 줄에 $N$개의 정수 $P\_1, P\_2, \cdots, P\_N$이 공백으로 구분되어 주어진다. $P\_0 = 0$이며, $P$는 순열이다.

네 번째 줄부터 $N-1$개의 줄에 걸쳐 트리에서 $i$번째 간선이 연결하는 두 정점 번호 $u\_i, v\_i$가 공백으로 구분되어 주어진다. $(1\le u\_i,v\_i\le N)$

이어서 $Q$개의 줄에 각 쿼리가 다음 형식 중 하나로 주어진다. $(1\le x, y\le N;$ $1\le z\le 50\ 000;$ $x, y, z$는 정수$)$

• 1 $x$
• 2 $x$ $y$
• 3 $x$ $z$

$1$번과 $2$번 쿼리의 결과를 한 줄에 하나씩 출력한다. $1$번 혹은 $2$번 쿼리가 $1$개 이상 주어짐이 보장된다.