Description

失昼城共由 $N$ 座岛屿组成，由 $N-1$ 条传递信息的空间通道联通。

作为失昼城的守星使，月凌霜具有部署守星塔的能力，具体而言，为了依靠特殊空间波动向每个有居民居住的岛屿传递消息，月凌霜可以任意数量地部署守星塔，每座岛屿只能部署一座守星塔，但是同一时刻所有部署的守星塔必须依靠空间通道连成一条链。

失昼城常年受到空间风暴的困扰，常常会出现某座岛屿遭受空间风暴，岛上全体居民被迫离开岛屿，此时，守星塔不再需要向该地传输消息，等到空间风暴散去，居民重新回到这里，守星塔才需要恢复向该地的信息传输。

由于空间波动的干扰，守星塔传递消息必须依靠联通岛屿的空间通道完成，具体而言，如果一座守星塔要向一座岛屿传递消息，其消耗的能量为该座守星塔所处的岛屿到需要接收消息的岛屿的所有空间通道能耗总和，当然，如果一座守星塔向自身所处的岛屿发送消息，则不需要消耗能量，守星塔对岛屿传递消息的信号波动互相独立，也就是说，每座守星塔对于每座岛屿的能量传输互不干扰。

作为城主兼守星使，月凌霜近期正在研究怎样部署守星塔才能使消息传递所消耗的能量最小，现在月凌霜已经找到了记载失昼城七千多年来空间风暴的爆发情况和当时失昼城的守星塔部署的资料，由于历史过于久远，每次能量的消耗情况已经不得而知，现在月凌霜希望你帮助她还原这些史料，具体详见输入格式。

Input Format

第一行三个数 $N,Q,Type$，表示失昼城岛屿数量，月凌霜的询问个数以及该数据点的特殊性质，$Type$ 在二进制下，若第 $i-1$ 位为 $1$，则表示存在特殊性质 $i$。

接下来 $N-1$ 行，每行三个数 $u_{i},v_{i},w_{i}$ 表示岛屿 $u_i$ 和岛屿 $v_i$ 之间存在一条双向空间通道，消息经过这条空间通道需要消耗能量为 $w_i$。

接下来一行 $N$ 个数，由 $0,1$ 两个数字构成，表示第 $i$ 个岛屿在失昼城建城之时是否存在空间风暴，$0$ 表示存在空间风暴，$1$ 表示不存在，同时我们认为，如果一个岛屿不存在空间风暴，那么它一定会吸引人们聚居，若存在空间风暴，则不会有人们在该岛屿居住。

最后 $Q$ 行，每行表示一个事件，具体如下：

$1$ $x$：对于岛屿 $x$，若原本该岛屿没有空间风暴，则空间风暴产生，岛上全体居民撤出该岛，否则表示该岛屿空间风暴散去，人们重新回到这里居住。

$2$ $x$ $y$：月凌霜向你提出一个询问，询问若此时部署守星塔在 $x$ 到 $y$ 的简单路径上，则向所有有居民的岛屿传递一次消息所需要的能量消耗之和最小为多少。一座守星塔可以同时向多座岛屿传递消息，也可以不向任何岛屿传递消息。

Output Format

输出 $Q$ 行，每行一个数，表示该次询问的答案。

5 2 0
1 2 2
1 3 3
4 3 2
5 3 7
0 1 1 0 1
2 2 4
2 4 3

7
12

6 3 0
2 1 3
3 1 5
4 1 2
6 4 8
4 5 9
1 1 1 0 0 1
2 1 1
1 5
2 3 6

18
12

Hint

特殊性质 $1$：$v_{i}=u_{i}+1$。

特殊性质 $2$：月凌霜所有的询问的 $x$ 和 $y$ 相同。

特殊性质 $3$：月凌霜所有的询问的 $x=1$。

对于所有的 $w_{i}$，保证 $0 \leq w_{i}\leq 10^{5}$。

对于 $100\%$ 的数据，保证 $N,Q\leq 200000,0\leq Type\leq 7$。

样例 1 解释：

初始图像如左图。

对于第一个询问如中图，有 $2,3,5$ 有居民，所以$ans_2=ans_3=0,ans_5=7$，所以$ans=7$。

对于第二组询问如右图，$ans_2=2+3=5,ans_3=0,ans_5=7$，因此 $ans=7+5=12$。

样例 2 解释：

初始图如左上。

询问 $1$ 点如图右上，存在 $1,2,3,6$ 有居民。 $ans_1=0,ans_2=3,ans_3=5,ans_6=8+2=10$，因此 $ans=3+5+10=18$。

1 操作后所有有居民点如左下。

接下来的操作图为右下，同上有 $ans_1=0,ans_2=3,ans_3=0,ans_5=9,ans_6=0$，所以 $ans=3+9=12$。