/**
 * 
 */

// header {{{
#include <bits/stdc++.h>
using namespace std;

// C++17 polyfill {{{
template<bool B>
using BoolConstant = integral_constant<bool, B>;
// }}}

// C++20 polyfill {{{
struct IDENTITY {
    using is_transparent = void;
    template<typename T>
    constexpr T&& operator()(T&& x) const noexcept {
        return forward<T>(x);
    }
};
// }}}

#define CPP_STR(x) CPP_STR_I(x)
#define CPP_CAT(x,y) CPP_CAT_I(x,y)
#define CPP_STR_I(args...) #args
#define CPP_CAT_I(x,y) x ## y

#define SFINAE(pred...) std::enable_if_t<(pred), std::nullptr_t> = nullptr

#define ASSERT(expr...) assert((expr))

using i8   = int8_t;
using u8   = uint8_t;
using i16  = int16_t;
using u16  = uint16_t;
using i32  = int32_t;
using u32  = uint32_t;
using i64  = int64_t;
using u64  = uint64_t;
#ifdef __SIZEOF_INT128__
using i128 = __int128;
using u128 = unsigned __int128;
#endif

using f32  = float;
using f64  = double;
using f80  = __float80;
using f128 = __float128;

using complex32 = complex<f32>;
using complex64 = complex<f64>;
using complex80 = complex<f80>;
// }}}

template<typename T> constexpr T PROCON_INF();
template<> constexpr i64 PROCON_INF<i64>() { return 1'010'000'000'000'000'017LL; }
template<> constexpr f64 PROCON_INF<f64>() { return 1e100; }

constexpr i64 INF  = PROCON_INF<i64>();
constexpr f64 FINF = PROCON_INF<f64>();

constexpr i64 MOD = 1'000'000'007LL;

constexpr f64 EPS = 1e-12;

constexpr f64 PI = 3.14159265358979323846;

// util {{{
#define FOR(i, start, end) for(i64 i = (start), CPP_CAT(i,xxxx_end)=(end); i < CPP_CAT(i,xxxx_end); ++i)
#define REP(i, n) FOR(i, 0, n)

#define ALL(f,c,...) (([&](decltype((c)) cccc) { return (f)(std::begin(cccc), std::end(cccc), ## __VA_ARGS__); })(c))
#define SLICE(f,c,l,r,...) (([&](decltype((c)) cccc, decltype((l)) llll, decltype((r)) rrrr) {\
    auto iiii = llll <= rrrr ? std::begin(cccc)+llll : std::end(cccc);\
    auto jjjj = llll <= rrrr ? std::begin(cccc)+rrrr : std::end(cccc);\
    return (f)(iiii, jjjj, ## __VA_ARGS__);\
})(c,l,r))

#define GENERIC(f) ([](auto&&... args) -> decltype(auto) { return (f)(std::forward<decltype(args)>(args)...); })

template<typename T1, typename T2, typename Comp=less<>,
         SFINAE(
             is_integral<T1>::value &&
             is_integral<T2>::value &&
             is_signed<T1>::value != is_unsigned<T2>::value
         )>
common_type_t<T1,T2> MAX(T1 x, T2 y, Comp comp={}) {
    return max<common_type_t<T1,T2>>(x, y, comp);
}

template<typename T1, typename T2, typename Comp=less<>,
         SFINAE(
             is_floating_point<T1>::value &&
             is_floating_point<T2>::value
         )>
common_type_t<T1,T2> MAX(T1 x, T2 y, Comp comp={}) {
    return max<common_type_t<T1,T2>>(x, y, comp);
}

template<typename T, typename Comp=less<>>
const T& MAX(const T& x, const T& y, Comp comp={}) {
    return max(x, y, comp);
}

template<typename T, typename Comp=less<>>
T MAX(initializer_list<T> ilist, Comp comp={}) {
    return max(ilist, comp);
}

template<typename T1, typename T2, typename Comp=less<>,
         SFINAE(
             is_integral<T1>::value &&
             is_integral<T2>::value &&
             is_signed<T1>::value != is_unsigned<T2>::value
         )>
