sums.cpp

// By Lawrence Melo

#include <bits/stdc++.h>
using namespace std;
const int maxc = 5e4 + 10;
#define x first
#define y second
typedef pair<int,int> pii;

vector<int> coins;
int n, m;

int dist[maxc];

void dijkstra()
{
	priority_queue<pair<int, int>, vector<pii>, greater<pii> > q;
	int m = coins[0];

	for(int i = 0; i < m; i++) dist[i] = 1000000010;
	
	dist[0] = 0;

	q.push({0, 0});
	
	int cont = 0;

	while(!q.empty())
	{
		int r = q.top().y;
		int d = q.top().x;

		q.pop();
		
		for(auto u : coins)
		{
			if(d + u < dist[(u + r) % m])
			{
				dist[(u + r) % m] = d + u;
				q.push({(d + u), (u + r) % m});
			}
		}
	}
}

int main()
{
	ios::sync_with_stdio(false), cin.tie(nullptr);

	cin >> n;
	for(int i = 0; i < n; i++)
	{
		int a;
		cin >> a;
		coins.push_back(a);
	}

	sort(coins.begin(), coins.end());

	dijkstra();

	cin >> m;

	int mod = coins[0];

	while(m--)
	{
		int a;
		cin >> a;
		if(dist[a % mod] > a) cout << "NIE\n";
		else cout << "TAK\n";
	}
}