#P2054. 疯狂的馒头

疯狂的馒头

疯狂的馒头

题目描述

CQF 把 NN 个白馒头排成一列,从 11 到 NN 编号。然后按顺序进行 MM 次染色,每次把连续的一段馒头改为同一种颜色。

给定两个正整数 p,qp,q。第 ii 次操作的两个端点为

li=(ip+q) mod N+1,ri=(iq+p) mod N+1.l_i=(ip+q)\bmod N+1,\qquad r_i=(iq+p)\bmod N+1.

把这两个端点之间的全部馒头染成颜色 ii,包括两个端点。较早的颜色会被覆盖,始终未染色的馒头颜色为 00。求所有操作完成后每个馒头的颜色。

输入格式

一行四个正整数 N,M,p,qN,M,p,q。

输出格式

输出 NN 行,第 ii 行是第 ii 个馒头的最终颜色。

4 3 2 4
2
2
3
0

数据范围

数据比例 NN 的上限 MM 的上限
20%20\% 10001000 1000010000
40%40\% 1000010000 100000100000
60%60\% 5000050000 500000500000
80%80\% 300000300000 30000003000000
100%100\% 10000001000000 1000000010000000

保证 1≤Mp+q≤231−11\le Mp+q\le2^{31}-1,1≤Mq+p≤231−11\le Mq+p\le2^{31}-1。