Problem Description

给定一棵包含 $n$ 个节点的带边权的树，树是一个无环的无向联通图。定义 $xordist(u,v)$ 为节点 $u$ 到 $v$ 的简单路径上所有边权值的异或和。

有 $q$ 次询问，每次给出 `l r x`，求 $\sum_{i=l}^rxordist(i,x)$ 的值。

Input

测试点包含多组数据。第一行包含一个整数 $T$（$1\leq T\leq 10$），表示数据组数。每组数据的输入格式如下：

第一行包含一个整数 $n$（$1\leq n\leq 10^5$），表示节点的个数。

接下来 $n-1$ 行，每行包含三个整数 $u$、$v$ 和 $w$（$1\leq u,v\leq n$，$0\leq w<2^{30}$），表示 $u$ 和 $v$ 之间存在一条权值为 $w$ 的无向边。保证输入是一棵树。

接下来一行，包含一个整数 $q$（$1\leq q\leq10^5$），表示询问的次数。

接下来 $q$ 行，每行包含三个整数 $l$、$r$ 和 $x$（$1\leq l\leq r\leq n$，$1\leq x\leq n$），分别表示每次询问的信息，其含义已在上文说明。

Output

每组数据包含 $q$ 行，每行一个整数，表示每次询问的答案。

1
4
1 2 1
1 3 2
3 4 4
2
1 4 3
1 2 4

9
13

Hint

本题输入数据较多，建议大家使用关闭同步流后的 cin 和 cout 输入输出。具体代码如下：

```cpp
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);

// you code

return 0;
}
```

样例中的树如下图所示：


- 对于第一个询问，答案为 $2+1\bigoplus2+4=2+3+4=9$。
- 对于第二个询问，答案为 $2\bigoplus4+1\bigoplus2\bigoplus4=6+7=13$。