// test only
#include <bits/stdc++.h>
template<typename...>using my_void_t = void;
template<>struct std::is_integral<__int128>: public std::true_type {};
template<>struct std::is_integral<__uint128_t>: public std::true_type {};
template<typename _Tp>constexpr int my_countr_zero(_Tp __x)noexcept {
    constexpr auto _Nd = std::numeric_limits<_Tp>::digits;

    if (__x == 0)
        return _Nd;

    constexpr auto _Nd_ull = std::numeric_limits<uint64_t>::digits;
    constexpr auto _Nd_u = std::numeric_limits<unsigned>::digits;

    if _GLIBCXX17_CONSTEXPR(_Nd <= _Nd_u)
        return __builtin_ctz(__x);
    else if _GLIBCXX17_CONSTEXPR(_Nd <= _Nd_ull)
        return __builtin_ctzll(__x);
    else {
        constexpr auto __max_ull = std::numeric_limits<uint64_t>::max();
        uint64_t __low = __x & __max_ull;

        if (__low)
            return __builtin_ctzll(__low);

        uint64_t __high = __x >> _Nd_ull;
        return __builtin_ctzll(__high) + _Nd_ull;
    }
}
template<typename _Clock, typename = my_void_t<typename _Clock::rep, typename _Clock::period, typename _Clock::duration, typename _Clock::time_point, decltype(_Clock::is_steady), decltype(_Clock::now())>>struct
    __check_time_helper {
    typename _Clock::time_point t;
    double used;
    __check_time_helper() {
        used = 0;
    } void start() {
        t = _Clock::now();
    } void stop() {
        used += std::chrono::duration_cast<std::chrono::nanoseconds>(_Clock::now() - t).count() / 1e6;
    }~__check_time_helper() {
        fprintf(stderr, "time used: %.2lfms\n", used);
    }
};
namespace OY {
template<uint64_t _BufferSize, uint64_t _BlockSize>class inputHelper {
public:
    FILE *m_filePtr;
    char m_buf[_BufferSize], *m_end, *m_cursor;
    bool m_ok;
    void flush() {
        uint64_t a = m_end - m_cursor;

        if (a >= _BlockSize)
            return;

        memmove(m_buf, m_cursor, a);
        uint64_t b = fread(m_buf + a, 1, _BufferSize - a, m_filePtr);
        m_cursor = m_buf;

        if (a + b < _BufferSize) {
            m_end = m_buf + a + b;
            *m_end = EOF;
        }
    } public:
    explicit inputHelper(const char *inputFileName): m_ok(true) {
        if ((ptrdiff_t)inputFileName <= 0 || !*inputFileName)
            m_filePtr = stdin;
        else
            m_filePtr = fopen(inputFileName, "rt");

        m_end = m_cursor = m_buf + _BufferSize;
    }~inputHelper() {
        fclose(m_filePtr);
    } static constexpr bool isBlank(char c) {
        return c == ' ' || c == '\t' || c == '\n' || c == '\r';
    } static constexpr bool isEndline(char c) {
        return c == '\n' || c == EOF;
    } const char &getChar_Checked() {
        if (m_cursor < m_end)
            return*m_cursor;

        uint64_t b = fread(m_buf, 1, _BufferSize, m_filePtr);
        m_cursor = m_buf;

        if (b < _BufferSize) {
            m_end = m_buf + b;
            *m_end = EOF;
        }

        return*m_cursor;
    } const char &getChar_Unchecked()const {
        return*m_cursor;
    } void next() {
        ++m_cursor;
    } void setState(bool _ok) {
        m_ok = _ok;
    } template<typename _Tp, typename std::enable_if<std::is_signed<_Tp>::value &std::is_integral<_Tp>::value, int>::type = 0>inputHelper<_BufferSize, _BlockSize>
    &operator>>(_Tp &ret) {
        while (isBlank(getChar_Checked()))
            next();

        flush();

        if (getChar_Unchecked() == '-') {
            next();

            if (isdigit(getChar_Unchecked())) {
                ret = -(getChar_Unchecked() - '0');

                while (next(), isdigit(getChar_Unchecked()))
                    ret = ret * 10 - (getChar_Unchecked() - '0');
            } else
                m_ok = false;
        } else {
            if (isdigit(getChar_Unchecked())) {
                ret = getChar_Unchecked() - '0';

                while (next(), isdigit(getChar_Unchecked()))
                    ret = ret * 10 + (getChar_Unchecked() - '0');
            } else
                m_ok = false;
        }

        return*this;
    } template<typename _Tp, typename std::enable_if<std::is_unsigned<_Tp>::value &std::is_integral<_Tp>::value, int>::type = 0>inputHelper<_BufferSize, _BlockSize>
    &operator>>(_Tp &ret) {
        while (isBlank(getChar_Checked()))
            next();

        flush();

        if (isdigit(getChar_Unchecked())) {
            ret = getChar_Unchecked() - '0';

            while (next(), isdigit(getChar_Unchecked()))
                ret = ret * 10 + (getChar_Unchecked() - '0');
        } else
            m_ok = false;

        return*this;
    } template<typename _Tp, typename std::enable_if<std::is_floating_point<_Tp>::value, int>::type = 0>inputHelper<_BufferSize, _BlockSize>
    &operator>>(_Tp &ret) {
        bool neg = false, integer = false, decimal = false;

        while (isBlank(getChar_Checked()))
            next();

        flush();

        if (getChar_Unchecked() == '-') {
            neg = true;
            next();
        }

        if (!isdigit(getChar_Unchecked()) && getChar_Unchecked() != '.') {
            m_ok = false;
            return*this;
        }

        if (isdigit(getChar_Unchecked())) {
            integer = true;
            ret = getChar_Unchecked() - '0';

            while (next(), isdigit(getChar_Unchecked()))
                ret = ret * 10 + (getChar_Unchecked() - '0');
        }

        if (getChar_Unchecked() == '.') {
            next();

            if (isdigit(getChar_Unchecked())) {
                if (!integer)
                    ret = 0;

                decimal = true;
                _Tp unit = 0.1;
                ret += unit * (getChar_Unchecked() - '0');

                while (next(), isdigit(getChar_Unchecked())) {
                    unit *= 0.1;
                    ret += unit * (getChar_Unchecked() - '0');
                }
            }
        }

        if (!integer && !decimal)
            m_ok = false;
        else if (neg)
            ret = -ret;

        return*this;
    } inputHelper<_BufferSize, _BlockSize> &operator>>(char &ret) {
        while (isBlank(getChar_Checked()))
            next();

        ret = getChar_Checked();

        if (ret == EOF)
            m_ok = false;
        else
            next();

        return*this;
    } inputHelper<_BufferSize, _BlockSize> &operator>>(std::string &ret) {
        while (isBlank(getChar_Checked()))
            next();

        if (getChar_Checked() != EOF) {
            ret.clear();

            do {
                ret += getChar_Checked();
                next();
            } while (!isBlank(getChar_Checked()) && getChar_Unchecked() != EOF);
        } else
            m_ok = false;

        return*this;
    } explicit operator bool() {
        return m_ok;
    }
};
template < uint64_t _BufferSize = 1 << 20 > class outputHelper {
    FILE *m_filePtr = nullptr;
    char m_buf[_BufferSize], *m_end, *m_cursor;
    char m_tempBuf[50], *m_tempBufCursor, *m_tempBufDot;
    uint64_t m_floatReserve, m_floatRatio;
public:
    outputHelper(const char *outputFileName, int prec = 6): m_end(m_buf + _BufferSize) {
        if ((ptrdiff_t)outputFileName <= 0 || !*outputFileName)
            m_filePtr = stdout;
        else
            m_filePtr = fopen(outputFileName, "wt");

        m_cursor = m_buf;
        m_tempBufCursor = m_tempBuf;
        precision(prec);
    }~outputHelper() {
        flush();
        fclose(m_filePtr);
    } void precision(int prec) {
        m_floatReserve = prec;
        m_floatRatio = pow(10, prec);
        m_tempBufDot = m_tempBuf + prec;
    } outputHelper<_BufferSize> &flush() {
        fwrite(m_buf, 1, m_cursor - m_buf, m_filePtr);
        fflush(m_filePtr);
        m_cursor = m_buf;
        return*this;
    } void putChar(const char &c) {
        if (m_cursor == m_end)
            flush();

        *m_cursor++ = c;
    } void putS(const char *c) {
        while (*c)
            putChar(*c++);
    } template<typename _Tp, typename std::enable_if<std::is_signed<_Tp>::value &std::is_integral<_Tp>::value, int>::type = 0>outputHelper<_BufferSize>
    &operator<<(const _Tp &ret) {
        _Tp _ret = _Tp(ret);

        if (_ret >= 0) {
            do {
                *m_tempBufCursor++ = '0' + _ret % 10;
                _ret /= 10;
            } while (_ret);

            do
                putChar(*--m_tempBufCursor);

            while (m_tempBufCursor > m_tempBuf)
                ;
        } else {
            putChar('-');

            do {
                *m_tempBufCursor++ = '0' - _ret % 10;
                _ret /= 10;
            } while (_ret);

            do
                putChar(*--m_tempBufCursor);

            while (m_tempBufCursor > m_tempBuf)
                ;
        }

        return*this;
    } template<typename _Tp, typename std::enable_if<std::is_unsigned<_Tp>::value &std::is_integral<_Tp>::value, int>::type = 0>outputHelper<_BufferSize>
    &operator<<(const _Tp &ret) {
        _Tp _ret = _Tp(ret);

        do {
            *m_tempBufCursor++ = '0' + _ret % 10;
            _ret /= 10;
        } while (_ret);

        do
            putChar(*--m_tempBufCursor);

        while (m_tempBufCursor > m_tempBuf)
            ;

        return*this;
    } template<typename _Tp, typename std::enable_if<std::is_floating_point<_Tp>::value, int>::type = 0>outputHelper<_BufferSize>
    &operator<<(const _Tp &ret) {
        if (ret < 0) {
            putChar('-');
            return*this << -ret;
        }

        _Tp _ret = ret * m_floatRatio;
        uint64_t integer = _ret;

        if (_ret - integer >= 0.4999999999)
            integer++;

        do {
            *m_tempBufCursor++ = '0' + integer % 10;
            integer /= 10;
        } while (integer);

        if (m_tempBufCursor > m_tempBufDot) {
            do
                putChar(*--m_tempBufCursor);

            while (m_tempBufCursor > m_tempBufDot)
                ;

            putChar('.');
        } else {
            putS("0.");

            for (int i = m_tempBufDot - m_tempBufCursor; i--;)
                putChar('0');
        }

        do
            putChar(*--m_tempBufCursor);

        while (m_tempBufCursor > m_tempBuf)
            ;

        return*this;
    } outputHelper<_BufferSize> &operator<<(const char &ret) {
        putChar(ret);
        return*this;
    } outputHelper<_BufferSize> &operator<<(const std::string &ret) {
        putS(ret.data());
        return*this;
    }
};
template<uint64_t _BufferSize, uint64_t _BlockSize>inputHelper<_BufferSize, _BlockSize> &getline(
    inputHelper<_BufferSize, _BlockSize> &ih, std::string &ret) {
    ret.clear();

    if (ih.getChar_Checked() == EOF)
        ih.setState(false);
    else {
        while (!inputHelper<_BufferSize, _BlockSize>::isEndline(ih.getChar_Checked())) {
            ret += ih.getChar_Unchecked();
            ih.next();
        }

        ih.next();
    }

    return ih;
}
} using OY::getline;
template<__uint128_t __mod, bool __isprime = true>class DynamicModInt {
public:
    using u32 = uint64_t;
    using i64 = __int128_t;
    using u64 = __uint128_t;
    using m64 = DynamicModInt;
    using value_type = u64;
    static inline u64 mod() {
        return s_mod;
    } static inline u64 get_primitive_root_prime() {
        if (!s_isPrime)
            return 0;

        u64 tmp[500] = {};
        u64 cnt = 0;
        const u64 phi = s_mod - 1;
        u64 m = phi;

        for (u64 i = 2; i * i <= m; ++i) {
            if (m % i == 0) {
                tmp[cnt++] = i;

                do
                    m /= i;

                while (m % i == 0)
                    ;
            }
        }

        if (m != 1)
            tmp[cnt++] = m;

        for (m64 res = 2;; res += 1) {
            bool f = true;

            for (int i = 0; i < cnt && f; ++i)
                f &= res.pow(phi / tmp[i]) != 1;

            if (f)
                return u64(res);
        }
    } constexpr DynamicModInt(): v_() {}~DynamicModInt() = default;
    template < typename T, typename std::enable_if < std::is_arithmetic<T>::value ||
               std::is_same<T, i64>::value ||
               std::is_same<T, u64>::value, int >::type = 0 > inline DynamicModInt(T v): v_(reduce(mul(norm(v % i64(s_mod)),
                           r2))) {} constexpr DynamicModInt(const m64 &) = default;
    inline u64 val()const {
        return reduce({0, v_});
    } template < typename T, typename std::enable_if < std::is_arithmetic<T>::value ||
                 std::is_same<T, i64>::value ||
                 std::is_same<T, u64>::value, int >::type = 0 > explicit constexpr operator T()const {
        return T(val());
    } inline m64 operator-()const {
        m64 res;
        res.v_ = (s_mod & -(v_ != 0)) - v_;
        return res;
    } inline m64 inv_exgcd()const {
        i64 x1 = 1, x3 = 0, a = val(), b = s_mod;

        while (b != 0) {
            i64 q = a / b, x1_old = x1, a_old = a;
            x1 = x3, x3 = x1_old - x3 * q, a = b, b = a_old - b * q;
        }

        return m64(x1);
    } inline m64 inv_fermat()const {
        return pow(s_mod - 2);
    } inline m64 inv()const {
        return s_isPrime ? inv_fermat() : inv_exgcd();
    } inline m64 &operator=(const m64 &) = default;
    inline m64 &operator+=(const m64 &rhs) {
        v_ += rhs.v_ - s_mod;
        v_ += s_mod & -(v_ >> 127);
        return*this;
    } inline m64 &operator-=(const m64 &rhs) {
        v_ -= rhs.v_;
        v_ += s_mod & -(v_ >> 127);
        return*this;
    } inline m64 &operator*=(const m64 &rhs) {
        v_ = reduce(mul(v_, rhs.v_));
        return*this;
    } inline m64 &operator/=(const m64 &rhs) {
        return operator*=(rhs.inv());
    } friend inline m64 operator+(const m64 &lhs, const m64 &rhs) {
        return m64(lhs) += rhs;
    } friend inline m64 operator-(const m64 &lhs, const m64 &rhs) {
        return m64(lhs) -= rhs;
    } friend inline m64 operator*(const m64 &lhs, const m64 &rhs) {
        return m64(lhs) *= rhs;
    } friend inline m64 operator/(const m64 &lhs, const m64 &rhs) {
        return m64(lhs) /= rhs;
    } friend inline bool operator==(const m64 &lhs, const m64 &rhs) {
        return lhs.v_ == rhs.v_;
    } friend inline bool operator!=(const m64 &lhs, const m64 &rhs) {
        return lhs.v_ != rhs.v_;
    } template<typename _Istream>friend inline _Istream &operator>>(_Istream &is, m64 &rhs) {
        i64 x;
        is >> x;
        rhs = m64(x);
        return is;
    } template<typename _Ostream>friend _Ostream &operator<<(_Ostream &os, const m64 &rhs) {
        return os << rhs.val();
    } inline m64 pow(u64 y)const {
        m64 res(1), x(*this);

        for (; y != 0; y >>= 1, x *= x)
            if (y & 1)
                res *= x;

        return res;
    } static inline void set_mod(u64 mod, bool prime = true) {
        s_mod = mod;
        s_isPrime = prime;
        r = get_r();
        r2 = get_r2();
    } static inline u64 init(u64 val) {
        return reduce(mul(val, r2));
} private:
    static constexpr std::pair<u64, u64>mul(u64 x, u64 y) {
        u64 a = x >> 64, b = u32(x), c = y >> 64, d = u32(y), ad = a * d, bc = b * c;
        return{a *c + (ad >> 64) + (bc >> 64) + (((ad & ~UINT64_C(0)) + (bc & ~UINT64_C(0)) + (b * d >> 64)) >> 64), x * y};
    } static constexpr u64 mulh(u64 x, u64 y) {
        u64 a = x >> 64, b = u32(x), c = y >> 64, d = u32(y), ad = a * d, bc = b * c;
        return a * c + (ad >> 64) + (bc >> 64) + (((ad & ~UINT64_C(0)) + (bc & ~UINT64_C(0)) + (b * d >> 64)) >> 64);
    } static inline u64 get_r() {
        u64 two = 2, iv = s_mod * (two - s_mod * s_mod);
        iv *= two - s_mod * iv;
        iv *= two - s_mod * iv;
        iv *= two - s_mod * iv;
        iv *= two - s_mod * iv;
        return iv * (two - s_mod * iv);
    } static inline u64 get_r2() {
        u64 iv = -u64(s_mod) % s_mod;

        for (int i = 0; i != 128; ++i)
            ((iv <<= 1) >= s_mod) && (iv -= s_mod);

        return iv;
    } static constexpr u64 reduce(const std::pair<u64, u64> &x) {
        u64 res = x.first - mulh(x.second * r, s_mod);
        return res + (s_mod & -(res >> 127));
    } static constexpr u64 norm(i64 x) {
        return x + (s_mod & -(x < 0));
    } u64 v_;
    static inline u64 s_mod = __mod;
    static inline u64 s_isPrime = __isprime;
    static inline u64 r = get_r();
    static inline u64 r2 = get_r2();
};
using mint = DynamicModInt<3, true>;
bool prime(const __uint128_t &x) {
    static constexpr __uint128_t first_prime[25] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97};

    if (x <= 100)
        return std::binary_search(first_prime, first_prime + 25, x);

    mint::set_mod(x, false);
    const mint one(1), none(-1);
    __uint128_t y(x - 1);
    const unsigned iend = my_countr_zero(y);
    y >>= iend;

    for (mint base : {
                2, 7, 61, 325
            }) {
        mint z(base.pow(y));

        if (z.val() == 1)
            continue;

        unsigned i = 0;

        for (; i ^ iend; i++) {
            if (z == none)
                break;

            z *= z;
        }

        if (i == iend)
            return false;
    }
    return true;
}
uint64_t seed = 5489ull;
static std::mt19937_64 rng;
__uint128_t gcd(__uint128_t a, __uint128_t b) {
    if (!a || !b)
        return a | b;

    int i = my_countr_zero(a), j = my_countr_zero(b), k = std::min(i, j);
    a >>= i;
    b >>= j;

    while (true) {
        if (a < b)
            std::swap(a, b);

        if (!(a -= b))
            break;

        a >>= my_countr_zero(a);
    }

    return b << k;
}
template<typename _Tp>struct Cipolla {
    static inline _Tp legrende(unsigned a) {
        return _Tp(a).pow((_Tp::mod() - 1) >> 1);
    } static inline std::pair<_Tp, _Tp>find_nsqr(unsigned n) {
        _Tp none(-1);

        for (unsigned i = sqrt(n) + 1e-6 + 1; i < _Tp::mod(); i++)
            if (unsigned tmp(i * i - n); legrende(tmp) == none)
                return{_Tp(i), _Tp(tmp)};

        return none;
    } static inline _Tp a, n, c;
    static inline void set_nsqr(unsigned n) {
        _Tp none(-1);

        for (unsigned i = sqrt(n) + 1e-6 + 1; i < _Tp::mod(); i++)
            if (unsigned tmp(i * i - n); legrende(tmp) == none) {
                a = i;
                c = tmp;
                return;
            }
    } struct cp {
        _Tp _M_real, _M_imag;
    public:
        cp(const _Tp &r, const _Tp &i): _M_real(r), _M_imag(i) {} cp(const _Tp &r = _Tp()): _M_real(r),
            _M_imag(0) {} cp(const cp &o): _M_real(o._M_real), _M_imag(o._M_imag) {} cp(cp &&o): _M_real(o._M_real),
        _M_imag(o._M_imag) {} public:
        cp &operator=(const cp &o) {
            _M_real = o._M_real;
            _M_imag = o._M_imag;
            return*this;
        } cp &operator=(const _Tp &o) {
            _M_real = o;
            _M_imag = 0;
            return*this;
        } public:
        ~cp() {
            _M_real = 0;
            _M_imag = 0;
        } public:
        cp operator+(const cp &o)const {
            return cp(_M_real + o._M_real, _M_imag + o._M_imag);
        } cp operator*(const cp &o)const {
            return cp(_M_real * o._M_real + _M_imag * o._M_imag * c, _M_real * o._M_imag + _M_imag * o._M_real);
        } friend cp operator-(const cp &o) {
            return cp(-o._M_real, -o._M_imag);
        } cp operator-(const cp &o)const {
            return*this + -o;
        } public:
        cp &operator+=(const cp &o) {
            return*this = *this + o;
        } cp &operator*=(const cp &o) {
            return*this = *this * o;
        } cp &operator-=(const cp &o) {
            return*this = *this - o;
        } public:
        _Tp &real() {
            return _M_real;
        } _Tp &imag() {
            return _M_imag;
        } const _Tp &real()const {
            return _M_real;
        } const _Tp &imag()const {
            return _M_imag;
        } cp conj()const {
            return cp(_M_real, -_M_imag);
        }
    };
    static cp qpow(const cp &bs, unsigned po) {
        cp ans(1, 0), base(bs);

        while (po) {
            if (po & 1)
                ans *= base;

            base *= base;
            po >>= 1;
        }

        return ans;
    } static inline _Tp get_sqr(const _Tp &nn) {
        n = nn;

        if (n == _Tp(0))
            return _Tp(0);

        if (legrende(n.val()) != 1)
            return _Tp(-1);

        set_nsqr(n.val());
        return qpow(cp(a, 1), (_Tp::mod() + 1) >> 1).real();
    } static inline _Tp get_sqr_unchecked(const _Tp &nn) {
        n = nn;
        set_nsqr(n.val());
        return qpow(cp(a, 1), (_Tp::mod() + 1) >> 1).real();
    }
};
__uint128_t rho(__uint128_t value) {
    mint::set_mod(value, false);
    mint x, y, z, c;
    uint64_t i, j;

    while (true) {
        y = x = rng();
        z = 1;
        c = rng();
        i = 0;
        j = 1;

        while (++i) {
            y = y * y + c;
            z *= (x.val() > y.val()) ? (x - y) : (y - x);

            if (x == y || !z.val())
                break;

            if (!(i & 127) || i == j) {
                if (__uint128_t g = gcd(z.val(), value); g > 1)
                    return g;

                if (i == j) {
                    x = y;
                    j <<= 1;
                }
            }
        }
    }
}
__uint128_t squfof(__uint128_t value) {
    __uint128_t s = sqrtl(1.0l * value) + 1e-6;

    while (s * s > value)
        s--;

    if (s * s == value)
        return s;

    __int128 d, po, p, p_prev, q, q_prev, q_, b, r;
    long long l, b_, i;
    int k = 0;
    l = 2 * sqrtl(2.0l * s);
    b_ = 3 * l;

    if (b_ > 20000000)
        return rho(value);

    while (++k) {
        d = k * value;
        po = p_prev = p = sqrtl(1.0l * d);
        q_prev = 1;
        q = d - po * po;

        while (q < 0) {
            po--;
            p_prev--;
            p--;
            q = d - po * po;
        }

        if (!q)
            return gcd(value, k);

        for (i = 2; i < b_; i++) {
            b = (po + p) / q;
            p = b * q - p;
            q_ = q;
            q = q_prev + b * (p_prev - p);
            r = sqrtl(1.0 * q) + 1e-6;

            if (!(i & 1) && r * r == q)
                break;

            q_prev = q_;
            p_prev = p;
        }

        if (i >= b_)
            continue;

        b = (po - p) / r;
        p_prev = p = b * r + p;
        q_prev = r;
        q = (d - p_prev * p_prev) / q_prev;
        i = 0;

        do {
            b = (po + p) / q;
            p_prev = p;
            p = b * q - p;
            q_ = q;
            q = q_prev + b * (p_prev - p);
            q_prev = q_;
            i++;
        } while (p != p_prev && i < b_);

        if (i >= b_)
            continue;

        r = gcd(value, q_prev);

        if (r != 1)
            return r;
    }

    return 0;
}
template<typename _ModType>class barrett {
    _ModType _M_mod;
    int _M_l;
    __uint128_t _M_inv;
    static constexpr auto _Nd = std::numeric_limits<_ModType>::digits;
    static constexpr auto _Nd_ull = std::numeric_limits<uint64_t>::digits;
    static constexpr auto _Nd_ul = std::numeric_limits<unsigned long>::digits;
    static constexpr auto _Nd_u = std::numeric_limits<unsigned>::digits;
public:
    static_assert(std::is_integral<_ModType>::value &&std::is_unsigned<_ModType>::value,
                  "_ModType must be an unsigned integral type");
    constexpr barrett() = default;
    constexpr barrett(const _ModType &mod): _M_mod(mod),
        _M_l(_Nd_ull + _Nd - __builtin_clzll((uint64_t)mod) - ((mod & (mod - 1)) != 0)),
        _M_inv(((unsigned __int128)1 << _M_l) / mod + ((mod & (mod - 1)) != 0)) {} constexpr void set_mod(
        const _ModType &mod) {
        _M_mod = mod;
        _M_l = _Nd_ull + _Nd - __builtin_clzll((uint64_t)mod) - ((mod & (mod - 1)) != 0);
        _M_inv = ((unsigned __int128)1 << _M_l) / mod + ((mod & (mod - 1)) != 0);
    } constexpr _ModType mod()const {
        return _M_mod;
    } constexpr _ModType mod(const _ModType &x)const {
        __uint128_t tmp = _M_inv * x;
        _ModType ret = x - (tmp >> _M_l) * _M_mod;
        return ret;
    }
};
namespace qs {
const size_t L = 256;
uint32_t pcnt, root[L];
mint primes[L];
double log_primes[L];
struct word {
    std::bitset<L>mask;
    mint lhs, rhs;
    size_t bit;
    word(): mask(), lhs(), rhs(), bit(L) {} void merge(const word &rOther) {
        lhs *= rOther.lhs;
        rhs *= rOther.rhs;
        const std::bitset<L>cons(mask & rOther.mask);

        for (size_t pos = cons._Find_first(); pos < L; pos = cons._Find_next(pos))
            rhs *= primes[pos];

        mask ^= rOther.mask;
        bit = mask._Find_first();
    } bool operator<(const word &rOther)const {
        return bit < rOther.bit;
    }
};
std::vector<word>smooth;
std::unordered_map<long long, word>data;
__uint128_t insert(word &o) {
    size_t x;

    for (x = 0; x < smooth.size(); x++) {
        if (smooth[x].bit > o.bit)
            break;

        if (smooth[x].bit == o.bit)
            o.merge(smooth[x]);
    }

    if (o.bit == L) {
        __uint128_t g(gcd((o.lhs + o.rhs).val(), mint::mod()));

        if (g != 1 && g != mint::mod())
            return g;
    }

    smooth.insert(smooth.begin() + x, o);
    return 0;
    return 0;
} __int128 try_insert(mint x, __int128 y) {
    word ins;
    ins.lhs = x;
    ins.rhs = 1;

    for (size_t k = 1; k <= pcnt; k++) {
        size_t cnt = 0;

        while (y % (__int128)primes[k].val() == 0)
            y /= (__int128)primes[k].val(), ++cnt;

        if (cnt) {
            ins.mask[k] = cnt & 1;
            ins.rhs *= primes[k].pow(cnt >> 1);
        }
    }

    ins.bit = ins.mask._Find_first();

    if (y != 1) {
        if (data.count(y)) {
            ins.merge(data[y]);
            ins.rhs *= mint(y);
            y = 1;
        } else
            data[y] = ins;
    }

    if (y == 1)
        return insert(ins);

    return 0;
}
void append(uint32_t p) {
    ++pcnt;
    primes[pcnt] = p;
    log_primes[pcnt] = log(1.0 * p);
} uint32_t fastpow(__uint128_t base, uint32_t power, uint32_t mod) {
    barrett<uint32_t>brt(mod);
    base %= mod;
    uint32_t ans = 1;

    for (; power; base = brt.mod(base * base), power >>= 1)
        if (power & 1)
            ans = brt.mod(ans * base);

    return ans;
} void init() {
    using mint_ = DynamicModInt<5, true>;
    uint32_t i, j;
    __uint128_t value = mint::mod();
    uint32_t B = pow(log(1.0 * mint::mod()), 2) * 0.6;
    std::vector<char>mark((B >> 1) + 5);

    for (i = 3; i * i <= B; i += 2)
        if (!mark[i >> 1])
            for (j = i * i; j <= B; j += i << 1)
                mark[j >> 1] = true;

    for (append(2u), i = 3; i <= B; i += 2)
        if (!mark[i >> 1])
            if (fastpow(value, i >> 1, i) == 1)
                append(i);

    root[1] = value % 2;

    for (i = 2; i <= pcnt; i++)
        mint_::set_mod(primes[i].val(), true), root[i] = Cipolla<mint_>::get_sqr(value).val();
} __uint128_t next_prime(__uint128_t x) {
    x += ~x & 1;

    while (!prime(x += 2))
        ;

    return x;
}
__uint128_t quadratic_sieve(__int128 value) {
    if (__int128 tmp = sqrtl(1.0 * value) + 1e-6; tmp * tmp == value)
        return tmp;

    static constexpr __uint128_t first_prime[30] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113};

