题目背景

小珅和小泽在研究一棵充满魔法的树，这棵树有 $N$ 个结点，每条边都带着神秘的权值。他们发现了异或运算的奇妙之处 —— 它就像不进位的加法，而在树上，两点间路径的权值异或，正好能揭示这条路径的魔法秘密。

题目描述

给定一棵包含 $N$ 个结点的树，树的每条边上有一个权值。 进行 $M$ 次询问，对于每次询问，求某两点之间的路径上所有边权的异或值。

输入格式

第一行一个整数 $N$，表示树的结点数。 接下来 $N-1$ 行，每行三个整数 $u,v,w$，表示 $u$ 和 $v$ 之间有一条权值为 $w$ 的边。 接下来一行一个整数 $M$，表示询问次数。 之后 $M$ 行，每行两个整数 $u,v$，表示询问这两个结点之间路径的权值异或值。

输出格式

输出 $M$ 行，每行一个整数，表示对应询问的异或值。

输入输出样例

5
1 4 9644
2 5 15004
3 1 14635
5 3 9684
3
2 4
5 4
1 1

975
14675
0

说明/提示

对于 $40\%$ 的数据，有 $1 \le N,M \le 3000$；
对于 $100\%$ 的数据，有 $1 \le N ,M\le 100000$。

保证边权在 int 范围内。

20
1 2 82613
1 3 973023
1 4 816086
1 5 108931
2 6 666981
1 7 545838
1 8 2881
3 9 395672
2 10 1028985
9 11 1032072
7 12 728223
1 13 901641
5 14 659475
2 15 365450
6 16 243214
15 17 937808
12 18 739935
14 19 265410
11 20 445493
24
7 19
5 7
10 9
9 11
8 2
10 5
13 5
15 11
3 6
14 8
15 4
13 16
12 12
20 1
18 19
2 17
15 2
11 17
14 4
2 10
17 16
20 5
20 17
20 7

516476
654765
401547
1032072
84468
1005647
813962
245744
374543
766673
565993
334807
0
107258
505788
777434
365450
913568
510534
1028985
149425
2937
736405
653012

6
1 2 684684
2 3 17983
2 4 192590
3 5 436122
5 6 835960
69
4 5
1 6
6 3
3 4
3 4
4 1
6 5
1 3
4 5
2 3
2 1
2 4
1 5
3 2
2 4
1 6
3 4
4 6
1 1
2 2
2 5
3 4
4 4
1 2
3 1
4 3
1 5
1 5
5 6
6 2
1 6
4 4
2 4
3 2
3 2
4 2
1 6
6 2
6 6
1 1
3 1
2 2
3 5
6 3
2 1
5 6
4 5
4 5
5 5
3 2
6 5
5 1
3 2
3 6
2 2
5 5
6 4
2 1
6 1
2 4
3 2
6 6
4 2
2 4
5 1
3 2
2 6
6 5
2 3

266731
21073
681698
177777
177777
557762
835960
668851
266731
17983
684684
192590
824105
17983
192590
21073
177777
577683
0
0
450981
177777
0
684684
668851
177777
824105
824105
835960
663773
21073
0
192590
17983
17983
192590
21073
663773
0
0
668851
0
436122
681698
684684
835960
266731
266731
0
17983
835960
824105
17983
681698
0
0
577683
684684
21073
192590
17983
0
192590
192590
824105
17983
663773
835960
17983