题目描述

给出一棵$n$个点的树，点从$1$到$n$编号，给出树上每条边的长度。 你需要顺次执行$m$个操作，操作有三个参数$L\;R\;x$：对于当前这棵树，查询编号在$[L,R]$内的所有点到点$x$的距离之和。 数据可能会强制在线。

输入

第一行三个整数$n,m,type$，$type=1$表示数据强制在线。 接下来$n−1$行，其中第$i$行包含三个正整数$a,b,c$，表示树上的第$i$条边连接点$a$和点$b$，边的长度为$c$。 接下来$m$行，顺次描述$m$个操作。 若$type=1$： ①、设$lastans$为上一次操作的答案模$n$的值（初始为$0$）。 ②、对于每个操作，输入的$L,R,x$都需要异或$lastans$。

输出

对于每个操作，输出一行一个整数表示答案。

输入样例

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

输出样例

27
15
12

提示

【样例解释】 第1次操作：答案$= 3 + 6 + 0 + 9 + 9 = 27$。 第3次操作：答案$= 3 + 0 + 6 + 3 + 3 = 15$。 第4次操作：答案$= 3 + 9 = 12$。 【数据规模及约定】 对于100%的数据，$1≤n,m≤60000，0≤type≤1，1≤a,b≤n，0≤c≤10^9$。

评测数据说明

本题使用按题意独立构造、以独立程序核对的训练数据及公开样例，共5个测试点，非原站或官方原始数据。总分100分。