Happy Painting!
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). The size of input file does not exceed 5 MB.
Output
For each type-3 operation, output two integers: the number of edges and the number of colors among these edges.