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,\dots ,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=(\sum _{i=1}^n(-1{)}^{i+1}\cdot a_{k-i})\mathrm{\%}m$ where $\mathrm{\%}$ denotes the modulo operation.

E.g., for $n=4$ it is $a_k=(a_{k-1}-a_{k-2}+a_{k-3}-a_{k-4})\mathrm{\%}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,\dots ,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