背景

中和星和温热星是两颗星星
来自这两颗星星的人都喜欢玩森林冰火人

描述

给出一棵N个点的树，边有长度l和属性，初始时边属性为无
初始时冰人与火人都在1号点上
接下来M个操作，为将冰人或火人移至节点to，对每个操作回答移过去经过边长度和的最小值
冰人经过一条边后，这条边的属性变为冰，火人类似
冰属性的边对于冰人长度为原长度l减去一个常数K，而对于火人为加K，火边类似

输入

第一行有三个整数N,M,K
接下来N-1行每行三个整数u,v,l表示树上有一条连接u,v，长度为l的双向边
接下来M行每行两个整数t,to表示将冰人(t=-1)或火人(t=1)移至节点to

输出

M行，为每个操作经过路径长度

样例

输入

3 10 1
2 1 4
3 1 5
1 3
1 2
1 3
-1 2
-1 3
-1 1
1 2
1 2
-1 1
-1 3

输出

5
8
7
5
9
4
11
0
0
6

范围

30% N,M<=9 l<=20
40% N,M<=1000
60% N,M<=3000 l<=200
90% N,M<=\(10^5\)
100% 1<=N<=7*\(10^5\) 1<=M<=5*\(10^5\) K+1<=l<=1000
有50% K=0
另50% 1<=K<=10

限制

4000ms
128M