题目描述

在 XCPC 竞赛里，会有若干道题目，一支队伍可以对每道题目提交若干次。我们称一支队伍对一道题目的一次提交是有效的，当且仅当：

• 在本次提交以前，还未通过该题目；
• 本次提交的题目在比赛里最终被该队伍通过了。

注意，事实上，在通过一道题目后，一支队伍仍然可以提交该题目。这样的提交是无效提交。

我们按顺序给出本场比赛所有队伍的全部提交记录，每条记录是一个三元组 $(tid_i,pid_i,state_i)$，其中 $tid_i$ 表示提交这条记录的队伍编号，$pid_i$ 表示这条记录所提交的题目编号，$state_i$ 表示这条记录的状态是未通过/通过。

如果一支队伍在比赛里通过了至少 $k$ 道不同的题目，则它们获得了奖牌。

你要求出本场比赛的顽强拼搏奖归属于哪支队伍。很遗憾的是，每个主办方对顽强拼搏奖的定义是不同的，因此你需要按如下四种计算方法分别计算获得顽强拼搏奖所归属的队伍编号：

1. 最后一次 AC 记录所对应的队伍；
2. 最后一次有效 AC 记录所对应的队伍；
3. 未获得奖牌的队伍的最后一次有效 AC 提交对应的队伍；
4. 最后一次使得一支队伍的通过题目数由 $0$ 变成 $1$ 的提交所对应的队伍。

输入格式

第一行是四个整数，依次表示记录数量 $n$，队伍数量 $t$，题目数量 $p$ 和获得奖牌的题目数 $k$。

接下来 $n$ 行，每行三个整数 $tid_i,pid_i,state_i$，表示一次提交记录。其中 $state_i=0$ 表示本次提交未通过，$state_i=1$ 表示本次提交已通过。

我们认为后输入的提交记录的提交时间晚于先输入的提交记录。

输出格式

输出一行四个用空格隔开的整数，依次表示按这四种评奖方法评定，顽强拼搏奖所归属的队伍的编号。

如果按某种评定方法没有顽强拼搏奖队伍，在对应位置输出 $-1$。

样例 #1

样例输入 #1

8 4 2 2
1 1 1
1 2 1
2 2 1
3 1 1
4 1 1
4 2 1
2 1 1
1 2 1

样例输出 #1

1 2 3 4

提示

数据规模与约定

对全部的测试数据，保证 $1\leq n\leq 1000$，$1\leq tid_i\leq t\leq 100$，$1\leq pid_i\leq p\leq 100$，$1\leq k\leq p$，$0\leq state_i\leq 1$。