Integer Sequences from Addition of Terms

We consider sequences formed from the addition of terms of a given sequence. Let {an}, n = 1, 2, 3, . . ., be an arbitrary sequence of integer numbers; d a positive integer. We construct another sequence {bm}, m=1,2,3,...,bydefiningbm asconsistingofn×doccurrencesoftheterman: a3,...,a3 ,··· | {z } Given an and d we want to obtain the corresponding k-th integer in the sequence {bm}. For example, withan =nandd=1wehave3fork=6;wehave4fork=7. Withan =nandd=2,wehave2 for k = 6; we have 3 for k = 7. Input The first line of input contains C (0 < C < 100), the number of test cases that follows. Each of the C test cases consists of three lines:

1. The first line represents an — a polynomial in n of degree i with non-negative integer coefficients in increasing order of the power: an =c0 +c1n+c2n2 +c3n3 +···+cini where cj ∈ IN0, j = 0, . . . , i. This polynomial an is codified by its degree i followed by the coefficients cj , j = 0, . . . , i. All the numbers are separated by a single space.
2. The second line is the positive integer d.
3. The third line is the positive integer k. It is assumed that the polynomial an is a polynomial of degree less or equal than 20 (1 ≤ i ≤ 20) with non-negative integer coefficients less or equal than 10000 (0 ≤ cj ≤ 10000, j = 0, . . . , i); 1 ≤ d ≤ 100000; 1 ≤ k ≤ 1000000. Output The output is a sequence of lines, one for each test case. Each of these lines contains the k-th integer in the sequence {bm} for the corresponding test case. This value is less or equal than 263 − 1. ,b2 = For example, if an = n, and d = 1,then the resulting sequence {bm} is: 1 , 2,2,3,3,3,4,4,4,4,··· |{z} |{z} |{z} | {z } b1 b1 = a1,...,a1 | {z } a2,...,a2 | {z } ,b3 = d occurrences of a1 2d occurrences of a2 3d occurrences of a3 b2 b3 b4

2/2 Sample Input 2 4 3 0 0 0 23 25 100 101 1 6 Sample Output 1866 3