Get the Salary of Atcoder

There are $N$ workers in Atcoder company. Each worker is numbered $0$ through $N - 1$, and the boss for worker $i$ is $p_i$ like a tree structure and the salary is currently $a_i$. ($p_i < i$, especially $p_0 = -1$ because worker $0$ is a president) In atcoder, the boss of boss of boss of ... (repeated $k$ times) worker $i$ called "$k$\-th upper boss", and "$k$\-th lower subordinate" called for vice versa. You have to process $Q$ queries for Atcoder: * Query 1: You are given $v_i, d_i, x_i$. Increase the salary of worker $v_i$, and all $j$\-th ($1 ≤ j ≤ d_i$) lower subordinates by $x_i$. * Query 2: You are given $v_i, d_i$. Calculate the sum of salary of worker $v_i$ and all $j$\-th ($1 ≤ j ≤ d_i$) lower subordinates. * Query 3: You are given $pr_i, ar_i$. Now Atcoder has a new worker $c$! ($c$ is the current number of workers) The boss is $pr_i$, and the first salary is $ar_i$. Process all queries!!! ## Input Format Let the $i$\-th query $query_i$, the input format is following: $N$ $Q$ $p_0$ $a_0$ $p_1$ $a_1$ : : $p_{N - 1}$ $a_{N - 1}$ $query_0$ $query_1$ : : $query_{Q - 1}$ THe format of $query_i$ is one of the three format: 1 $v_i$ $d_i$ $x_i$ 2 $v_i$ $d_i$ 3 $pr_i$ $ar_i$ [samples]