题目描述

幼儿园又到了玩耍时间，老师 Tom 遇到了麻烦。孩子们经常因为“谁该玩哪个玩具”发生争执。只要某个孩子认为玩具分配不公平，就会开始大哭。

孩子们的决策能力显然并不可靠，所以 Tom 今天决定不让他们自己选玩具，而是由自己为每个孩子指定一个玩具，使得没有孩子会哭。

Tom 已经研究了孩子们的行为，知道他们会在什么情况下哭。首先，如果一个孩子没有玩具玩，他会哭。其次，即使一个孩子 $A$ 有玩具，如果存在另一个孩子 $B$ 正在玩某个玩具 $T$，并且 $A$ 因为 $B$ 玩 $T$ 而嫉妒 $B$，同时 $A$ 更想玩 $T$ 而不是自己当前的玩具，那么 $A$ 也会哭。

此外，Tom 观察到孩子们有以下四个行为特点：

1. 嫉妒性：孩子会嫉妒那些昨天在某个玩具上玩得比自己更久的人。若孩子 $A$ 昨天玩玩具 $T$ 的时间严格长于孩子 $B$，那么今天 $B$ 会因为 $A$ 玩 $T$ 而嫉妒 $A$。
2. 固执性：孩子更想玩自己昨天玩过的玩具；并且昨天越早第一次开始玩的玩具，今天越想玩。所有昨天完全没玩过的玩具，对该孩子来说同样不想玩。
3. 不能一心多用：一个孩子同一时刻不会玩超过一个玩具。
4. 不合作：孩子们不擅长分享，同一时刻两个孩子不会玩同一个玩具。

Tom 记录了昨天每个孩子在什么时候开始玩哪个玩具。根据这些信息，他希望为今天制定一个固定的玩具分配方案，使得如果可能的话，没有孩子会哭。

输入格式

第一行包含两个整数 $n,m$，分别表示孩子数量和玩具数量。孩子编号为 $1$ 到 $n$，玩具编号为 $1$ 到 $m$。

$$1 \le n,m \le 1000$$

第二行包含两个整数 $d,e$，分别表示昨天玩耍时间总长度（单位为微秒）和 Tom 记录的事件数。

$$1 \le d \le 10^9,\qquad 0 \le e \le 10^6$$

接下来 $e$ 行，每行描述一个事件，包含三个整数 $s,k,t$。

• $s$：从昨天玩耍开始起经过的微秒数；
• $k$：孩子编号；
• $t$：孩子 $k$ 开始玩的玩具编号。

如果 $t=0$，表示孩子 $k$ 在时刻 $s$ 停止玩任何玩具。

约束为：

$$0 \le s < d,\qquad 1 \le k \le n,\qquad 0 \le t \le m$$

事件按时间非降序给出。Tom 记录了玩耍结束前所有孩子的玩具变化事件。特别地，如果某个孩子 $k_1$ 抢走了另一个孩子 $k_2$ 的玩具，那么在同一微秒也会有事件记录 $k_2$ 的玩具变化，即使 $k_2$ 只是停止玩任何玩具。

开始时，没有孩子正在玩玩具，但他们可以在时刻 $0$ 开始玩玩具。时刻 $d$ 时，所有仍在玩玩具的孩子都会停止玩，但 Tom 没有记录这些事件。

同一个孩子在同一微秒内不会切换超过一次玩具。

输出格式

如果存在一种今天的分配方案，使得没有孩子会哭，输出 $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