#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ull = unsigned long long;
using ld = long double;
#define REP(NAME, NUM) for (int NAME = 0; NAME < (NUM); ++NAME)
#define BREP(NAME, NUM) for (int NAME = (NUM)-1; NAME >= 0; --NAME)
#define ALL(NAME) (NAME).begin(), (NAME).end()

#define VEC(TYPE, A, NAME, INIT) vector<TYPE> NAME(A, INIT)
#define VEC2(TYPE, A, B, NAME, INIT) vector<vector<TYPE>> NAME(A, vector<TYPE>(B, (INIT)))

#define cMOD 1000000007ULL
#define cINF ((1ll<<62)-1)
#define cINFINT ((1<<30)-1)

int main()
{
	cin.tie( 0 ); ios::sync_with_stdio( false );
    //----------------
    
    ull n;
    string s,x;
    cin >> n>>s>>x;
    vector<vector<ll>> dp( n+1, vector<ll>( 0, 0 ) );
    
    dp[n].push_back(0);
    vector<ll> a( 0, 0 );
    vector<ll> b( 0, 0 );
    set<ll> se;
    BREP(i,n)
    {
        ll m = s[i] - '0';
        if(x[i] == 'A')
        {
            a.clear();
            b.clear();
            for(auto j: dp[i+1])REP(k,7)
            {
                if((k*10+0)%7==j) a.push_back(k);
                if((k*10+m)%7==j) b.push_back(k);
            }
            sort(ALL(a));
            sort(ALL(b));
            //REP( j, a.size() ) cout << a[j] << " "; cout << endl;
            //REP( j, b.size() ) cout << b[j] << " "; cout << endl;
            
            set_intersection( ALL( a ), ALL( b ), back_inserter( dp[i] ) );
        }
        else
        {
            se.clear();
            for(auto j: dp[i+1])REP(k,7)
            {
                if((k*10+0)%7==j) se.emplace(k);
                if((k*10+m)%7==j) se.emplace(k);
            }
            for(auto j: se) dp[i].push_back(j);
        }
        
        //REP( j, dp[i].size() ) cout << dp[i][j] << " "; cout << endl;
    }

    cout << 
    (find(ALL(dp[0]), 0)==dp[0].end()
    ? "Aoki" : "Takahashi") << endl;
    
    //----------------
    return 0;
}
#include <cmath>
#include <deque>
#include <algorithm>
#include <iterator>
#include <list>
#include <tuple>
#include <map>
#include <unordered_map>
#include <queue>
#include <set>
#include <unordered_set>
#include <stack>
#include <string>
#include <vector>
#include <fstream>
#include <iostream>
#include <functional>
#include <numeric>
#include <iomanip> 
#include <stdio.h>
//end of libraries
#define lnf 9999999999999999
#define inf 999999999
#define PI 3.14159265359
#define endl "\n"
#define fi first
#define se second
#define pb push_back
#define ll long long
#define all(c) (c).begin(),(c).end()
#define sz(c) (ll)(c).size()
#define mkp(a,b) make_pair(a,b)
#define make_unique(a) sort(all(a)),a.erase(unique(all(a)),a.end())
#define rsz(a,n) a.resize(n)
#define pii pair <ll,ll>
#define rep(i,n) for(ll i = 0 ; i < n ; i++) 
#define drep(i,n) for(ll i = n-1 ; i >= 0 ; i--)
#define crep(i,x,n) for(ll i = x ; i < n ; i++)
#define fcin ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);

const ll max_n = 3000;

using namespace std;
ll n , m , dp[max_n];
vector < pii > vci[max_n],vco[max_n];
set <pii> st;

ll get(ll x) {
	st.clear();
	rep(j,max_n-3) {dp[j] = lnf;}
	dp[x] = 0;

	st.insert({0,x});

	while(sz(st)) {
		auto it = st.begin();
		ll value = it->first;
		ll curr = it->second;

		st.erase(it);

		for(auto &y : vco[curr]) {
			if(dp[y.fi] > y.se + dp[curr]) {
			
				auto ti = st.find({dp[y.fi] , y.fi});
				if(ti!=st.end()) st.erase(ti);

				dp[y.fi] = y.se + dp[curr];
				st.insert({dp[y.fi],y.fi});
			
			}

		}

	}
	ll r = lnf;
	for(auto &y : vci[x]) {
		r = min(dp[y.fi]+y.se,r);
	}
	return r;

}

int main(){
fcin;
	cin >> n >> m;
	
	rep(i,m) {
		ll u , v , c;
		cin >> u >> v >> c;
		u--,v--;
		vci[v].pb({u,c});
		vco[u].pb({v,c});
	}
	// get(0);
	rep(i,n) {
		ll d = get(i);
		// cout << d << "\n";
		if(d>=lnf) cout << "-1\n";
		else cout << d << "\n";
	}
/*
*/
	return 0;	
}