Problem H

There is a forest of colorful rooted trees containing n nodes. You are given m operations. Execute them one by one, and output the results.

1 x y c

Change x's father to y. If x=y or x is a ancestor of y, simply ignore it. The edge between x and its old father is removed, and the new edge should be painted with color c.

2 x y c

Paint all the edges along the path x-y with color c. If there is no path between x and y, simply ignore it.

3 x y

Count the number of edges along the path x-y, and the total number of colors among these edges.

Input

The input contains several test cases. The first line of each test case contains two integers n and m (1<=n<=50,000, 1<=m<=200,000). Nodes are numbered from 1 to n. The second line contains n integers F[i] (0<=F[i]<=n), the father of each node (F[i]=0 means the node is the root of a tree). The next line contains n integers C[i] (1<=C[i]<=30), the colors of the edges between each node and its father (for root nodes, the corresponding color should be ignored). Each of the next m lines contains an operation. For all operations, 1<=x,y<=n, for each type-2 operation, 1<=c<=30. The input is terminated by end-of-file (EOF). The size of input file does not exceed 5MB.

Output

For each type-3 operation, output two integers: the number of edges and the number of colors among these edges.

Sample Input

6 6
0 1 1 3 3 0
1 2 1 1 1 1
3 2 3
1 3 2 3
3 2 3
3 5 6
1 6 1 1
3 4 6

Output for the Sample Input

2 2
1 1
0 0
4 3