武侍乐队
题号：NC214406
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

“醒醒吧，武侍，咱们把这座城市，烧成灰。” 

夜之城内有n个场地可供演出，n-1条道路将他们连通，武侍有m个巡演计划。  

每场巡演计划预计从u出发，最终到v，在这个过程中，我们将武侍的表演风格记为s，从所周知，夜之城是一个鱼龙混杂的地方，所以每个场地附近的人对于音乐有着不同的见解，我们将其记为x，如果表演风格与当地人对音乐的见解差距太大，就可能不被当地居民所接受，银手认为这个差距可以记成。  

对于每一场巡演，银手都能预计到和表演风格相差最大的城市位置，为了避免影响评价，银手会选择跳过这座城市，一次巡演预计取得的正面评价是除了跳过城市外所有途径城市的x的异或和S。  

武侍出道时已累计了一定的好评，我们称其为w，对于每次巡演，你需要帮助武侍求出每次巡演最大的。其中。

输入描述:

第一行包含三个整数n,m,w，分别是夜之城可供演出的场地，武侍乐队的巡演次数，出道时的好评。  

接下来的n-1行，每行两个整数p,q，表示编号为p的场地与编号为q的场地之间有一条双向边，保证场地之间连通。  

接下来的一行有n个整数，表示这n个场地的人们对音乐的见解x。  

接下来m行，每行三个整数u,v,s，表示巡演起点，终点，与风格。

输出描述:

对于每一次巡演，输出最大的
示例1

输入

复制 
7 4 11
1 2
2 5
3 4
1 3
4 7
3 6
2 4 6 3 7 9 5
3 7 1
4 6 6
5 6 5
1 7 7

输出

复制 
15
15
15
11

备注:

对于 的数据，保证。