Background

一个公司构架如下。

(1)每名员工只有一个直接主管(除了CEO没有主管)。

(2)一名员工可以有0名或多名直接下属(由他/她作为主管的员工)。

(3) 每名员工负责自己的部门。

(4)每名员工都是自己的一部分，所有的部门都是他们主管的一部分。（因此，CEO只是一个部门的一部分，所有的员工都是这个部门的一部分)。

当公司确定某个部门表现良好时，会向该部门所有员工发放奖金。奖金的计算方法是奖金金 额B乘以员工的奖金乘数m。所有员工都以相同的奖金乘数开始，但根据绩效，员工的奖金乘数可能会改变，从而潜在地改变员工未来奖金的金额。

创建一个程序， 跟踪支付给员工奖金的金额。问题:给定不同的查询类型，跟踪支付给不同员工的奖金金额。

查询将是以下4种类型之- - 。

(1)雇用新员工并指派他们的主管。

(2)更新员工的奖金乘数。

(3)给部门内的所有员工发奖金。

(4)检索(显示)支付给指定员工的总金额。

员工编号从1开始(CEO)，所有新员工按照他们被公司聘用的顺序，获得下一个整数员工编 号(id)。 最初，公司只有CEO， 即只有一名员工。

Input

第一行包含两个整数n和S ($1≤n≤10^5,0≤S≤10^6$)，分别代表所有员工(包括CEO好查询数量和起始关金乘数。接下来的n行用来描述查询，每一行都是以下4种格式中的种。 

(1)“1 i”的意思是:雇用了一名新员工，并且主管拥有员工idi，

(2)“2 i M” 意思是:使用idi的员工的奖金乘数为M ($1<M<10^6$).

(3)“3 i B”意思是:以奖金金额B ($0<B<10^6$)发放给以i为首的部门的所有员工奖金。请注意，员工的奖金是用奖金金额B乘以员工奖金乘数M计算出来的。 

(4)”4 i“表示一个查询要求向使用idi的员工支付到目前为止的奖金金额。.

Output

每行包含一个结果，输出所有（4）查询的结果。