E - Musical Sequences

★★★★★

3.7

31 votes

Approved, Easy-Medium

Details

Submissions

Discussion

Editorial

Problem

Valentina had a birthday recently. She got a special piano from parents. They told her about the piano melodies and the connection with the mathematical sequences. She got amazed and started to use piano keys to create her own musical sequences.

The piano has m keys, numbered 0 through $m-1$ .

Valentina has already hit n keys $a_0, a_1, \ldots, a_{n-1}$ ( $0 \le a_i \le m-1$ ), not necessarily distinct. To get a nice melody, each next key to hit must be chosen according to the following formula for $k \ge n$ : $a_k = \big( \sum_{i=1}^{n} (-1)^{i+1} \cdot a_{k-i} \big) \% m$ where $\%$ denotes the modulo operation.

E.g., for $n = 4$ it is $a_k = \big(a_{k-1} - a_{k-2} + a_{k-3} - a_{k-4}\big) \% m$ .

Given n, m and z, are you able to find $a_z$ , i.e. the z-th key hit by Valentina?

Input format

The first line of the input contains one integer T denoting the number of test cases.

The first line of each test case description contains three integers n, m and z.

The second line contains n integers $a_0, a_1, \ldots, a_{n-1}$ denoting keys already hit by Valentina.

Output format

For each test case, output the answer in a separate line.

Constraints

$1 \le T \le 10$
$1 \le n \le 10^5$
$2 \le m \le 10^9$
$0 \le a_i \le m-1$
$n \le z \le 10^{18}$

Subtasks

Extra constraints	Points	Which tests
$z \le 10^6$	30	1-3
$n \le 10$	40	4-7
no extra constraints	30	8-10

Sample Input

3
4 10 4
1 3 3 7
4 10 5
1 3 3 7
1 2 12345678987654321
1

Sample Output

6
9
1

Time Limit: 3

Memory Limit: 256

Source Limit:

Explanation

In the first sample test case, we know the first $n = 4$ keys hit by Valentina $a_0 = 1, a_1 = 3, a_2 = 3, a_3 = 7$ . We are asked to find $a_4$ . According to the given formula, $a_4 = (a_3 - a_2 + a_1 - a_0) \% m = (7 - 3 + 3 - 1) \% 10 = 6$ .

In the second sample test case, we are given the same first keys but we are asked to find $a_5$ this time. So, $a_5 = (a_4 - a_3 + a_2 - a_1) \% m = (6 - 7 + 3 - 3) \% 10 = 9$ .

In the third sample test case, Valentina will hit the same key over and over, i.e. $a_0 = a_1 = a_2 = \ldots = 1$ .

Stack Limit for C++ is 8MB. You are allowed to increase it in your code, e.g. using setrlimit().

Contributers:

Alexis Hernandez

Errichto Dębowski