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\)