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