common_type_t<T1,T2> MIN(T1 x, T2 y, Comp comp={}) {
    return min<common_type_t<T1,T2>>(x, y, comp);
}

template<typename T1, typename T2, typename Comp=less<>,
         SFINAE(
             is_floating_point<T1>::value &&
             is_floating_point<T2>::value
         )>
common_type_t<T1,T2> MIN(T1 x, T2 y, Comp comp={}) {
    return min<common_type_t<T1,T2>>(x, y, comp);
}

template<typename T, typename Comp=less<>>
const T& MIN(const T& x, const T& y, Comp comp={}) {
    return min(x, y, comp);
}

template<typename T, typename Comp=less<>>
T MIN(initializer_list<T> ilist, Comp comp={}) {
    return min(ilist, comp);
}

template<typename T1, typename T2, typename T3, typename Comp=less<>, SFINAE(
    is_integral<T1>::value &&
    is_integral<T2>::value &&
    is_integral<T3>::value &&
    is_signed<T1>::value != is_unsigned<T2>::value &&
    is_signed<T2>::value != is_unsigned<T3>::value
)>
common_type_t<T1,T2,T3> CLAMP(T1 x, T2 xmin, T3 xmax, Comp comp={}) {
    ASSERT(!comp(xmax, xmin));
    if(comp(x, xmin)) return xmin;
    if(comp(xmax, x)) return xmax;
    return x;
}

template<typename T1, typename T2, typename T3, typename Comp=less<>, SFINAE(
    is_floating_point<T1>::value &&
    is_floating_point<T2>::value &&
    is_floating_point<T3>::value
)>
common_type_t<T1,T2,T3> CLAMP(T1 x, T2 xmin, T3 xmax, Comp comp={}) {
    ASSERT(!comp(xmax, xmin));
    if(comp(x, xmin)) return xmin;
    if(comp(xmax, x)) return xmax;
    return x;
}

template<typename T, typename Comp=less<>>
const T& CLAMP(const T& x, const T& xmin, const T& xmax, Comp comp={}) {
    ASSERT(!comp(xmax, xmin));
    if(comp(x, xmin)) return xmin;
    if(comp(xmax, x)) return xmax;
    return x;
}

template<typename T>
T ABS(T x) {
    static_assert(is_signed<T>::value, "ABS(): argument must be signed");
    return x < 0 ? -x : x;
}

f64 ROUND(f64 x) {
    return round(x);
}

i64 IROUND(f64 x) {
    return llround(x);
}

template<typename C>
i64 SIZE(const C& c) { return static_cast<i64>(c.size()); }

template<typename T, size_t N>
i64 SIZE(const T (&)[N]) { return static_cast<i64>(N); }

bool is_odd (i64 x) { return x % 2 != 0; }
bool is_even(i64 x) { return x % 2 == 0; }

template<typename T> i64 cmp(T x, T y) { return (y<x) - (x<y); }
template<typename T> i64 sgn(T x) { return cmp(x, T(0)); }

// 事前条件: a >= 0, b >= 0
i64 gcd_impl(i64 a, i64 b) {
    if(b == 0) return a;
    return gcd_impl(b, a%b);
}

// GCD(0,0) = 0
i64 GCD(i64 a, i64 b) {
    return gcd_impl(ABS(a), ABS(b));
}

// LCM(0,x) は未定義
i64 LCM(i64 a, i64 b) {
    ASSERT(a != 0 && b != 0);
    a = ABS(a);
    b = ABS(b);
    return a / gcd_impl(a,b) * b;
}

// lo:OK, hi:NG
template<typename Pred>
i64 bisect_integer(i64 lo, i64 hi, Pred pred) {
    ASSERT(lo < hi);

    while(lo+1 < hi) {
        i64 mid = (lo+hi) / 2;
        if(pred(mid))
            lo = mid;
        else
            hi = mid;
    }
    return lo;
}

template<typename Pred>
f64 bisect_real(f64 lo, f64 hi, Pred pred, i64 iter=100) {
    ASSERT(lo < hi);

    REP(_, iter) {
        f64 mid = (lo+hi) / 2;
        if(pred(mid))
            lo = mid;
        else
            hi = mid;
    }
    return lo;
}

