Let's consider a₀, minimum of them.

The point is when you can make x, you also can make x + a₀.

So, try finding some of the minimum numbers you can construct in a way that you can construct all of the numbers from them.

Complexity:

//                           <................ be name khoda .................>
#include<bits/stdc++.h>
using namespace std;
int iin(){int x;scanf("%d",&x);return x;}
int n, k;
const int N = 10001;
const int maxA = 100001;
const int inf = 1e9 + 1;
int ans[ maxA + 1];
int mn = 0;
main()
{
	fill( ans, ans + maxA + 1, inf);
	n = iin();
	ans[ 0 ] = 0;
	mn = iin();
	n--;
	while(n--){
		int cc = iin();
		int gcd = __gcd(mn, cc);
		int t = mn / gcd;
		for(int j = 0;j < gcd; j++){
			int c = inf;
			for(int k = 0; k < t * 2; k++){
				int I = ( j + ((cc%mn) * k )) % mn;
				if( ans[ I ] < c ) c = ans[ I ];
				else ans[ I ] = c;
				c += cc;
			}
		}
	}
	k = iin();
	while( k-- ){
		int c = iin();
		if( ans[ c % mn ] > c ) printf("NIE\n");
		else printf("TAK\n");
	}
	
}

Actually, it uses dijkstra to implement what I said in hint 3.

Complexity:

#include <bits/stdc++.h>
using namespace std;
int INF = 2000000000,A[5005],dist[50005];
set < pair<int,int> > dijk;
int main()
{
	int n;
	scanf("%d", &n);
	for (int i = 0; i < n; ++i)
	{
		scanf("%d", &A[i]);
	}
	for (int i = 0; i < A[0]; ++i)
	{
		dist[i] = INF;
	}
	dist[0] = 0;
	dijk.insert(make_pair(dist[0],0));
	while(!dijk.empty())
	{
		pair<int,int> top = *dijk.begin();
		dijk.erase(top);
		int v = top.second;
		int d = top.first;
		for (int i = 1; i < n; ++i)
		{
			int d2 = d+A[i];
			int v2 = (v+A[i])%A[0];
			if(d2 < dist[v2])
			{
				if(dist[v2] < INF)
					dijk.erase(make_pair(dist[v2],v2));
				dist[v2] = d2;
				dijk.insert(make_pair(dist[v2],v2));
			}
		}
	}
	int k;
	scanf("%d", &k);
	while(k--)
	{
		int x;
		scanf("%d", &x);
		if(dist[x%A[0]] <= x)
			printf("TAK\n");
		else
			printf("NIE\n");
	}
	return 0;
}

582C - Superior Periodic Subarrays

632E - Thief in a Shop