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.
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.
For each type-3 operation, output two integers: the number of edges and the number of colors among these edges.
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
2 2 1 1 0 0 4 3