题目

CQF十分喜欢吃馒头。兴奋之下他一下子买了N个馒头请所有认识他的人吃。但是CQF不喜欢白色，而喜欢红色、黄色、绿色等鲜艳的颜色。

于是他把所有白色的馒头排成一列。然后进行M次染色操作。每个染色操作都是用一个神奇的刷子把连续的多个馒头染成特定的某种颜色。一个馒头最终的颜色是最后一次染它的颜色。如果一个馒头没有被染过色，那么它的颜色就是白色。现在CQF已经定好了染色计划：在第i次染色操作中，把第(i×p+q)mod N+1个馒头和第(i×q+p)mod N+1个馒头之间的馒头染成颜色 i，其中p、q是特定的两个正整数。他想立即知道最后每个馒头的颜色。你能帮他吗？

输入格式

１行: 四个正整数N，M，p，q。

输出格式

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

输入样例

4 3 2 4

输出样例

2
2
3
0

数据范围

在20%的数据中，1≤N≤1000，1≤M≤10000

在40%的数据中，1≤N≤10000，1≤M≤100000

在60%的数据中，1≤N≤50000，1≤M≤500000

在80%的数据中，1≤N≤300000，1≤M≤3000000

在100%的数据中，1≤N≤1000000，1≤M≤10000000

保证所以输入数据中1≤M×p + q、M×q + p≤ 2^31－1