COVID-19 is spreading rapidly and has become a pandemic in no time. Starting from a few countries, it is expanding indefinitely.

Initially, there are K countries (numbered 0 to K-1) – with the i^th country (0 < i < K) having S_i COVID-19 viruses.

The no. of COVID-19 viruses in the N^th country (N > K) is given by: -
S_N = S_N-1 + S_N-2 + S_N-3 + … + S_N-K

This sequence continues infinitely and we call it - “The COVID-19 Sequence”.

You need to answer Q queries. In each query, you are given an integer N. You need to find the value of S_N modulo 2. Can you answer them quickly?

Input:

• The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
• The first line contains two space-separated integers – K , Q.
• The next line contains K space-separated integers S_i .
• The i^th of the next Q lines contains a single integer N, describing the query.

Output:

For each query, print a single line containing one integer – the value of S_N modulo 2.

Constraints:

• 1 < T < 5
• 1 < K < 1000
• 1 < Q < 10⁵
• 0 < S_i < 10⁹
• 0 < N < 10¹⁰⁰⁰⁰⁰
• Sum of D.Q (D = no. of digits in N) over all test cases does not exceed 10⁶
   

Test Files:

Test File #1 (10 points):

• K = 2
• 0 < N < 10⁹
• S_o = 0
• S₁ = 1

Test File #2 (10 points):

• K = 2
• 0 < N < 10⁹

Test File #3 (10 points):

• K = 3
• 0 < N < 10⁹

Test File #4 (30 points):

• 0 < N < 10⁹

Test File #5 (40 points): original constraints