{"raw_statement":[{"iden":"problem statement","content":"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)  \nIn 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.  \n  \nYou have to process $Q$ queries for Atcoder:  \n\n*   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$.\n*   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.\n*   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$.\n\nProcess all queries!!!"},{"iden":"input format","content":"Let the $i$\\-th query $query_i$, the input format is following:  \n\n$N$ $Q$\n$p_0$ $a_0$\n$p_1$ $a_1$\n :   :\n$p_{N - 1}$ $a_{N - 1}$\n$query_0$\n$query_1$\n :   :\n$query_{Q - 1}$\n\nTHe format of $query_i$ is one of the three format:  \n\n1 $v_i$ $d_i$ $x_i$\n\n2 $v_i$ $d_i$\n\n3 $pr_i$ $ar_i$"},{"iden":"sample input 2","content":"7 9\n-1 1\n0 5\n0 7\n0 8\n1 3\n4 1\n5 1\n2 1 1\n2 1 2\n1 1 2 3\n1 4 1 1\n2 3 1\n2 0 2\n3 6 1\n3 7 11\n2 0 15"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}