자료 구조

Andy는 난징대학교에서 그를 따를 자가 없는 유명한 자료 구조 전문가이다. 어느 날 그는 평범하고 지루한 자료 구조 문제를 친구들에게 냈지만, 아무도 풀지 못했다. 당신은 어떤가?

루트가 1번인 트리가 주어진다. 각 노드의 가중치는 처음에 0이다. 두 노드 사이의 거리는 두 노드를 잇는 유일한 단순 경로의 간선 수이다. 다음 두 종류의 연산을 수행해야 한다.

• 1번 연산: $a, x, y, z$가 주어지면, $a$의 자손 중 자기 자신을 포함하여 $a$와의 거리를 $x$로 나눈 나머지가 $y$인 노드들의 가중치에 $z$를 더한다.
• 2번 연산: $a$가 주어지면 노드 $a$의 가중치를 구한다.

첫 줄에는 테스트 케이스의 수 $T$ $(1 \leq T \leq 4)$가 하나의 정수로 주어진다.

각 테스트 케이스는 트리의 노드 수 $n$과 연산의 수 $m$ $(1 \leq n, m \leq 300000)$을 나타내는 두 정수로 시작한다. 노드는 1번부터 $n$번까지 번호가 매겨져 있다. 다음 줄에는 $n-1$개의 정수 $f_1, f_2, \cdots, f_{n-1}$ $(1 \leq f_i \leq i)$가 주어지며, $i$번째 정수는 노드 $i+1$의 부모이다. 이후 $m$개의 줄에 연산이 주어진다. 각 줄은 1번 연산 1 a x y z $(1 \leq a \leq n, 1 \leq x \leq n, 0 \leq y < x, 0 \leq z \leq 500)$ 또는 2번 연산 2 a $(1 \leq a \leq n)$이다.

각 테스트 케이스에서 2번 연산마다 답을 한 줄에 출력한다.