i64 ipow(i64 x, i64 e) {
    ASSERT(e >= 0);
    i64 res = 1;
    REP(_, e) {
        res *= x;
    }
    return res;
}

i64 sqrt_floor(i64 x) {
    ASSERT(x >= 0);

    i64 lo = 0;
    i64 hi = MIN(x/2+2, 3037000500LL);
    return bisect_integer(lo, hi, [x](i64 r) { return r*r <= x; });
}

i64 sqrt_ceil(i64 x) {
    i64 r = sqrt_floor(x);
    return r*r == x ? r : r+1;
}

// 0 <= log10_ceil(x) <= 19
i64 log10_ceil(i64 x) {
    ASSERT(x > 0);
    static constexpr i64 TABLE[19] {
        1LL,
        10LL,
        100LL,
        1000LL,
        10000LL,
        100000LL,
        1000000LL,
        10000000LL,
        100000000LL,
        1000000000LL,
        10000000000LL,
        100000000000LL,
        1000000000000LL,
        10000000000000LL,
        100000000000000LL,
        1000000000000000LL,
        10000000000000000LL,
        100000000000000000LL,
        1000000000000000000LL,
    };
    REP(i, SIZE(TABLE)) {
        if(x <= TABLE[i]) return i;
    }
    return SIZE(TABLE);
}

// 0 <= log10_floor(x) <= 18
i64 log10_floor(i64 x) {
    ASSERT(x > 0);
    static constexpr i64 TABLE[18] {
        9LL,
        99LL,
        999LL,
        9999LL,
        99999LL,
        999999LL,
        9999999LL,
        99999999LL,
        999999999LL,
        9999999999LL,
        99999999999LL,
        999999999999LL,
        9999999999999LL,
        99999999999999LL,
        999999999999999LL,
        9999999999999999LL,
        99999999999999999LL,
        999999999999999999LL,
    };
    REP(i, SIZE(TABLE)) {
        if(x <= TABLE[i]) return i;
    }
    return SIZE(TABLE);
}

// 2^n - 1 の形かどうか
bool is_mersenne(i64 x) {
    ASSERT(x >= 0);
    return (x&(x+1)) == 0;
}

bool is_pow2(i64 x) {
    ASSERT(x > 0);
    return (x&(x-1)) == 0;
}

// Haskell の divMod と同じ
pair<i64,i64> divmod(i64 a, i64 b) {
    i64 q = a / b;
    i64 r = a % b;
    if((b>0 && r<0) || (b<0 && r>0)) {
        --q;
        r += b;
    }
    return {q,r};
}

i64 div_ceil(i64 a, i64 b) {
    i64 q = a / b;
    i64 r = a % b;
    if((b>0 && r>0) || (b<0 && r<0))
        ++q;
    return q;
}

i64 div_floor(i64 a, i64 b) {
    return divmod(a,b).first;
}

i64 modulo(i64 a, i64 b) {
    return divmod(a,b).second;
}

// x を align の倍数に切り上げる
i64 align_ceil(i64 x, i64 align) {
    ASSERT(align > 0);
    return div_ceil(x,align) * align;
}

// x を align の倍数に切り下げる
i64 align_floor(i64 x, i64 align) {
    ASSERT(align > 0);
    return div_floor(x,align) * align;
}

bool feq(f64 x, f64 y, f64 eps=EPS) {
    return fabs(x-y) < eps;
}

template<typename T, typename U, typename Comp=less<>>
bool chmax(T& xmax, const U& x, Comp comp={}) {
    if(comp(xmax, x)) {
        xmax = x;
        return true;
    }
    return false;
}

template<typename T, typename U, typename Comp=less<>>
bool chmin(T& xmin, const U& x, Comp comp={}) {
    if(comp(x, xmin)) {
        xmin = x;
        return true;
    }
    return false;
}

template<typename Pred>
i64 arg_find(i64 lo, i64 hi, Pred pred) {
    ASSERT(lo < hi);

    FOR(x, lo, hi) {
        if(pred(x)) return x;
    }
    return INF;
}

