小t非常喜爱画画，但是他还是一个初学者。他最近费尽千辛万苦才拜到小Q为师。小Q是画鸡蛋长大的，让小t一入门就拿着一张白纸条疯狂地涂色。假设纸条被划分成了n个区域，用1~n的整数从左到右顺序编号，小Q总共下达了m条指令。第i条指令是让小t把编号为(i*p+q)mod n+1与(i*q+p)mod n+1 (p,q为常整数)之间的区域（连续的一段区域）涂成第i种颜色。

现在由于小Q下达的指令过多，小t一时应付不过来。小Q只让他回答每一个区域最后的颜色。趁小Q还在“五谷轮回之所”忙碌时，小t偷偷的请让你这个计算机高手帮他算出最后的颜色状态，并告诉他。

输入格式

文件仅一行，为四个整数n,m,p,q。

输出格式

文件共n行，第i行代表最后第i个格子的颜色。白色编号为0。

输入样例

4 3 2 4

输出样例

2

2

3

0

数据范围

20%数据满足：1≤n≤1000，1≤m≤10000；

40%数据满足：1≤n≤10000，1≤m≤100000；

program paint;
type
  node=record
    x,y:longint;
  end;
var
  x,y,n,m,i,p,q,t,j,k:longint;
  xia,a:array[0..10000001] of longint;//a[i]记录i点染的颜色，xia即使题解中的next数组
  b:array[0..10000001] of node;//用来保存每次染的区间x~y

begin
  readln(n,m,p,q);
  for i:=1 to n do xia[i]:=i+1;
  for i:=1 to m do begin
    b[i].x:=(i*p+q) mod n+1;
    b[i].y:=(i*q+p) mod n+1;
  end;//记录每次染色区间
  for i:=m-1 downto 1 do begin
    if (b[i].x=b[m].x) and (b[i].y=b[m].y) then begin
      k:=i;break;
    end;//从后向前找循环
  end;
  inc(k);//循环节为k到m
  for i:=m downto k do begin//从后向前枚举
    x:=b[i].x;y:=b[i].y;
    if x>y then begin t:=x;x:=y;y:=t;end;
    j:=x;//j为准备染色的点，最开始为左边界
    while (j<=y) do begin
      if a[j]=0 then a[j]:=i;//没染过就染
      k:=xia[j];//记录下下一次准备染的点
      xia[j]:=xia[y];//更新下染了这个点之后该染哪一个，也就是这个点的xia值，当然是右边界的xia值。。
      j:=k;//由于xia[j]有变化不能直接写j:=xia[j];
    end;
  end;
  for i:=1 to n do begin
    writeln(a[i]);//输出即可
  end;
end.