#576. 【ULR #1】服务器调度

“跳找”计划布置 $n$ 个服务器，编号 $1\sim n$。

• 修改服务器 $u$ 的组别；

• 查询 $u$ 子树内所有服务器的延时总和。

输入格式

• 若 $opt_i = 1$，那么下面紧跟两个整数 $u_i, v_i$，表示将服务器 $u_i$ 的组别修改为 $v_i$；

• 若 $opt_i = 2$，后跟一个整数 $u_i$，表示查询 $u_i$ 子树内所有服务器的延时总和。

样例一

input

8 3 6
1 2 3 2 3 2 2 3
1 2 2 1 5 6 4
1 1 1 1 1 1 1
2 1
2 2
1 4 1
2 5
1 7 3
2 2



output

79
40
36
44



样例二

input

15 4 5
2 1 3 4 1 3 3 4 2 1 2 2 1 3 2
1 1 3 2 2 1 3 4 9 10 4 8 12 10
60 39 99 85 78 41 87 70 19 8 60 60 18 3
2 1
2 2
2 3
2 4
2 5



output

16657
3820
11041
8125
1396



样例三

input

15 4 10
4 2 4 3 2 1 4 1 1 1 2 2 3 3 3
1 1 3 3 4 2 7 8 7 6 11 9 11 6
41 43 67 66 77 76 85 90 76 39 20 56 88 100
1 12 1
2 1
1 7 1
2 1
1 1 1
2 1
1 13 2
2 1
1 4 2
2 1



output

23399
22389
22045
21816
21816



限制与约定

$1$ $200$ $10$
$2$ $2000$ $15$
$3$ $2\times 10^5$ 不存在修改操作 $15$
$4$ $10^5$ 询问操作中 $u_i=1$ $25$
$5$ $15$
$6$ $2\times 10^5$ $20$