You are visiting a fair in byteland. You are shopping and want to buy Q items. Each item cost exactly B[i] amount of money. You have no money but you have a magical bag on which you can apply an operation any times you want. In bag there are N integers denoted by array A. In one operation, You choose two integer X Y from A and deposit all of the amount of money M you have, this will magically increase your money by X ⊕ Y. Note: You have to deposit all money you have otherwise you will be exiled from Byteland for your greed. Also, shopkeepers have no change, So you have to pay exact amount. :p Treating each item as independent and starting with 0 amount of money, Can you find if we can buy each item? 

Problem Constraints
2 ≤ N ≤ 1000
1 ≤ A[i] ≤ 10000
1 ≤ Q ≤ 100000
0 ≤ B[i] ≤ 10^9

Input Format 
First argument contains an integer array A of size N. Second argument contains an integer array B of size Q. 

Output Format 
Return a binary string of size Q containing i as 1 if its possible to buy ith item else 0.

Example Input 

Input 1:
A = [1, 2], B = [3, 5, 10, 15]

Input 2:
A = [1, 2, 3], B = [1, 5, 10]

Example Output 

Output 1:
"1001"

Output 2:
"111"

My approach : As N is only 1000 we can generate all possible xor pairs whose value will not exceed the maximum possible value of array element (i.e.10000). Let's store all the xor values from all possible pairs in another array XOR_ARRAY. After this for each query we basically need to find if there exists some subset in the XOR_ARRAY whose sum is equal to the required value. Seems like subset sum problem but constraints are large so I am stuck here.

Please let me know if I am thinking in correct way or is there some other approach to solve this problem. Thanks in advance :)