#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#pragma GCC optimize("O3")

using namespace std;
using namespace __gnu_pbds;

#define int long long
#define double long double
#define _ << ' ' <<
#define For(i,z) for(int32_t i=0;i<(z);i++)
#define sqr(a) ((a)*(a))

#define pii pair<int, int>
#define f first
#define s second

template<typename T>
using orset = tree <T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

template<typename T, typename K> inline void umax(T &a, K b) { a = max(a, (T)b); }
template<typename T, typename K> inline void umin(T &a, K b) { a = min(a, (T)b); }

const int32_t N = (1<<20);
const int32_t M = 20010;
//const int INF = 1e16 + 10;
const double EPS = 1e-2;
const int II = 1e9 + 10;
const int MOD = 1e9+9;
//const int AMOD = 99194853094755497;
bool bad[N];
vector <int> prime;
void resh() {
    for (int i = 2; i < N; i++) {
        if (bad[i] == false) {
            prime.push_back(i);
            for (int j = i * i; j < N; j += i)
                bad[j] = true;
        }
    }
}

vector <pair<int, vector<int> > > lay2;
void ff() {
    lay2.resize(prime.size()-1);
    For (i, prime.size() - 1) {
        lay2[i].f = prime[i] * prime[i+1];
        lay2[i].s.push_back(prime[i]);
        lay2[i].s.push_back(prime[i+1]);
    }
}


string nums = "0123456789abcdef";

long long mul(long long a, long long b, long long m){
    if(b==1)
        return a;
    if(b%2==0){
        long long t = mul(a, b/2, m);
        return (2 * t) % m;
    }
    return (mul(a, b-1, m) + a) % m;
}

long long pows(long long a, long long b, long long m){
    if(b==0)
        return 1;
    if(b%2==0){
        long long t = pows(a, b/2, m);
        return mul(t , t, m) % m;
    }
    return ( mul(pows(a, b-1, m) , a, m)) % m;
}

bool isprime(long long x){
    if(x == 2)
        return true;
    srand(time(NULL));
    for(int i=0;i<20;i++){
        long long a = (rand() % (x - 2)) + 2;
        if (__gcd(a, x) != 1)
            return false;
        if( pows(a, x-1, x) != 1)
            return false;
    }
    return true;
}

string conv(int ch) {
    string s;
    while (ch) {
        s.push_back(nums[ch%16LL]);
        ch /= 16LL;
    }
    reverse(s.begin(), s.end());
    return s;
}

int32_t main() {
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    srand(time(NULL));
    prime.reserve(N);

    int n, k;
    cin >> n >> k;
    string s; cin >> s;
    int ch = 0, mn = 1;
    for (int i = s.size()-1; i >= 0; i--) {
        ch += nums.find(s[i]) * mn;
        mn *= 16LL;
    }

    if (k == 2) {
        for (int i = sqrt(ch); ; i++)
            if (ch % i == 0 && ch != i * i &&
                isprime(i) && isprime(ch/i)) {
                cout << conv(i) << '\n';
                cout << conv(ch / i);
                return 0;
            }
        cout << "CHLEN\n";
        return 0;
    }

    resh();
    ff();
    for (auto &i : lay2) {
        for (auto &j : lay2) {
            if (i.f * j.f != ch) continue;
            for (auto &z : i.s)
                cout << conv(z) << '\n';
            for (auto &z : j.s)
                cout << conv(z) << '\n';
            return 0;
        }

    }
}