Andy is a famous data structure expert at Nanjing University second to none. One day he throws a plain dry data structure problem to his friends, but none of them can solve. How about you?
Given a tree rooted at node 1. Each node has a weight which is 0 initially. Define the distance between two nodes as the number of edges in the unique simple path between the two nodes. You need to perform these two types of operations:
- Type 1: given a,x,y,za,x,y,z, add zz to the weights of all aa's descendants (including aa itself) whose distances to aa are yy modulo xx; - Type 2: given aa, return the weight of node aa.
Input
The first line of the input is a single integer TT(1≤T≤4)(1≤T≤4), the number of test cases.
Each test cases starts with two integers n,mn,m(1≤n,m≤300000)(1≤n,m≤300000), denoting that there are nn nodes (numbered 11 through nn) in the tree and you need to perform mm operations. The next line contains n−1n−1integers, f1,f2,⋯,fn−1f1,f2,⋯,fn−1(1≤fi≤i)(1≤fi≤i), specifying the edges of the trees; the iith integer denotes the parent of node i+1i+1. The next mmlines describe the operations. Each line is either 1 a x y z1 a x y z(1≤a≤n,1≤x≤n,0≤y<x,0≤z≤500)(1≤a≤n,1≤x≤n,0≤y<x,0≤z≤500), denoting an operation of type 1, or 2 a2 a(1≤a≤n)(1≤a≤n), denoting an operation of type 2.
Output
For each operation of type 2 in each test case, print the answer in one line.