【问题描述】

windy 有一条木板需要被粉刷。这条木板被分为 N 个格子，依次编号为 1 ~ N。

windy 的粉刷分为 K 天。第 i 天，他会将位于 ( i × a + b ) % N + 1 和 ( i × b + a ) % N + 1 之间（包含两端）的所有格子粉刷成同一种颜色。其中 a, b 是输入的两个常数。

如果某个格子之前被粉刷过，则之前的颜色会被覆盖。

由于颜色调配非常麻烦，所以在整个工期内，任意一种颜色只会调配一次，即每天粉刷的颜色都是不同的。

记第 i 天粉刷的颜色为 i。

问：K 天后，每个格子是什么颜色？

【输入格式】

一行，包含 4 个正整数 N，K，a，b

【输出格式】

共 N 行，每行一个整数，依次表示 1 ~ N 号格子在 K 天后的颜色（如果某个格子没有被粉刷过，则对应行输出 0）

【样例输入】

4 3 2 4

【样例输出】

2
2
3
0

【数据范围】

20%的数据，$1 ≤ N ≤ 10^3，1 ≤ K ≤ 10^4$

40%的数据，$1 ≤ N ≤ 10^4，1 ≤ K ≤ 10^5$

60%的数据，$1 ≤ N ≤ 5 × 10^4，1 ≤ K ≤ 5 × 10^5$

80%的数据，$1 ≤ N ≤ 3 × 10^5，1 ≤ K ≤ 3 × 10^6$

100%的数据，$1 ≤ N ≤ 10^6，1 ≤ K ≤ 10^7, 1 ≤ K × a + b, K × b + a ≤ 2^{31}-1$