template<typename F>
i64 arg_max(i64 lo, i64 hi, F f) {
    ASSERT(lo < hi);

    i64 res = lo;
    auto ymax = f(lo);
    FOR(x, lo+1, hi) {
        if(chmax(ymax, f(x)))
            res = x;
    }
    return res;
}

template<typename F>
i64 arg_min(i64 lo, i64 hi, F f) {
    ASSERT(lo < hi);

    i64 res = lo;
    auto ymin = f(lo);
    FOR(x, lo+1, hi) {
        if(chmin(ymin, f(x)))
            res = x;
    }
    return res;
}

template<typename Pred>
i64 arg_find_r(i64 lo, i64 hi, Pred pred) {
    i64 x = arg_find(-hi+1, lo+1, [pred](i64 xx) { return pred(-xx); });
    return x == INF ? INF : -x;
}

template<typename F>
i64 arg_max_r(i64 lo, i64 hi, F f) {
    return -arg_max(-hi+1, lo+1, [f](i64 x) { return f(-x); });
}

template<typename F>
i64 arg_min_r(i64 lo, i64 hi, F f) {
    return -arg_min(-hi+1, lo+1, [f](i64 x) { return f(-x); });
}

template<typename ForwardIt, typename T, typename Comp=less<>>
ForwardIt bsearch_find(ForwardIt first, ForwardIt last, const T& x, Comp comp={}) {
    auto it = lower_bound(first, last, x, comp);
    if(it == last || comp(x,*it)) return last;
    return it;
}

// x 未満の最後の要素
template<typename BidiIt, typename T, typename Comp=less<>>
BidiIt bsearch_lt(BidiIt first, BidiIt last, const T& x, Comp comp={}) {
    auto it = lower_bound(first, last, x, comp);
    if(it == first) return last;
    return prev(it);
}

// x 以下の最後の要素
template<typename BidiIt, typename T, typename Comp=less<>>
BidiIt bsearch_le(BidiIt first, BidiIt last, const T& x, Comp comp={}) {
    auto it = upper_bound(first, last, x, comp);
    if(it == first) return last;
    return prev(it);
}

// x より大きい最初の要素
template<typename BidiIt, typename T, typename Comp=less<>>
BidiIt bsearch_gt(BidiIt first, BidiIt last, const T& x, Comp comp={}) {
    return upper_bound(first, last, x, comp);
}

// x 以上の最初の要素
template<typename BidiIt, typename T, typename Comp=less<>>
BidiIt bsearch_ge(BidiIt first, BidiIt last, const T& x, Comp comp={}) {
    return lower_bound(first, last, x, comp);
}

template<typename InputIt, typename BinaryOp>
auto FOLD(InputIt first, InputIt last,
          typename iterator_traits<InputIt>::value_type init,
          BinaryOp op)
{
    for(; first != last; ++first)
        init = op(move(init), *first);
    return init;
}

template<typename InputIt, typename BinaryOp>
auto FOLD1(InputIt first, InputIt last, BinaryOp op) {
    auto init = *first++;
    return FOLD(first, last, init, op);
}

template<typename InputIt>
auto SUM(InputIt first, InputIt last) {
    using T = typename iterator_traits<InputIt>::value_type;
    return accumulate(first, last, T());
}

template<typename ForwardIt, typename UnaryOperation>
ForwardIt transform_self(ForwardIt first, ForwardIt last, UnaryOperation op) {
    return transform(first, last, first, op);
}

template<typename C>
void UNIQ(C& c) {
    c.erase(ALL(unique,c), end(c));
}

template<typename BinaryFunc>
auto FLIP(BinaryFunc f) {
    return [f](const auto& x, const auto& y) {
        return f(y,x);
    };
}

template<typename BinaryFunc, typename UnaryFunc>
auto ON(BinaryFunc bf, UnaryFunc uf) {
    return [bf,uf](const auto& x, const auto& y) {
        return bf(uf(x), uf(y));
    };
}

template<typename F>
auto LT_ON(F f) { return ON(less<>(), f); }

template<typename F>
auto GT_ON(F f) { return ON(greater<>(), f); }

template<typename F>
auto EQ_ON(F f) { return ON(equal_to<>(), f); }

template<typename F>
auto NE_ON(F f) { return ON(not_equal_to<>(), f); }

