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$ ≤ a_i ≤ 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 ≥ 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 ≤ T ≤ 10
1 ≤ n ≤ 10^5
2 ≤ m ≤ 10^9
0 ≤ a_i ≤ m-1
n ≤ z ≤ 10^{18}

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

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().

见题面

见题面