题目描述

JAG 王国中有 $N$ 个城镇，城镇之间由若干条单向道路连接，每条道路都有一个通行费。

道路的起点和终点可以相同，即允许自环。但是，不存在两条不同的道路拥有完全相同的起点和终点。

你希望制定一个旅行计划，使得旅途中恰好经过 $L$ 条道路。

旅行计划满足：

• 出发城镇和终点城镇可以任意选择；
• 出发城镇和终点城镇可以相同；
• 同一个城镇或同一条道路可以经过多次。

一次旅行计划的分数定义为所经过的全部道路通行费的按位异或值，即 bitwise XOR。

将所有旅行计划按分数从大到小排列，请求出其中第 $K$ 大的分数。

不同的旅行计划可能具有相同的分数。在排名时，每个旅行计划都要单独计算，因此相同分数可能占据多个名次。

输入格式

输入包含不超过 $10$ 组测试数据。

每组测试数据格式如下：

N M L K
a1 b1 w1
a2 b2 w2
...
aM bM wM

• 第一行包含四个整数 $N,M,L,K$；
• 接下来 $M$ 行，每行包含三个整数 $a_i,b_i,w_i$，表示存在一条从城镇 $a_i$ 指向城镇 $b_i$、通行费为 $w_i$ 的道路。

输入以一行四个整数 0 0 0 0 结束。

输出格式

对于每组测试数据：

• 若至少存在 $K$ 个旅行计划，输出第 $K$ 大的分数；
• 否则输出 -1。

数据范围

对于任意 $i\ne j$，保证：

样例

2 4 3 2
1 1 5
1 2 4
2 1 3
2 2 7
3 3 2 4
1 2 3
2 3 4
3 1 5
6 5 1 3
1 2 1
1 3 2
1 4 2
1 5 2
1 6 2
0 0 0 0

6
-1
2