Background

高斯十分喜欢吃馒头，兴奋之下他一下子买了N 个馒头请所有认识他的人吃。

Description

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

Format

Input

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

Output

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

Sample 1

Input

4 3 2 4

Output

2
2
3
0

Limitation

时间：1s 空间：256M
在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

Source

Amorphophallus Orz Group