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:
- 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.
- The second line is the positive integer d.
- 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