#include <algorithm>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include <cmath>

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<bool> vb;
#define all(c) c.begin(), c.end()
#define rall(c) c.rbegin(), c.rend()
#define INFLL (ll)(1e18)
#define INF 0x3f3f3f3f
#define EPS 1e-9

template<class T>
istream &operator>>(istream &is, vector<T> &a_vector) {
    for (int i = 0; i < a_vector.size(); ++i)
        is >> a_vector[i];
    return is;
}

bool prime(ll n) {
    for (ll i = 2; i * i <= n; ++i)
        if (n % i == 0)
            return false;
    return true;
}

int main() {
    int b, k;
    cin >> b >> k;
    string s;
    cin >> s;
    ll n = stoll(s, 0, 16);
    if (k == 2) {
        ll d = sqrt(n) + 1;
        while (d >= 2) {
            if (n % d == 0 && prime(d)) {
                printf("%x\n%x", d, n / d);
                return 0;
            }
            --d;
        }
    } else {
        int d = 2;
        set<int> ans;
        ll kk = n;
        while (d * d <= kk) {
            if (n % d == 0) {
                ans.insert(d);
                n /= d;
            } else
                ++d;
        }
        if (n != 1)
            ans.insert(n);
        for (int i:ans)
            printf("%x\n", i);
    }
}