Country A is beautiful and consists of $n$ cities, each with its own unique character, forming a diverse and magnificent landscape. Unfortunately, due to the financial crisis, Country A is under fiscal strain, so there are only $n - 1$ bidirectional roads connecting these $n$ cities. To ensure convenience and efficiency, these $n - 1$ roads guarantee that it is always possible to travel from any city to any other city.

The city system of Country A is well-organized: city 1 is the capital, and every other city has a superior city. Specifically, for the $i$-th city, there is a road to its superior city $f_{ai}$ ($1 \le f_{ai} < i$) with a length of $w_i$. We say a city $y$ is an indirect subordinate of city $x$ if and only if the superior city of $y$, $f_{ay}$, is $x$, or $f_{ay}$ is an indirect subordinate of $x$. Let $dist(x, y)$ denote the shortest path length from city $x$ to city $y$.

Due to the rugged terrain and frequent natural disasters in Country A, the central command needs precise coordination and must balance the total workload of the fire safety forces in each city. Let $a_i$ be the workload of the fire safety force in city $i$. When the fire safety force of city $i$ travels to city $x$ to perform a task, the workload increases by $dist(i, x)$ due to the difficult terrain, i.e., $a_i \leftarrow a_i + dist(i, x)$. The initial workload of each city is 0.

The central command has issued a total of $q$ instructions:

• $1 \ x \ y$: Perform a task: A disaster has occurred in city $y$. Order the fire safety forces of city $x$ and all its indirect subordinates to travel to city $y$ for front-line support, each performing one task to city $y$.
• $2 \ x$: Query workload: Query the sum of the workloads of the fire safety forces of city $x$ and all its indirect subordinates.

Input

The first line contains two integers $n, q$ ($1 \le n, q \le 5 \times 10^5$), representing the number of cities and the number of instructions, respectively.

The next $n - 1$ lines each contain two integers $f_{ai+1}, w_{i+1}$ ($1 \le f_{ai+1} < i + 1, 1 \le w_{i+1} \le 100$), where the two integers in the $i$-th line represent the superior city and the path length for city $i + 1$.

The next $q$ lines each follow one of these formats:

• $1 \ x \ y$ ($1 \le x, y \le n$): Represents a type 1 instruction: perform a task.
• $2 \ x$ ($1 \le x \le n$): Represents a type 2 instruction: query workload.

Output

For each type 2 instruction, output a single integer on a new line representing the total workload.

Examples

Input 1

5 4
1 3
1 2
2 1
2 2
1 5 1
2 1
1 2 3
2 2

Output 1

5
23