E - Musical Sequences

Practice

3.7 (31 votes)

Approved

Easy Medium

Problem

51% Success 2589 Attempts 30 Points 3s Time Limit 256MB Memory 1024 KB Max Code

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

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

Code Editor

You need to be logged in to access the code editor

Please wait while we load the editor

Submissions

Please login to view your submissions

You need to be logged in to access the code editor

Please wait while we load the editor