Background

"By the brushwood gate, a dog barks; through wind and snow, a traveler returns at night." Winter arrives unexpectedly. A thousand miles are frozen, and ten thousand miles are swept by snow. Feathery snow whirls in the air, and snowflakes drift down to the world. The people on the Planet of Positive Energy (a colony of pty on spore) are awed by this beauty. However, pty is not pleased; he dislikes a world of white and finds it too monotonous. So he wants to dye the snowflakes to make the world more colorful.

Problem Description

There are $n$ snowflakes arranged in a line. pty will perform $m$ coloring operations. In the $i$-th coloring operation, he colors all snowflakes between the $((i\times p+q)\bmod n)+1$-th snowflake and the $((i\times q+p)\bmod n)+1$-th snowflake (inclusive) with color $i$. Here $p, q$ are two given positive integers. He wants to know the final color of each of the $n$ snowflakes. Output $0$ for any snowflake that is never colored.

Input Format

The input consists of four lines, each containing one integer, namely $n, m, p, q$, as described above.

Output Format

Output $n$ lines. The $i$-th line contains one integer, the color of the $i$-th snowflake.

4
3
2
4

2
2
3
0

Hint

• For $20\%$ of the testdata: $n,m\leq 1000$.
• For $40\%$ of the testdata: $n\leq 8000$, $m\leq 10^6$.
• For $80\%$ of the testdata: $n\leq 5\times 10^5$, $m\leq 10^7$.
• For $100\%$ of the testdata: $1\leq n\leq 10^6$, $1\leq m\leq 10^7$.

It is guaranteed that $1\leq m\times p+q,m\times q+p\leq 2\times 10^9$.

Translated by ChatGPT 5