You are given a rooted tree $T$ of $n$ nodes and a graph $G$ of $n$ nodes. Initially, the graph $G$ has no edges. There are two types of queries:

• $1\ x\ y\ w$: Add an edge of weight $w$ between nodes $x$ and $y$ in $G$
• $2\ v\ p$: Consider that the edge between $v$ and its parent in $T$ is deleted which decomposes $T$ into 2 connected components. You need to find the sum of weights of all edges like $x$ in $G$ such that:
  • The weight of $x$ is divisible by $p$
  • If an edge is added in $T$ between the same endpoints as $x$ then again we will get a tree (it will connect the two components). Note that the edge is deleted only for that particular query. 

Input:

• First line: Two integers $n, q (1 \le n \le 200\ 000,  1 \le q \le 300\ 000)$
• Second line: $n-1$ integers where $(i)th$ integer is the number of the parent of $(i + 1)th$ node. $1$ is the root of the tree.
• Next $q$ lines: Contains a description of queries. One query per line as described in the question $(1 \le w,p \le 1\ 000\ 000, 1 \le x, y \le n, 2 \le v \le n)$, $p$ is prime
• The graph $G$ may have self-loops and multiple edges.
• Queries are encrypted, hence you have to answer queries online. If $lastAns$ is the answer of the last query of type 2 (zero if not present), then you must decrypt queries as follows:
  • $1\ x'\ y'$ must be decrypted as $x = (x' + lastAns - 1) \mod n + 1, y = (y' + lastAns - 1) \mod n + 1$
  • $2\ v'$ must be decrypted as $v = (v' + lastAns - 1) \mod (n - 1) + 2$.

Output:
For each query of the second type, print the answer in a seperate line.