给定一个 $kn$ 个顶点的无向简单图，保证每个点的度数小于 $kd$。

请你求出一个 $n$ 个点的子集，使得导出子图的每个点度数均 小于 $d$。

输入格式

第一行输入四个正整数 $k,n,d,m$。

接下来 $m$ 行每行输入两个正整数 $u,v$ 表示一条边。

输出格式

输出 $n$ 个互不相同的 $1\sim kn$ 间的正整数，表示所选点集。

样例数据

样例输入

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

样例输出

3 4 5

提示

对于 $100\%$ 的数据，保证 $2\leq k\leq 10$，$1\leq d\leq 10$，$1\leq n\leq 10^3$，$m\leq \frac{k(k-1)}2dn$。

对于数据点 $1\sim 2$，$kn\leq 20$。

对于数据点 $3\sim 5$，$d=1$。

对于数据点 $6\sim 8$，$k=2$。

对于数据点 $9\sim 10$，无特殊限制。