CQF 十分喜欢吃馒头。

兴奋之下他一下子买了 $N$ 个馒头请所有认识他的人吃。

但是 CQF 不喜欢白色，喜欢红色、黄色、绿色等鲜艳的颜色。

于是他把所有白色的馒头排成一列。

然后进行 $M$ 次染色操作。

每个染色操作都是用一个神奇的刷子把连续的多个馒头染成特定的某种颜色。

一个馒头最终的颜色是最后一次染它的颜色。

如果一个馒头没有被染过色，那么它的颜色就是白色。

现在 CQF 已经定好了染色计划:在第 $i$ 次染色操作中，把第 $(i×p+q)\bmod N+1$ 个馒头和第 $(i×q+p)\bmod N+1$ 个馒头之间的馒头染成颜色 $i$，其中 $p, q$ 是特定的两个正整数。

他想立即知道最后每个馒头的颜色。

你能帮他吗?

输入格式

第一行四个正整数 $N,M,p,q$。

输出格式

一共输出 $N$ 行，第 $i$ 行表示第 $i$ 个馒头的最终颜色（如果最终颜色是白色就输出 $0$）。

数据范围

在 $20\%$ 的数据中，$1 \le N \le 10^3,1 \le M \le 10^4$
在 $40\%$ 的数据中，$1 \le N \le 10^4,1 \le M \le 10^5$
在 $60\%$ 的数据中，$1 \le N \le 5 \times 10^4,1 \le M \le 5 \times 10^5$
在 $80\%$ 的数据中，$1 \le N \le 3 \times 10^5,1 \le M \le 3 \times 10^6$
在 $100\%$ 的数据中,$1 \le N \le 10^6,1 \le M \le 10^7$
保证所有输入数据中 $1 \le M \times p + q, M \times q + p \le 2^{31}-1$。

输入样例：

4 3 2 4

输出样例：

2
2
3
0