#include <fstream>
#include <vector>

using namespace std;

ifstream cin("frac.in");
ofstream cout("frac.out");

long long c[50],n,k,x,y,i,p,u,m,pr,j;

void rez()
{

    long long power = (long long) 1 << 61;
    long long p1 = 0;

    for( ; power ; power >>= 1)
    {

        long long y = p1 + power;

        for (i = 1 ; i < (1 << x); i++)
        {
            pr = 1;

            for (j = 0 ; j <= x; j++)
                if ((i & (1 << j)))
                    pr *= -c[j+1];

            y += p1 + power / pr;
        }
        //cout << p1 + power << ' ' << y << '\n';
        if(y < k)
        {
            p1 += power;
            cout << y << ' ' << p1 << '\n';
        }

    }


    cout << p1 + 1;
}

int main()
{
    long long i;

    cin >> n >> k;

    for (i = 2 ; i * i <= n ; i++)
        if (n % i==0)
        {
            while (n % i == 0)
                n /= i;

            c[++x] = i;
        }

    if (n != 1)
        c[++x] = n;

    rez();
    return 0;
}