template<typename Comp=less<>>
auto EQUIV(Comp comp={}) {
    return [comp](const auto& lhs, const auto& rhs) {
        return !comp(lhs,rhs) && !comp(rhs,lhs);
    };
}

template<typename T=void>
struct OpMax {
    using result_type          = T;
    using first_argument_type  = T;
    using second_argument_type = T;
    T operator()(const T& x, const T& y) const {
        return MAX(x, y);
    }
};

template<>
struct OpMax<void> {
    using is_transparent = void;
    template<typename T1, typename T2>
    auto operator()(T1&& x, T2&& y) const {
        return MAX(forward<T1>(x), forward<T2>(y));
    }
};

template<typename T=void>
struct OpMin {
    using result_type          = T;
    using first_argument_type  = T;
    using second_argument_type = T;
    T operator()(const T& x, const T& y) const {
        return MIN(x, y);
    }
};

template<>
struct OpMin<void> {
    using is_transparent = void;
    template<typename T1, typename T2>
    auto operator()(T1&& x, T2&& y) const {
        return MIN(forward<T1>(x), forward<T2>(y));
    }
};

template<typename T=void>
struct OpGcd {
    using result_type          = T;
    using first_argument_type  = T;
    using second_argument_type = T;
    T operator()(const T& x, const T& y) const {
        return GCD(x, y);
    }
};

template<>
struct OpGcd<void> {
    using is_transparent = void;
    template<typename T1, typename T2>
    auto operator()(T1&& x, T2&& y) const {
        return GCD(forward<T1>(x), forward<T2>(y));
    }
};

template<typename T=void>
struct OpLcm {
    using result_type          = T;
    using first_argument_type  = T;
    using second_argument_type = T;
    T operator()(const T& x, const T& y) const {
        return LCM(x, y);
    }
};

template<>
struct OpLcm<void> {
    using is_transparent = void;
    template<typename T1, typename T2>
    auto operator()(T1&& x, T2&& y) const {
        return LCM(forward<T1>(x), forward<T2>(y));
    }
};

template<typename ForwardIt>
ForwardIt next_bounded(ForwardIt last, ForwardIt it, i64 n=1) {
    auto bound = distance(it, last);
    return next(it, MIN(n, bound));
}

template<typename ForwardIt>
ForwardIt prev_bounded(ForwardIt first, ForwardIt it, i64 n=1) {
    auto bound = distance(first, it);
    return prev(it, MIN(n, bound));
}

template<typename ForwardIt>
void advance_bounded(ForwardIt first, ForwardIt last, ForwardIt& it, i64 n) {
    if(n > 0) {
        auto bound = distance(it, last);
        advance(it, MIN(n, bound));
    }
    else if(n < 0) {
        auto bound = distance(it, first);
        advance(it, MAX(n, bound));
    }
}

char digit_chr(i64 n) {
    return static_cast<char>('0' + n);
}

i64 digit_ord(char c) {
    return c - '0';
}

char lower_chr(i64 n) {
    return static_cast<char>('a' + n);
}

i64 lower_ord(char c) {
    return c - 'a';
}

char upper_chr(i64 n) {
    return static_cast<char>('A' + n);
}

i64 upper_ord(char c) {
    return c - 'A';
}

// 出力は operator<< を直接使わず、このテンプレート経由で行う
// 提出用出力とデバッグ用出力を分けるため
template<typename T, typename Enable=void>
struct Formatter {
    static ostream& write_str(ostream& out, const T& x)  { return out << x; }
    static ostream& write_repr(ostream& out, const T& x) { return out << x; }
};

template<typename T>
ostream& WRITE_STR(ostream& out, const T& x) {
    return Formatter<T>::write_str(out, x);
}

template<typename T>
ostream& WRITE_REPR(ostream& out, const T& x) {
    return Formatter<T>::write_repr(out, x);
}

template<typename InputIt>
ostream& WRITE_JOIN_STR(ostream& out, InputIt first, InputIt last, const string& sep) {
    while(first != last) {
        WRITE_STR(out, *first++);
        if(first != last)
            out << sep;
    }
    return out;
}

