Sequence (a_i) of natural numbers is defined as follows:

a_i = b_i if i ≤ k
a_i = c₁a_i-1 + c₂a_i-2 + ... + c_ka_i-k if i > k

where b_j and c_j are given natural numbers for 1 ≤ j ≤ k. Your task is to compute a²_m + a²_m+1 + a²_m+2 + ... + a²_n for given m ≤ n and output it modulo a given positive integer p (not necessarily prime).

Input

On the first row there is the number T of test cases (T ≤ 50).
Each following test case contains four lines:

• k - number of elements of (c) and (b) (1 ≤ k ≤ 15)
• b₁,...,b_k - k natural numbers where 0 ≤ b_j ≤ 10⁹ separated by spaces
• c₁,...,c_k - k natural numbers where 0 ≤ c_j ≤ 10⁹ separated by spaces
• m, n, p - natural numbers separated by spaces (1 ≤ m ≤ n ≤ 10¹⁸, 1 ≤ p ≤ 10⁸)

Output

Exactly T lines, one for each test case: (a²_m + a²_m+1 + a²_m+2 + ... + a²_n) modulo p.

Example

Input:
2
3
2 3 5
1 2 3
10 15 1000000
15
401 131 940 406 673 592 532 452 733 966 602 600 61 212 257
13 12 81 75 37 12 10 35 25 75 16 90 27 33 47
2 85704376 99999991
Output:
248783
32397016

Note

You can try the problem SPP first.