Description

如果 A 和 B 是朋友，B 和 C 也是朋友，那么说 A、B、C 都是同一个帮派里的。

现给出 $x$ 个兄弟关系，请你弄清其中的帮派关系，再求出 $n$ 个海盗分 $m$ 个金币的最新方法。

毒瘤预警：

当然，你仍然需要保证结果号码较小的分到的金币尽可能的多，哪怕破坏帮派之间的关系。（自行理解）

Input Format

第一行，五个数 $n, m, p, x, k$ 之间用空格隔开，分别表示强盗数目，金币数目，最低赞成百分比，兄弟关系总数以及所谓的友情所需要的代价。

接下来 $X$ 行，每行两个数，$i, j$，表示 $i$ 和 $j$ 是兄弟关系（或是说在同一个帮派）。

Output Format

只有一行，$N$ 个数之间用空格隔开，表示最后的结果。

如果某个海盗死了，输出 $-1$ 代替。

5 7 50 2 1
1 2
3 2

5 1 1 0 0

Hint

数据范围及约定

对于100%的数据：$1\le n\le 1000$，$0\le m\le 10^5$，$1\le p\le 100$，$1\le x\le 500$，$1\le k\le 100$。