template<typename InputIt>
ostream& WRITE_JOIN_REPR(ostream& out, InputIt first, InputIt last, const string& sep) {
    while(first != last) {
        WRITE_REPR(out, *first++);
        if(first != last)
            out << sep;
    }
    return out;
}

template<typename InputIt>
ostream& WRITE_RANGE_STR(ostream& out, InputIt first, InputIt last) {
    return WRITE_JOIN_STR(out, first, last, " ");
}

template<typename InputIt>
ostream& WRITE_RANGE_REPR(ostream& out, InputIt first, InputIt last) {
    out << "[";
    WRITE_JOIN_REPR(out, first, last, ", ");
    out << "]";
    return out;
}

template<typename T>
void FROM_STR(const string& s, T& x) {
    istringstream in(s);
    in >> x;
}

template<typename T>
string TO_STR(const T& x) {
    ostringstream out;
    WRITE_STR(out, x);
    return out.str();
}

template<typename T>
string TO_REPR(const T& x) {
    ostringstream out;
    WRITE_REPR(out, x);
    return out.str();
}

template<typename InputIt>
string RANGE_TO_STR(InputIt first, InputIt last) {
    ostringstream out;
    WRITE_RANGE_STR(out, first, last);
    return out.str();
}

template<typename InputIt>
string RANGE_TO_REPR(InputIt first, InputIt last) {
    ostringstream out;
    WRITE_RANGE_REPR(out, first, last);
    return out.str();
}

template<typename InputIt>
string JOIN(InputIt first, InputIt last, const string& sep) {
    ostringstream out;
    WRITE_JOIN_STR(out, first, last, sep);
    return out.str();
}

template<>
struct Formatter<i64> {
    static ostream& write_str(ostream& out, i64 x) {
        return out << x;
    }
    static ostream& write_repr(ostream& out, i64 x) {
        if(x == INF) return out << "INF";
        if(x == -INF) return out << "-INF";
        return out << x;
    }
};

template<>
struct Formatter<f64> {
    static ostream& write_str(ostream& out, f64 x) {
        return out << x;
    }
    static ostream& write_repr(ostream& out, f64 x) {
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wfloat-equal"
        if(x == FINF) return out << "FINF";
        if(x == -FINF) return out << "-FINF";
#pragma GCC diagnostic pop
        return out << x;
    }
};

template<typename Enum>
struct Formatter<Enum, enable_if_t<is_enum<Enum>::value>> {
    static ostream& write_str(ostream& out, Enum x) {
        return WRITE_STR(out, static_cast<underlying_type_t<Enum>>(x));
    }
    static ostream& write_repr(ostream& out, Enum x) {
        return WRITE_REPR(out, static_cast<underlying_type_t<Enum>>(x));
    }
};

template<typename T>
struct Formatter<vector<T>> {
    static ostream& write_str(ostream& out, const vector<T>& v) {
        return WRITE_RANGE_STR(out, begin(v), end(v));
    }
    static ostream& write_repr(ostream& out, const vector<T>& v) {
        out << "vector";
        return WRITE_RANGE_REPR(out, begin(v), end(v));
    }
};

template<typename T>
void RD(T& x) {
    cin >> x;
#ifdef PROCON_LOCAL
    ASSERT(cin);
#endif
}

template<typename T>
void RD1(T& x) {
    RD(x);
    --x;
}

void PRINT() {}

template<typename T, typename... TS>
void PRINT(const T& x, const TS& ...args) {
    WRITE_STR(cout, x);
    if(sizeof...(args)) {
        cout << ' ';
        PRINT(args...);
    }
}

template<typename... TS>
void PRINTLN(const TS& ...args) {
    PRINT(args...);
    cout << '\n';
}

[[noreturn]] void EXIT() {
    cout.flush();
#ifdef PROCON_LOCAL
    cerr.flush();
    exit(0);
#else
    _Exit(0);
#endif
}

template<typename... TS, SFINAE(sizeof...(TS) == 1)>
void DBG_IMPL(i64 line, const char* expr, const tuple<TS...>& value) {
    cerr << "[L " << line << "]: ";
    cerr << expr << " = ";
    WRITE_REPR(cerr, get<0>(value));
    cerr << "\n";
}

