Recently, I participated in Round 2 of Traveloka Intern hiring challenge on HackerEarth.

Problem Statement

You are given N, the size of the array A and A0, the first element of the array. The other elements of the array can be calculated by:

A[i] >= 3 + A[i-1] , if i is odd
A[i] = 2 * A[i-1] + 3 * A[i-2] , if i is even

i varies from 1 to N - 1

The array follows a special propert. The elements at even indices of the aray are even and elements at odd indices of the array are odd. Your first task is to prepare this array such that the sum of the array is minimized, and array follows all the given conditions.
You are given Q queries. Each query consists of a single integer X. You have to print true if we can achieve it by adding some elements of the array A, false if it is not possible.

Constraints

1 <= T <=50
1<= N <= 5000
1<=A0<=10^6
A0 is even
1<=Q<=1000
1<=X<=10^18

Sample Testcase

Input
1
4 2
5
3 27 36 68 88

Output
false
true
false
true
true

Explanation - Array elements are [2,7,20,61]