给定一个包含 $N$ 个顶点（编号为 $1, 2, \dots, N$）和 $M$ 条边的连通无向图。第 $i$ 条边连接顶点 $u_i$ 和 $v_i$。图中可能存在重边，但不包含自环。

对于每个 $W = 0, 1, \dots, K$，请解决以下问题： 判断是否存在一种方式，为每条边 $i$（$1 \le i \le M$）分配一个权重 $w_i \in \{0, 1, \dots, L\}$，使得图中任意生成树的权重恰好为 $W$。生成树的权重定义为该生成树所包含的所有边的权重之和。如果存在这样的分配方式，求出所有满足条件的分配方式中 $(w_1)^2 + (w_2)^2 + \dots + (w_M)^2$ 的最小值。

输入格式

输入通过标准输入给出，格式如下：

$N \ M \ K \ L$ $u_1 \ v_1$ $\vdots$ $u_M \ v_M$

• 输入中的所有值均为整数。
• $2 \le N \le 10^5$
• $N - 1 \le M \le 2 \times 10^5$
• $1 \le L, K \le 10^5$
• $1 \le u_i, v_i \le N$
• $u_i \neq v_i$
• 给定的无向图是连通的。

输出格式

对于每个 $W = 0, 1, \dots, K$，按顺序输出问题的答案，并用空格分隔。具体而言，如果不存在满足条件的分配方式，输出 -1。如果存在，输出所有满足条件的分配方式中 $(w_1)^2 + (w_2)^2 + \dots + (w_M)^2$ 的最小值。

样例

样例输入 1

4 4 3 2
1 2
2 3
2 4
3 4

样例输出 1

0 1 3 4

样例输入 2

2 3 2 1
1 2
2 1
1 2

样例输出 2

0 3 -1

样例输入 3

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

样例输出 3

0 1 2 5 6 7 10 13 22 25

说明

在样例 1 中，例如当 $W = 2$ 时，如果我们设置 $(w_1, w_2, w_3, w_4) = (0, 1, 1, 1)$，则图中任意生成树的权重均为 2。

在样例 2 中，无法使图中任意生成树的权重等于 2。