template<typename... TS, SFINAE(sizeof...(TS) >= 2)>
void DBG_IMPL(i64 line, const char* expr, const tuple<TS...>& value) {
    cerr << "[L " << line << "]: ";
    cerr << "(" << expr << ") = ";
    WRITE_REPR(cerr, value);
    cerr << "\n";
}

template<typename T, size_t N>
void DBG_CARRAY_IMPL(i64 line, const char* expr, const T (&ary)[N]) {
    cerr << "[L " << line << "]: ";
    cerr << expr << " = ";
    WRITE_RANGE_REPR(cerr, begin(ary), end(ary));
    cerr << "\n";
}

template<typename InputIt>
void DBG_RANGE_IMPL(i64 line, const char* expr1, const char* expr2, InputIt first, InputIt last) {
    cerr << "[L " << line << "]: ";
    cerr << expr1 << "," << expr2 << " = ";
    WRITE_RANGE_REPR(cerr, first, last);
    cerr << "\n";
}

#ifdef PROCON_LOCAL
    #define DBG(args...) DBG_IMPL(__LINE__, CPP_STR_I(args), std::make_tuple(args))
    #define DBG_CARRAY(expr) DBG_CARRAY_IMPL(__LINE__, CPP_STR(expr), (expr))
    #define DBG_RANGE(first,last) DBG_RANGE_IMPL(__LINE__, CPP_STR(first), CPP_STR(last), (first), (last))
#else
    #define DBG(args...)
    #define DBG_CARRAY(expr)
    #define DBG_RANGE(first,last)
#endif

#define PAIR  make_pair
#define TUPLE make_tuple

[[noreturn]] void PROCON_MLE(size_t size=1U<<31) {
    static constexpr size_t PAGE_SIZE = 4096;
    char* buf = new char[size];
    for(size_t i = 0; i < size; i += PAGE_SIZE)
        buf[i] = static_cast<char>(i);
    EXIT();
}

[[noreturn]] void PROCON_OLE() {
    static constexpr char BUF[8192] {};
    for(;;)
        cout.write(BUF, SIZE(BUF));
}

[[noreturn]] void PROCON_RE() {
    abort();
}

[[noreturn]] void PROCON_TLE() {
    this_thread::sleep_for(chrono::hours(10000));
    EXIT();
}

