一组数据或hack掉所有题解（最快链表，2s左右

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define R register
using namespace std;
int n,m,color[1000010],pre[1000010],nxt[1000010],p,q;
template <typename T> void in(R T &a)
{
    R char c = getchar();R T x=0,f=1;
    while(!isdigit(c)) {if(c == '-') f=-1; c=getchar();}
    while(isdigit(c)) x=(x<<1)+(x<<3)+c-'0',c = getchar();
    a=x*f;
}
int main()
{
    //freopen("color.in","r",stdin);
    //freopen("color.out","w",stdout);
    in(n),in(m),in(p),in(q);
    for(R int i=1;i<=n;i++)
    {
        nxt[i]=i+1;//链表初始化
        pre[i]=i-1;
    }
    for(R int i=m;i>=1;i--)//从后往前
    {
        R int l=(i*p+q)%n+1,r=(i*q+p)%n+1;//计算左右端点
        if(l>r) l^=r,r^=l,l^=r;
        R int now=l;
        while(now<=r)//敲黑板！！！
        {
            R int temp=0;//如果没染过色，就染色、将该点与区间左右端点相连，记录原本的下一个位置为temp
            if(!color[now]) color[now]=i,pre[now]=pre[l],temp=nxt[now],nxt[now]=nxt[r];
            temp==0?now=nxt[now]:now=temp;//temp不为零，则跳到原本的下一个点；为零，则说明该点已经染过色（就是已经缩过点，直接跳到缩点后的下一个端点）
        }
    }
    for(R int i=1;i<=n;i++) printf("%d\n",color[i]);
    return 0;
}