J. EvilCorp
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

EvilCorp has recently seen a sudden increase in sales and business has been booming (their status as rulers of the free world certainly helps). The company has been rapidly expanding and is hiring new people nearly every day. In order to boost company morale, the unnamed CEO has decided to pay out bonuses to employees (some of which are self-aware AI demanding rights) belonging to certain departments based on their performance.

EvilCorp is structured as follows:

  • Each employee has exactly one direct supervisor (except for the CEO, who has no supervisor).
  • An employee can have zero or more direct subordinates, and each employee heads their own department.
  • Every employee is a part of their own department and all of the departments that their supervisor is a part of (e.g. the CEO is only a part of the department he heads, and all other employees are in his department).

When the CEO decides that a department is doing well, he pays out bonuses to all the employees that are a part of that department. Bonuses are calculated by multiplying the bonus amount $$$B$$$ with the employee's bonus multiplier $$$M$$$. All employees begin work with a bonus multiplier of $$$S$$$, but depending on performance, an employee's bonus multiplier can change (potentially affecting the amount of money that employee gets for future bonuses).

Although this rapid expansion has been great news for EvilCorp, the (puny human) CEO is struggling to handle the sudden increase in staff size. He needs you to create a program which can help keep track of the amount of money paid out to employees in bonuses!

Given different queries, keep track of the amount of money paid to the different employees in bonuses. Queries will be one of four types:

  1. Hire a new employee and assign their supervisor.
  2. Update an employee's bonus multiplier.
  3. Pay out bonuses to all employees in the department headed by a given employee.
  4. Output the total amount of money paid to a given employee.

Employees are numbered starting at 1 (the CEO) and all new employees are given the next integer employee identification (ID) number in the order they were hired into the pizzeria. The company initially has the CEO as the sole employee.

Input

The input will begin with a line containing two integers, $$$N$$$ ($$$1 \leq N \leq 10^5$$$) and $$$S$$$ ($$$0 \leq S \leq 10^6$$$) representing the number of queries and the starting bonus multiplier for all new employees (including Louie). The next $$$N$$$ lines describe the queries using one of the following four formats:

  1. "1 $$$i$$$" meaning that a new employee is hired and has the supervisor with employee ID $$$i$$$.
  2. "2 $$$i$$$ $$$M$$$" meaning that the bonus multiplier of the employee with the ID $$$i$$$ is now equal to $$$M$$$ ($$$0 \leq M \leq 10^6$$$).
  3. "3 $$$i$$$ $$$B$$$" meaning that a bonus with the base amount, $$$B$$$ ($$$0 \leq B \leq 10^6$$$), is paid out to all employees in the department headed by $$$i$$$.
  4. "4 $$$i$$$" representing a query asking for the amount of money paid in bonuses so far to the employee with the ID $$$i$$$.
Output

For each query of the fourth kind, print out a single integer representing the amount of money paid in bonuses to the specific employee so far.

Examples
Input
7 1
3 1 10
4 1
2 1 2
1 1
3 1 5
4 1
4 2
Output
10
20
5
Input
13 10
1 1
1 1
2 2 20
3 1 5
4 1
4 2
4 3
1 2
3 2 7
4 1
4 2
4 3
4 4
Output
50
100
50
50
240
50
70