Background

Special for beginners, ^_^

Description

小t非常喜爱画画，但是他还是一个初学者。他最近费尽千辛万苦才拜到已仙逝的达芬奇为师（神仙？妖怪？谢谢）。达芬奇果然是画鸡蛋长大的，让小t一入门就拿着一张白纸条疯狂地涂色。假设纸条被划分成了n个区域，用1~n的整数从左到右顺序编号，达芬奇总共下达了m条指令。第I条指令是让小t把编号为(Ip+q)mod n+1与(Iq+p)mod n+1(p,q为常整数)之间的区域（连续的一段区域）涂成第I种颜色。你可以假设达芬奇家中颜料的颜色数足够多（达芬奇是画鸡蛋长大的）。

现在由于达芬奇下达的指令过多，小t一时应付不过来。达芬奇只让他回答每一个区域最后的颜色。趁达芬奇还在“五谷轮回之所”忙碌时，小t偷偷的请让你这个计算机高手帮他算出最后的颜色状态，并告诉他。时间紧迫，要快哟！（达芬奇的指令次数多到恶心）

Format

Input

为四个整数n,m,p,q。

Output

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

Samples

1000 999 341 547

897
897
897
897
897
897
897
897
961
961
961
961
961
961
961
961
961
961
961
961
961
961
975
975
975
975
975
975
975
975
975
975
975
975
975
975
975
975
975
975
975
975
983
983
983
983
983
983
983
983
983
983
983
983
983
983
983
983
983
994
994
994
994
994
994
994
994
994
994
994
994
994
994
994
994
994
994
994
994
994
994
994
994
994
994
994
994
994
994
994
994
994
994
994
994
994
994
994
994
994
994
994
994
994
994
994
994
994
994
994
994
994
994
994
994
994
994
994
994
994
994
994
994
994
994
994
994
994
994
994
994
994
994
994
994
994
994
994
994
994
994
994
994
994
994
994
994
994
994
994
994
994
994
996
996
996
996
996
996
996
996
996
996
996
996
996
996
996
996
996
996
996
996
996
996
996
996
996
996
996
996
996
996
996
994
994
994
994
994
994
994
994
994
994
994
994
994
994
994
994
994
994
994
994
994
994
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
998
998
998
998
998
998
998
998
998
998
998
998
998
998
998
998
998
998
998
998
998
998
998
998
998
998
998
998
998
998
998
998
998
998
998
998
998
998
998
998
998
998
998
998
998
998
998
998
998
998
998
998
998
998
998
998
998
998
998
998
998
998
998
998
998
998
998
998
998
998
998
992
992
992
992
992
992
992
992
992
992
992
992
992
992
992
992
992
992
992
992
992
992
992
992
992
992
992
992
992
992
992
992
992
992
992
992
992
992
992
992
992
992
992
992
992
992
992
992
992
992
992
992
992
992
992
992
992
992
992
992
992
992
992
992
992
992
992
992
992
992
992
992
992
992
992
992
992
992
992
992
992
992
992
992
992
992
992
992
992
992
992
992
992
992
992
992
992
992
992
992
972
972
972
972
972
972
972
972
972
972
972
972
972
972
972
972
972
972
972
972
972
972
972
972
972
972
972
972
972
972
972
972
972
972

Limitation

1≤n≤1000000，1≤m≤10000000;1≤mp+q，mq+p≤231-1；

友情提示：

加入编译开关{$M 100000000,0,100000000}，可防栈溢出。