    for (int i = 1; i < 30; i++)
        if (value % first_prime[i] == 0)
            return first_prime[i];

    if (value <= 1024)
        return squfof(value);

    pcnt = 0;
    data.clear();
    smooth.clear();
    mint::set_mod(value, false);
    init();
    uint32_t M = pcnt * 50;
    uint64_t D = sqrtl(sqrtl(2.0L * value) / M);
    double bound = log(M * sqrtl(0.5L * value)) * 0.75;
    barrett<uint64_t>brt;

    while (true) {
        do
            D = next_prime(D);

        while ((D & 3) == 1)
            ;

        mint::set_mod(D, true);
        uint64_t y0;
        mint y1;
        {
            mint tmp_value(value);

            if (!tmp_value.val())
                return D;

            mint tmp_y0 = tmp_value.pow((D + 1) >> 2);

            if (tmp_y0 * tmp_y0 != tmp_value)
                continue;

            y0 = tmp_y0.val();
            y1 = (value - y0 * y0) / D;
            y1 = y1 * (D / 2 + 1) / tmp_y0;
        }
        __int128 A(D);
        A *= A;
        __int128 B(y1.val()*D + y0);
        __int128 C((B * B - value) / A);
        mint::set_mod(value, false);
        __int128 E = (mint(B) / D).val();
        std::vector<double>pos(M), neg(M);

        for (uint32_t x = 1; x <= pcnt; x++) {
            uint32_t p = primes[x].val();
            brt.set_mod(p);
            uint32_t s = brt.mod(A);
            uint32_t a = s;
            uint32_t inv_a = 1;

            if (!a)
                continue;

            while (a > 1)
                inv_a = brt.mod(1ull * (p - inv_a) * (p / a)), a = p % a;

            uint32_t u = brt.mod(1ull * (p - brt.mod(B)) * inv_a);
            uint32_t v = brt.mod(1ull * root[x] * inv_a);
            uint32_t r1 = brt.mod(u + v), r2 = brt.mod(u + p - v);

            for (uint32_t su = 0; su < M; su += p) {
                if (su + r1 < M)
                    pos[su + r1] += log_primes[x];

                if (su + r2 < M)
                    pos[su + r2] += log_primes[x];

                if (su >= r1)
                    neg[su - r1] += log_primes[x];

                if (su >= r2)
                    neg[su - r2] += log_primes[x];
            }
        }

        for (uint32_t x = 0; x < M; ++x) {
            if (pos[x] > bound)
                if (__uint128_t tmp(try_insert(E + D * x, A * x * x + 2 * B * x + C)); tmp)
                    return tmp;

            if (neg[x] > bound)
                if (__uint128_t tmp(try_insert(E - D * x, A * x * x - 2 * B * x + C)); tmp)
                    return tmp;
        }
    }

    return value;
}
}
main() {
    OY::inputHelper < 1 << 18, 20 > cin("");
    OY::outputHelper < 1 << 18 > cout("");
    __uint128_t x = 0;
    cin >> x;
    __check_time_helper<std::chrono::high_resolution_clock>_Helper;
    _Helper.start();
    __uint128_t factor = qs::quadratic_sieve(x);
    _Helper.stop();

    if (factor > x / factor)
        factor = x / factor;

    cout << factor << ' ' << x / factor;
}