Given an undirected simple graph with $kn$ vertices, it is guaranteed that the degree of each vertex is less than $kd$.

Find a subset of $n$ vertices such that the degree of each vertex in the induced subgraph is less than $d$.

Input

The first line contains four positive integers $k, n, d, m$.

The next $m$ lines each contain two positive integers $u, v$, representing an edge.

Output

Output $n$ distinct integers between $1$ and $kn$, representing the selected set of vertices.

Examples

Input 1

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

Output 1

3 4 5

Note

For $100\%$ of the data, it is guaranteed that $2\leq k\leq 10$, $1\leq d\leq 10$, $1\leq n\leq 10^3$, and $m\leq \frac{k(k-1)}2dn$.

For data points $1\sim 2$, $kn\leq 20$.

For data points $3\sim 5$, $d=1$.

For data points $6\sim 8$, $k=2$.

For data points $9\sim 10$, there are no special restrictions.