$kn$ 個の頂点を持つ無向単純グラフが与えられる。各頂点の次数は $kd$ 未満であることが保証されている。

このグラフから $n$ 個の頂点を選び、それらによって誘導される部分グラフにおいて、各頂点の次数が $d$ 未満となるような頂点集合を求めよ。

入力

1 行目に 4 つの正整数 $k, n, d, m$ が与えられる。

続く $m$ 行の各行には、辺を表す 2 つの正整数 $u, v$ が与えられる。

出力

選んだ頂点集合を表す、$1$ から $kn$ までの互いに異なる $n$ 個の正整数を出力せよ。

入出力例

入力 1

2 3 2 9
1 2
2 3
3 1
4 5
5 6
6 4
1 4
2 5
3 6

出力 1

3 4 5

提示

すべてのデータにおいて、以下が成り立つ。 $2 \leq k \leq 10, 1 \leq d \leq 10, 1 \leq n \leq 10^3, m \leq \frac{k(k-1)}{2}dn$

データセット $1 \sim 2$ について、$kn \leq 20$。

データセット $3 \sim 5$ について、$d = 1$。

データセット $6 \sim 8$ について、$k = 2$。

データセット $9 \sim 10$ について、特別な制約はない。