题目描述

大 W 是一个打工人，他只有很低的工资。为了生存下去，他决定规划一个策略来让自己的工资变多。

大 W 所在的城市可以看作一张 $n$ 个点、$m$ 条无向边的连通图，边有边权。
每个点代表一个公司，每条边代表两个公司之间的关系，边权 $w$ 是两个公司的好感度。
图里可能存在重边甚至自环。

大 W 目前在公司 $s$，工资为 $d$。他想要最终去公司 $t$ 工作，并且拿到尽量多的工资。
大 W 可以以任意顺序做以下两件事情：

1. 从当前所在的 $a$ 公司跳槽到与其有连边的 $b$ 公司，工资变成 $d \oplus w$。其中 $\oplus$ 是按位异或，$w$ 是两个公司的好感度。
2. 在当前所在的 $a$ 公司努力工作，工资翻倍。

由于精力有限，他只能努力工作至多 $k$ 次，而跳槽可以跳任意多次。

现在有 $q$ 组询问，每组给出 $s,t,d,k$，请输出他能拿到的最大工资。

输入格式

第一行输入测试点编号 id（样例中为 0）。
第二行输入三个正整数 $n,m,q$。
接下来 $m$ 行，每行输入三个整数 $u,v,w$，表示公司 $u$ 与公司 $v$ 之间有好感度 $w$ 的关系（无向边）。
接下来 $q$ 行，每行输入四个整数 $s,t,d,k$，含义同题面。

输出格式

输出 $q$ 行，每行一个整数表示答案。

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

7
6

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

7
15

样例解释

• 样例 1：第一种情况依次经过 $(1,2),(2,3),(3,4)$ 到 4，最终工资是 7。
  第二种情况先在 2 努力工作一次，工资变为 4，然后经过 $(2,3)$ 到 3，最终工资是 6。

数据范围与提示