#38 「 天天去哪吃 」

统计

吃饭是自古以来令人头疼的问题,最后天天决定写一个程序来替他做决定。

现在已知有$n$个餐厅,编号从$0$到$n-1$。记$a_i$表示第$i$天决定吃什么,令

$$t_{i0} = \alpha a_{i-1} + \beta a_{i-2} \ mod\ n$$

$$t_{ij} = t_{i(j-1)} + 1 \ mod\ n, j \ge 1$$

天天不想连续几天吃一样的餐厅,所以如果在前面$\lfloor \frac{n}{2} \rfloor$天中吃过某个餐厅,就不想再去这个餐厅。所以我们要找一个最小的$k$,使得$t_{ik}$ 不为前$\lfloor \frac{n}{2} \rfloor$天去过的餐厅。那么天天第$i$ 天就想去$t_{ik}$餐厅。

现在已知$a_1$和$a_2$,想让你输出$a_3 ... a_m$,即接下来$m-2$天 天天会去哪里吃饭。

输入格式

第一行两个整数$n$和$m$。其中$2\le n \le 100,000, 3 \le m \le 200,000$

第二行两个整数,分别为$\alpha$ 和$\beta$。其中$0 \le \alpha, \beta \le 10^9$

第三行两个整数,为$a_1$,$a_2$。其中$0 \le a_1, a_2 < n$,且$a_1 \ne a_2$

输出格式

一行$m-2$个整数,表示接下来$m-2$天里,天天去哪里吃饭。

样例数据

input

3 4
7 11 
2 0

output

1 2

样例解释

$t_{30} = 7a_{2} + 11 a_{1} \ mod\ n = 1$,前面$\lfloor \frac{n}{2} \rfloor = 1$ 天没有出现,所以第三天去1号餐厅。

$t_{40} = 1$,前面1天已经出现,所以第四天去$t_{41} = 2$号餐厅。

数据规模与约定

$2\le n \le 100,000, 3 \le m \le 200,000$,且保证$\alpha, \beta$为随机选择的两个素数,所以可以认为$t_{i0}$为一个随机数。

时间限制:1s

空间限制:512MB

Author: Chenyao2333