[[noreturn]] void PROCON_WA() {
    static constexpr char BUF[256] {
        '\xd1', '\x14', '\xe3', '\xee', '\x3c', '\x37', '\x82', '\x11',
        '\x3f', '\xa7', '\x2a', '\x89', '\xbb', '\x62', '\xad', '\xfc',
        '\xcd', '\x79', '\xfe', '\x0e', '\x0f', '\xe9', '\xdc', '\x23',
        '\x8e', '\x96', '\x7a', '\x5a', '\xfa', '\x56', '\xeb', '\xb9',
        '\xf4', '\xb1', '\x88', '\xe8', '\x05', '\x68', '\x13', '\xd8',
        '\x77', '\x31', '\xc4', '\x64', '\xcc', '\x85', '\x92', '\x22',
        '\xa2', '\xbe', '\x54', '\xfd', '\x3d', '\xce', '\x9a', '\xe2',
        '\x36', '\x47', '\xa9', '\x9d', '\x24', '\x58', '\x2f', '\x1c',
        '\x4f', '\x7b', '\x99', '\xf6', '\x76', '\x70', '\x93', '\x4d',
        '\x6b', '\xc5', '\xc2', '\x4c', '\xd3', '\x86', '\x8d', '\x0d',
        '\x5d', '\x20', '\x3b', '\x4e', '\x8f', '\xa0', '\x98', '\x57',
        '\x9b', '\x6d', '\xb0', '\x12', '\xcf', '\x69', '\x66', '\x27',
        '\x4a', '\x53', '\x60', '\x67', '\x78', '\x87', '\x59', '\xa1',
        '\x43', '\x1b', '\xb5', '\xd4', '\x72', '\x97', '\x34', '\x30',
        '\x06', '\xe0', '\x95', '\x02', '\xbd', '\xd6', '\xf5', '\xc8',
        '\x91', '\x10', '\x90', '\x63', '\x5e', '\x5f', '\xfb', '\xff',
        '\x94', '\x2e', '\xc7', '\xb6', '\xae', '\x50', '\xaa', '\x44',
        '\x0b', '\x6f', '\xc9', '\x83', '\x32', '\x81', '\xb4', '\x2b',
        '\xc6', '\x7c', '\x0a', '\x42', '\x28', '\xb3', '\x48', '\x35',
        '\xea', '\xf3', '\x04', '\x01', '\xf8', '\x08', '\x4b', '\xe5',
        '\xed', '\x49', '\x9f', '\xba', '\x26', '\x29', '\x71', '\xa6',
        '\x09', '\x9c', '\xbc', '\x38', '\xe7', '\x07', '\x8b', '\x1f',
        '\x75', '\xec', '\x1d', '\x1a', '\x7e', '\xa8', '\x8c', '\xd7',
        '\xdb', '\x2d', '\xef', '\x9e', '\xf0', '\xdf', '\x40', '\xb7',
        '\x21', '\x5b', '\xd5', '\x15', '\x45', '\x19', '\x03', '\x7d',
        '\x1e', '\x5c', '\xc3', '\xd9', '\x52', '\xca', '\xda', '\xac',
        '\x80', '\xf2', '\xc0', '\xa4', '\x6a', '\x18', '\x65', '\xb8',
        '\x55', '\x61', '\xab', '\xe6', '\xcb', '\x84', '\xd2', '\xe4',
        '\xbf', '\xdd', '\xb2', '\xe1', '\x16', '\xf9', '\xa3', '\x74',
        '\x0c', '\xde', '\xa5', '\x3a', '\xaf', '\xc1', '\xf1', '\x8a',
        '\x73', '\x51', '\xf7', '\x46', '\x41', '\x25', '\x7f', '\x17',
        '\x00', '\x39', '\x2c', '\xd0', '\x6c', '\x3e', '\x6e', '\x33',
    };
    cout.write(BUF, SIZE(BUF));
    EXIT();
}
// }}}

// init {{{
struct ProconInit {
    static constexpr int IOS_PREC = 15;
    static constexpr bool AUTOFLUSH = false;

    ProconInit() {
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(IOS_PREC);
#ifdef PROCON_LOCAL
        cerr << fixed << setprecision(IOS_PREC);
#endif
        if(AUTOFLUSH)
            cout << unitbuf;
    }
} PROCON_INIT;
// }}}

//--------------------------------------------------------------------

tuple<bool,vector<i64>> graph_tsort(const vector<vector<i64>>& g) {
    i64 n = SIZE(g);
    vector<i64> res;
    res.reserve(n);

    vector<i64> deg_in(n, 0);
    for(const auto& tos : g)
        for(auto to : tos)
            ++deg_in[to];

    queue<i64> que;
    REP(v, n) {
        if(deg_in[v] == 0)
            que.emplace(v);
    }

    while(!que.empty()) {
        i64 v = que.front(); que.pop();

        res.emplace_back(v);

        for(auto to : g[v]) {
            if(--deg_in[to] > 0) continue;
            que.emplace(to);
        }
    }

    bool ok = SIZE(res) == n;
    return make_tuple(ok, res);
}

void solve() {
    i64 N; RD(N);
    i64 M; RD(M);

    vector<vector<i64>> G(N);
    REP(_, M) {
        i64 from,to; RD(from); RD(to);
        G[from].emplace_back(to);
    }

    bool ok;
    vector<i64> ans;
    tie(ok,ans) = graph_tsort(G);
    assert(ok);

    ALL(for_each, ans, GENERIC(PRINTLN));

    // * 小さいケースで試した?
    // * 不可能なケースはチェックした?
    // * MOD はとった?
    // * メモ化忘れてない?
    // * 入出力の 0-based/1-based 確認した?
    // * 時間/メモリ制限は確認した?
    // * 違うやつ提出してない?
    // * 違うやつテストしてない?
}

signed main() {
    

    solve();

    EXIT();
}



Measured memory_bytes: 3920