Fantastic Sequence

Time limit: ? seconds

Memory limit: 64 megabytes

A fantastic sequence a_i is defined in the following way: $a_0,\dots,a_{k-1}$ are given integers, and the subsequent elements are defined by the linear recurrence relation

$a_n=\left(\sum\limits_{i=1}^{k}c_ia_{n-i}\right)+c_{k+1}.\ \ (n\geq k)$ Here $c_1,\dots,c_{k+1}$ are known integers.

You have to find a_n mod m , where n and m are given.

Input

The first line of the input contains the number of the test cases, which is at most 20. The descriptions of the test cases follow. The first line of a test case description contains three integers k (0 ≤ k ≤ 25), m ( $1\leq m<2^{31}$ ), and n ( $0\leq n<2^{31}$ ) separated by spaces. The second line contains the integers $c_1,\dots,c_{k+1}$ separated by spaces ( $-2^{31}\leq c_i<2^{31}$ ). The third line contains the integers $a_0,\dots,a_{k-1}$ separated by spaces ( $-2^{31}\leq a_i<2^{31}$ ). The test cases are separated by blank lines.

Output

For each test case in the input, output one nonnegative integer: a_n mod m . Print a blank line between test cases.

Examples

Input	Output
1 2 10 10 1 1 0 1 1	9