H2. Rami's Scheme (Hard Version)
time limit per test
15 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

This is the hard 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 10^9$$$ 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^{18}$$$ representing the terms to calculate.
Output
  1. The first line contains one integer $$$R:$$$ the robustness index of the selected scheme, modulo $$$2^{64}$$$.
  2. The second line contains $$$s$$$ integers $$$w_{n_1},\dots,w_{n_s}:$$$ the calculated terms.
Examples
Input
7 2 6
0 1
14
0 1 2 3 4 5 6 7 8 9 10 11 12 13
Output
7
0 1 5 0 2 6 0 0 1 5 0 2 6 0
Input
499 13 41
0 15
5
0 1 2 3 4
Output
31062750
0 15 405 374 47
Input
17 0 0
2 3
7
0 1 2 3 4 5 6
Output
1
0 3 3 3 3 3 3
Input
5 0 0
4 0
8
0 1 2 3 4 5 6 7
Output
1
0 0 0 0 0 0 0 0
Input
975151579 1 1
0 1
5
0 1 2 3 4
Output
950920601051041662
0 1 3 9 21
Note
  • A period $$$T$$$ of a sequence $$$(H_n)_{n\in\mathbb{N}}$$$ is a strictly positive integer such that $$$\forall k\in\mathbb{N},\quad H_{T+k}=H_k.$$$
  • A sequence is said to be periodic if it has at least one period. The smallest such integer is called the fundamental period.
  • An eventual period $$$T$$$ of a sequence $$$(H)_{n\in\mathbb{N}}$$$ is an integer for which there exists certain integer $$$K$$$ that $$$H_{K},H_{K+1},\dots$$$ is periodic with a period $$$T.$$$
  • a sequence $$$(H)_{n\in\mathbb{N}}$$$ is said to be eventually periodic if it has at least one eventual period. The smallest such eventual period is called the eventual fundamental period.
  • It is guaranteed that the sequence $$$(w_n)_{n\in\mathbb{N}}$$$ is eventually periodic.
  • For the first test case, the first $$$14$$$ terms of the sequence $$$(u_n)_{n\in\mathbb{N}}$$$ are: $$$0,1,2,3,4,5,6,7,8,9,10,11,12,13.$$$ Therefore, the first $$$14$$$ terms of the sequence $$$(w_n)_{n\in\mathbb{N}}$$$ would be: $$$0,1,5,0,2,6,0,0,1,5,0,2,6,0.$$$ It can be proven that $$$(w_n)_{n\in\mathbb{N}}$$$ is indeed periodic as it appears, and its fundamental period is $$$7.$$$
  • For the second test case, the first $$$5$$$ terms of the sequence $$$(u_n)_{n\in\mathbb{N}}$$$ are: $$$0,15,195,156,43.$$$ Clearly, $$$w_0=0,\ w_1=15,$$$ we have: $$$w_2=(15+2\cdot 195)\bmod 499=405,\quad w_3=(405+3\cdot 156)\bmod 499=374,$$$ and $$$w_4=(374+4\cdot 43)\bmod 499=47.$$$ It can be proven that $$$(w_n)_{n\in\mathbb{N}}$$$ is periodic with a fundamental period of $$$31062750.$$$
  • For the third test case, It can be proven that $$$u_n=0 \quad \forall n\ge 2.$$$ Therefore, $$$w_n = 3 \quad \forall n\ge 1.$$$ As $$$w_0=0,$$$ the sequence $$$(w_n)_{n\in\mathbb{N}}$$$ is periodic starting from $$$N= 1.$$$ Its fundamental period is $$$1.$$$
  • For the fourth test case, It can be proven that $$$w_n = 0 \quad \forall n\in\mathbb{N}.$$$ Therfore, $$$(w_n)_{n\in\mathbb{N}}$$$ is periodic starting from $$$N=0$$$ with a fundamental period of $$$1$$$