#include <bits/stdc++.h>
#define int int64_t
#define F first
#define S second

using namespace std;
const int N = (1LL<<20);
const int INF = 1e18+7;
const int MOD = 1e9+7;

int n,k;
string s;
bool used[N];
vector<int> prime;

string ss="0123456789abcdef";

bool isprime(int x) {
    for(int i=2;i<=sqrt(x);i++)
        if(x%i==0) return false;
    return true;
}

string get(int x) {
    string ttt;
    while(x) ttt+=ss[x%16], x/=16;
    reverse(ttt.begin(), ttt.end());
    return ttt;
}

void compute1()
{
    for(int i=2;i<N;i++) used[i]=true;
    for (int i=2;i<N;i++) {
        if (used[i]==true) {
            prime.push_back(i);
            for (int j=i*i;j<N;j+=i){
                used[j]=false;
            }
        }
    }
}

vector<pair<int,vector<int>>> t;
void compute2()
{
    for(int i=0;i<t.size();i++){
        t[i].S.push_back(prime[i+1]);
        t[i].S.push_back(prime[i]);
        t[i].F=prime[i]*prime[i+1];
    }
}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
//    freopen("input.txt","r",stdin);
//    freopen("output.txt","w",stdout);
    cin>>n>>k;
    cin>>s;
    compute1();
    t.resize(prime.size()-1);
    compute2();
    int number=0,p=1;
    for (int i=s.size()-1;i>=0;i--) {
        number+=ss.find(s[i])*p; p*=16;
    }
    if(k==2){
        for(int i=max((int)sqrt(number)-220,(int)2);;i++)
            if(isprime(i) && isprime(number/i) && number%i==0 && number!=i*i){
                cout<<get(i)<<endl<<get(number/i)<<endl;
                break;
            }
    }else{
        for(auto i : t) {
            for(auto j : t) {
                if(i.F*j.F!=number) continue;
                for(auto y : i.S)
                    cout<<get(y)<<endl;
                for(auto y : j.S)
                    cout<<get(y)<<endl;
                return 0;
            }
        }
    }
}