题目描述

「那仿佛是个奇迹，没错，铭刻于火星历史的，“奇迹的七分钟”」

$\text{CAROLE & TUESDAY}$ 为了将自己的歌曲传唱开来，$\text{Gus}$ 为他们安排了 $m$ 场巡演计划，火星上有 $n$ 座城市，城市之间有 $n-1$ 条道路使他们相互连通

每一场巡演计划预计从城市 $u$ 出发，沿着城市间的道路到达城市 $v$ ，并且使用的音乐风格可以被表述为 $s$ ，由于风俗文化的关系，不同的城市的居民对音乐有不同的见解 $x$，如果音乐风格和当地差别太大，就可能不被当地居民所接受，$\text{Gus}$ 认为这个差别可以用 $s\oplus x$ 来描述

对于每一场巡演，$\text{Gus}$ 都能预计到和表演音乐风格差别最大的城市的位置，为了避免影响评价，$\text{Gus}$ 会选择跳过这个城市，一次巡演预计取得的正面评价是除了跳过的城市之外的所有途径的城市的 $x$ 的异或和 $S$

$\text{CAROLE & TUESDAY}$ 出道时就已经积累的一定的好评 $w$，巡演后的评价同样受其影响，所以你需要帮助 $\text{Gus}$ 求出每次巡演的最大的 $W\oplus S$ ，其中 $W\in[\,0,\,w\,]$

输入格式

第一行包含四个整数 $n,\,m,\,w$ ，表示火星上的城市数、巡演计划数和出道时的好评

下面 $n-1$ 行，每行两个整数 $x,\,y$ 表示城市 $x$ 和城市 $y$ 之间有一条双向的道路，保证城市连通

第 $n+1$ 行包含 $n$ 个整数，第 $i$ 个整数表示城市 $i$ 喜好的音乐风格 $x_i$

下面 $m$ 行，每行包含三个整数 $u,\,v,\,s$ ，表示一次从城市 $u$ 到城市 $v$ 的巡演，风格为 $s$

输出格式

输出包含 $m$ 行，第 $i$ 行表示第 $i$ 场巡演后能够取得的最大好评 $W\oplus S$

数据范围与提示

对于 $100\%$ 的数据，保证 $n,m\le2\times10^5,\;s_i,x_i,w\le2^{30}-1$