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. 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). Output For each type-3 operation, output two integers: the number of edges and the number of colors among these edges. Sample Input 66 011330 121111 323 1323 323 356 1611 346 Sample Output 22 11 00 43 1xyc 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. 2xyc Paint all the edges along the path x–y with color c. If there is no path between x and y, simply ignore it. 3xy Count the number of edges along the path x–y, and the total number of colors among these edges.