Tree is defined as an undirected graph of N nodes and $N - 1$ edges that does not contain any cycles.

You are given two trees with N nodes rooted at 1. Each node has a colour associated with it, either white or black. You need to do perform Q operations of the following three kinds:

1. Given a node U in second tree, swap the colour of all nodes in $U's$ subtree.

2. You are given 3 integers $U, V$ and W where nodes U and V belong to the first tree, W belongs to the second tree and V lies in the subtree of U. Let the parent of W be P. You need to attach $W's$ subtree as a child of V and $U's$ subtree as child of P.

3. Given a node U in the second tree, find the number of white nodes in $U's$ subtree.

Input:

First line of input contains 2 space separated integers N and Q. Next line contains N space separated integers. If the $i^{th}$ integer is 1 then the $i^{th}$ node in first tree is coloured white, else black. Next line contains N space separated integers. If the $i^{th}$ integer is 1 then the $i^{th}$ node in second tree is coloured white, else black.

Each of the next $N-1$ lines contain two integers u and v denoting edges of the first tree. The next $N-1$ lines contain edges of the second tree in the same format.

Each of the next Q lines contain queries. The first integer denotes the type of query. If it is a type 1 or type 3 query, next integer denotes U (as defined in the problem statement). If it is a type 2 query, next three integers denote $U, V$ and W (as defined in the problem statement).

Output:

For each query of the third kind, print the number of white nodes in $U's$ subtree.

Constraints:

$2 \le N \le 2 \times 10^5$

$1 \le Q \le 2 \times 10^5$

$1 \le U, V \le N$

$2 \le W \le N$