幼儿园的玩耍时间又变得混乱了，汤姆老师遇到了一些困难。孩子们经常因为谁该玩哪个玩具而产生分歧。每当孩子觉得玩具分配不公时，他们就会开始大哭。孩子们显然不擅长做决定，所以今天汤姆有一个新计划：与其让孩子们自己选择玩具，不如他以一种能防止任何孩子哭泣的方式为他们分配玩具。

汤姆一直在研究孩子们的行为，现在他完全理解了他们在什么情况下会哭。首先，如果一个孩子没有玩具玩，他会哭。其次，即使有玩具，如果存在另一个孩子 $B$ 正在玩某个玩具 $T$，而孩子 $A$ 因为 $B$ 在玩 $T$ 而嫉妒他，且 $A$ 更愿意玩 $T$ 而不是他当前拥有的玩具，那么孩子 $A$ 也会哭。此外，汤姆观察到了孩子们的以下四种行为特征：

(a) 嫉妒：孩子们会嫉妒那些在任何给定玩具上玩得比他们久的人。如果孩子 $A$ 昨天玩玩具 $T$ 的时间严格多于孩子 $B$，那么今天 $B$ 就会因为 $A$ 玩 $T$ 而嫉妒他。

(b) 固执：孩子更愿意玩他昨天玩过的玩具，并且他昨天第一次玩该玩具的时间越早，他今天就越想玩它。对于孩子昨天完全没玩过的所有玩具，孩子对它们的渴望程度（或不渴望程度）是相同的。

(c) 不能一心多用：孩子在同一时间从不玩超过一个玩具。

(d) 不合作：孩子们不擅长分享，两个孩子从不在同一时间玩同一个玩具。

汤姆记录了昨天哪些孩子玩了哪些玩具，并记下了每个孩子开始玩玩具的时间。利用这些信息，汤姆的目标是为今天的所有玩具制定一个固定的分配方案，如果可能的话，防止任何孩子哭泣。

输入格式

输入的第一行包含两个整数 $n$ 和 $m$ ($1 \le n, m \le 1000$)，分别表示孩子的数量和玩具的数量。孩子编号为 $1$ 到 $n$，玩具编号为 $1$ 到 $m$。接下来一行包含两个整数 $d$ 和 $e$ ($1 \le d \le 10^9$ 且 $0 \le e \le 10^6$)，分别表示昨天玩耍的总时长（以微秒为单位）和汤姆记录的事件数量。

接下来 $e$ 行给出了汤姆昨天记录的事件。每个事件由一行包含三个整数 $s, k, t$ ($0 \le s < d, 1 \le k \le n, 0 \le t \le m$) 描述，表示孩子 $k$ 在时间 $s$（自昨天玩耍开始以来的微秒数）开始玩玩具 $t$。如果 $t = 0$，则表示孩子 $k$ 在时间 $s$ 停止玩任何玩具。

事件按时间非递减顺序给出（即 $s$ 的值是非递减的）。所有孩子在玩耍结束前的所有玩具变更都已被汤姆记录（特别是如果一个孩子 $k_1$ 从另一个孩子 $k_2$ 那里抢走了一个玩具，也会有一个事件表明 $k_2$ 在同一微秒内更换了玩具，即使 $k_2$ 停止玩任何玩具）。在玩耍开始时，没有孩子在玩任何玩具（但他们可以在时间 $0$ 开始玩玩具）。在时间 $d$，所有仍在玩玩具的孩子都停止了玩耍，但汤姆没有记录这些事件。孩子们每微秒更换玩具的次数不超过一次。

输出格式

如果存在一种玩具分配方案使得今天没有任何孩子哭泣，则输出 $n$ 个不同的整数，其中第 $i$ 个整数是孩子 $i$ 应该玩的玩具。如果存在多种可能的解决方案，输出其中任意一个即可。否则，如果不存在这样的分配方案，输出 “impossible”。

样例

样例输入 1

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

样例输出 1

1 2

样例输入 2

2 1
20 3
0 1 1
10 1 0
10 2 1

样例输出 2

impossible

样例输入 3

1 3
3 3
0 1 1
1 1 2
2 1 3

样例输出 3

2