H1. Rami's Scheme (Easy Version)
time limit per test
6 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

This is the easy version of the problem. The difference between the two versions are the constraints.

Rami has been always fond of random numbers, he keeps wondering about how randomness arises from the deterministic nature of mathematics.

Wanting to impress his friends, he created a new pseudo-random number generation scheme, that he proudly called Rami Scheme.

A Rami Scheme is used to generate $$$s$$$ random numbers, it consists of the following steps:

1. choose $$$3$$$ integer parameters: $$$p,a,b$$$ such that $$$0\leq a,b, \lt p$$$ with $$$p$$$ prime

2. choose $$$2$$$ seeds $$$u_0,u_1$$$

3. for $$$k \gt 1,$$$ $$$u_k$$$ will be generated with the following rule: $$$$$$ \boxed{u_k=(au_{k-1}+bu_{k-2})\bmod p} $$$$$$

4. using the rule above, he will calculate many such numbers and use them to generate the following random numbers $$$(w_k)_{k\in\mathbb{N}}$$$: $$$$$$ \boxed{w_k=\left(\sum_{i=0}^kiu_i\right)\bmod p} $$$$$$

5. Finally, he will choose $$$s$$$ numbers $$$w_{n_1},\dots,w_{n_s}.$$$ those final numbers will be his sought random numbers.

Rami wants you to evaluate his scheme:

- First of all, he wants you to measure the robustness index $$$R$$$ of this scheme, which is defined as the eventual fundamental period of the sequence $$$(w_k)_{k\in\mathbb{N}}.$$$ In other words,he wants the smallest strictly positive integer $$$R$$$ such that:

$$$$$$ \boxed{\exists K\in\mathbb{N}/\quad\forall k\in\mathbb{N}_{\ge K}, w_{k+R}=w_k} $$$$$$

- After that, he knows that he cannot calculate all terms of the sequence $$$(w_k)_{k\in\mathbb{N}}$$$, and he only needs $$$s$$$ terms $$$w_{n_1},\dots,w_{n_s}$$$ of it. So he asks your help for it.

As the number $$$R$$$ may be too big, Rami will be happy if you only give him $$$R\bmod 2^{64}.$$$

Input
  1. The first line contains $$$3$$$ integers $$$p,a,b:$$$ the parameters of the scheme, with $$$0 \le a,b \lt p \lt 100$$$ and $$$p$$$ a prime number.
  2. The second line contains $$$2$$$ integers $$$0\leq u_0,u_1 \lt p:$$$ the seeds.
  3. The third line contains one integer $$$0\leq s \leq 10^6:$$$ the number of terms to calculate.
  4. The final line contains $$$s$$$ integers $$$0\leq n_1,\dots,n_s \leq 10^{6}$$$ representing the terms to calculate.
Output

The first line contains one integer $$$R:$$$ the robustness index of the selected scheme, modulo $$$2^{64}$$$.

The second line contains $$$s$$$ integers $$$v_{n_1},\dots,v_{n_s}:$$$ the calculated terms.

Examples
Input
97 3 5
0 1
3
2 7 3
Output
912576
7 79 49
Input
17 0 0
2 3
7
0 1 2 3 4 5 6
Output
1
0 3 3 3 3 3 3
Note

- In this version, it's guaranteed that $$$R \lt 10^6$$$

- It is also guaranteed that the sequence $$$(v_n)_{n\in\mathbb{N}}$$$ is eventually periodic