#define USE_AC_LIBRARY

#ifndef USE_AC_LIBRARY
#include <bits/stdc++.h>
#elif defined(ONLINE_JUDGE)
#include <bits/stdc++.h>

#include <atcoder/all>
#else
#include <precompile.hpp>
#endif

using namespace std;
using ll = long long;
using uint = unsigned int;
using ull = unsigned long long;

namespace atcoder {};
using namespace atcoder;

// for suisen-cp/cp-library-cpp
namespace suisen {};
using namespace suisen;

#ifdef ATCODER_MODINT_HPP
using mint = modint998244353;
#endif

#define rep_kind(a, b, c, d, e, ...) e
#define rep1(i, r) for (int i = 0; i < (int)(r); ++i)
#define rep2(i, l, r) for (int i = (l); i < (int)(r); ++i)
#define rep3(i, l, r, d) for (int i = (l); i < (int)(r); i += (d))
#define rep_r1(i, r) for (int i = (r) - 1; i >= 0; --i)
#define rep_r2(i, l, r) for (int i = (r) - 1; i >= (l); --i)
#define rep_r3(i, l, r, d) for (int i = (r) - 1; i >= (l); i -= (d))
#define rep(...) rep_kind(__VA_ARGS__, rep3, rep2, rep1)(__VA_ARGS__)
#define rep_r(...) rep_kind(__VA_ARGS__, rep_r3, rep_r2, rep_r1)(__VA_ARGS__)

#define rep_t_kind(a, b, c, d, e, f, ...) f
#define rep_t1(type, i, r) for (type i = 0; i < (type)(r); ++i)
#define rep_t2(type, i, l, r) for (type i = (l); i < (type)(r); ++i)
#define rep_t3(type, i, l, r, d) for (type i = (l); i < (type)(r); i += (d))
#define rep_t_r1(type, i, r) for (type i = (r) - 1; i >= 0; --i)
#define rep_t_r2(type, i, l, r) for (type i = (r) - 1; i >= (l); --i)
#define rep_t_r3(type, i, l, r, d) for (type i = (r) - 1; i >= (l); i -= (d))
#define rep_t(...) rep_t_kind(__VA_ARGS__, rep_t3, rep_t2, rep_t1)(__VA_ARGS__)
#define rep_t_r(...) \
    rep_t_kind(__VA_ARGS__, rep_t_r3, rep_t_r2, rep_t_r1)(__VA_ARGS__)

#define do_while_kind(a, b, c, ...) c
#define do_while1(cond) \
    for (bool is_first = true; is_first || (cond); is_first = false)
#define do_while2(cond, is_first) \
    for (bool is_first = true; is_first || (cond); is_first = false)
#define do_while(...) \
    do_while_kind(__VA_ARGS__, do_while2, do_while1)(__VA_ARGS__)

#ifdef ATCODER_MODINT_HPP
template <int M> istream &operator>>(istream &is, static_modint<M> &x) {
    ll val;
    is >> val;
    x = val;
    return is;
}
template <int M> ostream &operator<<(ostream &os, const static_modint<M> &x) {
    os << x.val();
    return os;
}

template <int id> istream &operator>>(istream &is, dynamic_modint<id> &x) {
    ll val;
    is >> val;
    x = val;
    return is;
}
template <int id>
ostream &operator<<(ostream &os, const dynamic_modint<id> &x) {
    os << x.val();
    return os;
}
#endif

inline int slot_index() {
    static int idx = ios_base::xalloc();
    return idx;
}
struct separator {
    string s;
};
inline separator sep(string s) { return {std::move(s)}; }
inline void cleanup(ios_base::event ev, ios_base &ios, int idx) {
    void *&slot = ios.pword(idx);
    if (ev == ios_base::erase_event) {
        delete static_cast<string *>(slot);
        slot = nullptr;
    } else if (ev == ios_base::copyfmt_event) {
        if (auto *p = static_cast<string *>(slot); p) {
            slot = new string(*p);
        }
    }
}
inline ostream &operator<<(ostream &os, const separator &m) {
    void *&slot = os.pword(slot_index());
    if (!slot) {
        slot = new string(m.s);
        os.register_callback(&cleanup, slot_index());
    } else {
        *static_cast<string *>(slot) = m.s;
    }
    return os;
}
inline const char *current_sep(ios_base &ios) {
    if (auto p = static_cast<string *>(ios.pword(slot_index())); p) {
        return p->c_str();
    }
    return " ";
}

template <class T>
concept char_range =
    ranges::input_range<T> && same_as<ranges::range_value_t<T>, char>;
template <class T>
concept nonstring_range =
    ranges::input_range<T> &&
    !is_convertible_v<remove_cvref_t<T>, string_view> && !char_range<T>;
template <class R>
concept writable_lvalue_range =
    is_lvalue_reference_v<ranges::range_reference_t<R>> &&
    !is_const_v<remove_reference_t<ranges::range_reference_t<R>>>;
template <class R>
concept proxy_writable_range =
    !is_lvalue_reference_v<ranges::range_reference_t<R>> &&
    !same_as<remove_cvref_t<ranges::range_reference_t<R>>,
             ranges::range_value_t<R>> &&
    default_initializable<ranges::range_value_t<R>> &&
    requires(ranges::range_reference_t<R> e, ranges::range_value_t<R> v) {
        e = std::move(v);
    };
template <class R>
concept inputtable_nonstring_range =
    nonstring_range<R> && (writable_lvalue_range<R> || proxy_writable_range<R>);

namespace io_detail {
template <class T>
concept tuple_like = requires { typename tuple_size<remove_cvref_t<T>>::type; };

template <class T> void read(istream &is, T &x);
template <class T> void write(ostream &os, T &&x);

template <class Tuple, class F> void for_each_tuple_element(Tuple &&t, F &&f) {
    [&]<size_t... I>(index_sequence<I...>) {
        using std::get;
        (f(get<I>(std::forward<Tuple>(t))), ...);
    }(make_index_sequence<tuple_size_v<remove_cvref_t<Tuple>>>{});
}

template <class T> void read(istream &is, T &x) {
    if constexpr (inputtable_nonstring_range<T>) {
        for (auto &&e : x) {
            if constexpr (writable_lvalue_range<T>) {
                read(is, e);
            } else {
                ranges::range_value_t<T> v{};
                read(is, v);
                e = std::move(v);
            }
        }
    } else if constexpr (tuple_like<T>) {
        for_each_tuple_element(x, [&](auto &e) { read(is, e); });
    } else {
        is >> x;
    }
}

template <class T> void write(ostream &os, T &&x) {
    if constexpr (nonstring_range<T>) {
        bool is_first = true;
        for (auto &&e : x) {
            if (is_first) {
                is_first = false;
            } else {
                os << current_sep(os);
            }
            write(os, std::forward<decltype(e)>(e));
        }
    } else if constexpr (tuple_like<T>) {
        bool is_first = true;
        for_each_tuple_element(std::forward<T>(x), [&](auto &&e) {
            if (is_first) {
                is_first = false;
            } else {
                os << current_sep(os);
            }
            write(os, std::forward<decltype(e)>(e));
        });
    } else {
        os << std::forward<T>(x);
    }
}
} // namespace io_detail

template <class T1, class T2>
istream &operator>>(istream &is, pair<T1, T2> &p) {
    io_detail::read(is, p);
    return is;
}
template <class T1, class T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p) {
    io_detail::write(os, p);
    return os;
}

template <class... Ts> istream &operator>>(istream &is, tuple<Ts...> &t) {
    io_detail::read(is, t);
    return is;
}
template <class... Ts> ostream &operator<<(ostream &os, const tuple<Ts...> &t) {
    io_detail::write(os, t);
    return os;
}

template <inputtable_nonstring_range T> istream &operator>>(istream &is, T &r) {
    io_detail::read(is, r);
    return is;
}
template <nonstring_range T> ostream &operator<<(ostream &os, T &&r) {
    io_detail::write(os, std::forward<T>(r));
    return os;
}

namespace incdec_detail {
template <class> inline constexpr bool always_false_v = false;

template <class T>
concept pre_incrementable = requires(T &x) { ++x; };
template <class T>
concept pre_decrementable = requires(T &x) { --x; };
template <class T>
concept tuple_like = requires { typename tuple_size<remove_cvref_t<T>>::type; };

template <class R>
concept mutable_lvalue_range =
    ranges::input_range<R> &&
    is_lvalue_reference_v<ranges::range_reference_t<R>> &&
    !is_const_v<remove_reference_t<ranges::range_reference_t<R>>>;
template <class R>
concept mutable_proxy_range =
    ranges::input_range<R> &&
    !is_lvalue_reference_v<ranges::range_reference_t<R>> &&
    !same_as<remove_cvref_t<ranges::range_reference_t<R>>,
             ranges::range_value_t<R>> &&
    constructible_from<ranges::range_value_t<R>,
                       ranges::range_reference_t<R>> &&
    requires(ranges::range_reference_t<R> e, ranges::range_value_t<R> v) {
        e = std::move(v);
    };

template <class T> void increment_impl(T &x);
template <class T> void decrement_impl(T &x);

template <class Tuple, class F> void for_each_tuple_element(Tuple &t, F &&f) {
    [&]<size_t... I>(index_sequence<I...>) {
        using std::get;
        (f(get<I>(t)), ...);
    }(make_index_sequence<tuple_size_v<remove_cvref_t<Tuple>>>{});
}

template <class T> void increment_impl(T &x) {
    if constexpr (mutable_lvalue_range<T>) {
        for (auto &&e : x) {
            increment_impl(e);
        }
    } else if constexpr (mutable_proxy_range<T>) {
        for (auto &&e : x) {
            ranges::range_value_t<T> v(e);
            increment_impl(v);
            e = std::move(v);
        }
    } else if constexpr (ranges::input_range<T>) {
        static_assert(always_false_v<T>);
    } else if constexpr (tuple_like<T>) {
        for_each_tuple_element(x, [](auto &e) { increment_impl(e); });
    } else if constexpr (pre_incrementable<T>) {
        ++x;
    } else {
        static_assert(always_false_v<T>);
    }
}

template <class T> void decrement_impl(T &x) {
    if constexpr (mutable_lvalue_range<T>) {
        for (auto &&e : x) {
            decrement_impl(e);
        }
    } else if constexpr (mutable_proxy_range<T>) {
        for (auto &&e : x) {
            ranges::range_value_t<T> v(e);
            decrement_impl(v);
            e = std::move(v);
        }
    } else if constexpr (ranges::input_range<T>) {
        static_assert(always_false_v<T>);
    } else if constexpr (tuple_like<T>) {
        for_each_tuple_element(x, [](auto &e) { decrement_impl(e); });
    } else if constexpr (pre_decrementable<T>) {
        --x;
    } else {
        static_assert(always_false_v<T>);
    }
}
} // namespace incdec_detail

template <class T> void increment(T &x) { incdec_detail::increment_impl(x); }
template <class T> void decrement(T &x) { incdec_detail::decrement_impl(x); }

template <class... Ts> void in(Ts &...args) { (cin >> ... >> args); }
template <class... Ts> void in_z(Ts &...args) {
    in(args...);
    (decrement(args), ...);
}

namespace input_detail {
template <class Tuple> void read(Tuple &t) {
    apply(
        [](auto &...xs) {
            if constexpr (sizeof...(xs) > 0) {
                in(xs...);
            }
        },
        t);
}
template <class Tuple> void read_z(Tuple &t) {
    apply(
        [](auto &...xs) {
            if constexpr (sizeof...(xs) > 0) {
                in_z(xs...);
            }
        },
        t);
}

template <class T, size_t> using repeat_t = T;
template <class T, size_t... Is> auto input_impl(index_sequence<Is...>) {
    tuple<repeat_t<T, Is>...> t;
    read(t);
    return t;
}
template <class T, size_t... Is> auto input_z_impl(index_sequence<Is...>) {
    tuple<repeat_t<T, Is>...> t;
    read_z(t);
    return t;
}
} // namespace input_detail

template <class... Ts> auto input() {
    tuple<Ts...> t;
    in(t);
    return t;
}
template <class... Ts> auto input_z() {
    tuple<Ts...> t;
    in_z(t);
    return t;
}

template <class T, size_t N> auto input() {
    return input_detail::input_impl<T>(make_index_sequence<N>{});
}
template <class T, size_t N> auto input_z() {
    return input_detail::input_z_impl<T>(make_index_sequence<N>{});
}

template <bool do_flush = false, class Hd, class... Tl>
void out(const Hd &hd, const Tl &...tl) {
    cout << hd;
    if constexpr (sizeof...(Tl)) {
        (cout << ... << (cout << current_sep(cout), tl));
    }
#ifdef ONLINE_JUDGE
    cout << "\n";
    if constexpr (do_flush) {
        cout << flush;
    }
#else
    cout << endl;
#endif
}

template <class... Ts> void out_and_flush(const Ts &...args) {
    out<true>(args...);
}

template <class Hd, class... Tl> void err(const Hd &hd, const Tl &...tl) {
#ifndef ONLINE_JUDGE
    cerr << hd;
    if constexpr (sizeof...(Tl)) {
        (cerr << ... << (cerr << current_sep(cerr), tl));
    }
    cerr << "\n";
#endif
}

template <bool do_flush = false, class It1, class It2>
void out2(It1 first, It2 last) {
    for (; first != last; ++first) {
        out<do_flush>(*first);
    }
}
template <bool do_flush = false, class R> void out2(R &&range) {
    out2<do_flush>(begin(range), end(range));
}

template <class It1, class It2> void out2_and_flush(It1 first, It2 last) {
    out2<true>(first, last);
}
template <class R> void out2_and_flush(R &&range) { out2<true>(range); }

template <class It1, class It2> void err2(It1 first, It2 last) {
#ifndef ONLINE_JUDGE
    for (; first != last; ++first) {
        err(*first);
    }
#endif
}
template <class R> void err2(R &&range) {
#ifndef ONLINE_JUDGE
    err2(begin(range), end(range));
#endif
}

auto &change_out_sep(string s = string()) { return cout << sep(s); }
auto &change_err_sep(string s = string()) { return cerr << sep(s); }
void change_seps(string s = string()) {
    change_out_sep(s);
    change_err_sep(s);
}

constexpr array<int, 2> dx_2{1, 0}, dy_2{0, 1};
constexpr array<int, 4> dx{1, 0, -1, 0}, dy{0, 1, 0, -1};
constexpr array<int, 8> dx_8{1, 1, 0, -1, -1, -1, 0, 1},
    dy_8{0, 1, 1, 1, 0, -1, -1, -1};

namespace dir_detail {
template <size_t N>
constexpr auto zip(const array<int, N> &xs, const array<int, N> &ys) {
    array<pair<int, int>, N> res{};
    for (size_t i = 0; i < N; ++i) {
        res[i] = {xs[i], ys[i]};
    }
    return res;
}
}; // namespace dir_detail

constexpr auto dxdy_2 = dir_detail::zip(dx_2, dy_2);
constexpr auto dxdy = dir_detail::zip(dx, dy);
constexpr auto dxdy_8 = dir_detail::zip(dx_8, dy_8);

#define dir_2(dx_, dy_) for (auto [dx_, dy_] : dxdy_2)
#define dir(dx_, dy_) for (auto [dx_, dy_] : dxdy)
#define dir_8(dx_, dy_) for (auto [dx_, dy_] : dxdy_8)

#define all(v) (v).begin(), (v).end()
#define all_r(v) (v).rbegin(), (v).rend()
#define iter(v, l, r) ((v).begin() + l), ((v).begin() + r)

template <class T> void dedup(T &v) { v.erase(unique(all(v)), v.end()); }
template <class T> void sort_and_dedup(T &v) {
    sort(all(v));
    v.erase(unique(all(v)), v.end());
}

constexpr string_view yes() { return "Yes"; }
constexpr string_view no() { return "No"; }
constexpr string_view yn(bool cond) {
    if (cond) {
        return yes();
    } else {
        return no();
    }
}
string yn(bool cond, const string &yes_str, const string &no_str) {
    if (cond) {
        return yes_str;
    } else {
        return no_str;
    }
}
template <class T>
constexpr T yn(bool cond, const T &yes_val, const T &no_val) {
    if (cond) {
        return yes_val;
    } else {
        return no_val;
    }
}

template <class T1, class T2> bool chmin(T1 &l, const T2 &r) {
    if (r < l) {
        l = r;
        return true;
    }
    return false;
}
template <class T1, class T2> bool chmax(T1 &l, const T2 &r) {
    if (r > l) {
        l = r;
        return true;
    }
    return false;
}

template <class T>
using sum_type_t = typename conditional_t<is_integral_v<T>, common_type<T, ll>,
                                          type_identity<T>>::type;
template <class T, class U>
using sum_init_type_t =
    typename conditional_t<is_arithmetic_v<T> && is_arithmetic_v<U>,
                           common_type<sum_type_t<T>, U>,
                           type_identity<T>>::type;

template <class It> auto sum_of(It first, It last) {
    using T = typename iterator_traits<It>::value_type;
    return accumulate(first, last, sum_type_t<T>{});
}
template <class It, class U> auto sum_of(It first, It last, U init) {
    using T = typename iterator_traits<It>::value_type;
    using R = sum_init_type_t<T, U>;
    return accumulate(first, last, R(init));
}

template <class Hd1, class Hd2, class... Tl>
auto min_of(Hd1 hd1, Hd2 hd2, Tl... tl) {
    if constexpr (sizeof...(Tl) == 0) {
        return min(hd1, hd2);
    } else {
        return min(hd1, min_of(hd2, tl...));
    }
}
template <class Hd1, class Hd2, class... Tl>
auto max_of(Hd1 hd1, Hd2 hd2, Tl... tl) {
    if constexpr (sizeof...(Tl) == 0) {
        return max(hd1, hd2);
    } else {
        return max(hd1, max_of(hd2, tl...));
    }
}
template <class Hd1, class Hd2, class... Tl>
auto gcd_of(Hd1 hd1, Hd2 hd2, Tl... tl) {
    if constexpr (sizeof...(Tl) == 0) {
        return gcd(hd1, hd2);
    } else {
        return gcd(hd1, gcd_of(hd2, tl...));
    }
}
template <class Hd1, class Hd2, class... Tl>
auto lcm_of(Hd1 hd1, Hd2 hd2, Tl... tl) {
    if constexpr (sizeof...(Tl) == 0) {
        return lcm(hd1, hd2);
    } else {
        return lcm(hd1, lcm_of(hd2, tl...));
    }
}

namespace div_detail {
template <class T> using uncv_t = remove_cv_t<T>;

template <class T>
constexpr bool integral_non_bool_v =
    is_integral_v<uncv_t<T>> && !is_same_v<uncv_t<T>, bool>;

template <class T1, class T2>
using common_t = common_type_t<uncv_t<T1>, uncv_t<T2>>;

template <class T1, class T2>
using div_type_t =
    conditional_t<is_unsigned_v<common_t<T1, T2>> &&
                      (is_signed_v<uncv_t<T1>> || is_signed_v<uncv_t<T2>>),
                  make_signed_t<common_t<T1, T2>>, common_t<T1, T2>>;

template <class To, class From> constexpr bool fits_in_div_type(From x) {
    using F = uncv_t<From>;

    if constexpr (is_signed_v<To> && is_unsigned_v<F>) {
        using UTo = make_unsigned_t<To>;
        return x <= static_cast<UTo>(numeric_limits<To>::max());
    } else {
        return true;
    }
}
} // namespace div_detail

template <class T1, class T2>
constexpr pair<div_detail::div_type_t<T1, T2>, div_detail::div_type_t<T1, T2>>
floor_div_mod(T1 x, T2 y) {
    static_assert(div_detail::integral_non_bool_v<T1>);
    static_assert(div_detail::integral_non_bool_v<T2>);
    assert(y != 0);

    using T = div_detail::div_type_t<T1, T2>;
    assert(div_detail::fits_in_div_type<T>(x));
    assert(div_detail::fits_in_div_type<T>(y));

    T a = static_cast<T>(x), b = static_cast<T>(y);
    T q = a / b, r = a % b;

    if constexpr (is_signed_v<T>) {
        if (r != 0 && ((r < 0) != (b < 0))) {
            --q;
            r += b;
        }
    }

    return pair{q, r};
}
template <class T1, class T2>
constexpr div_detail::div_type_t<T1, T2> floor_div(T1 x, T2 y) {
    static_assert(div_detail::integral_non_bool_v<T1>);
    static_assert(div_detail::integral_non_bool_v<T2>);
    assert(y != 0);
    return floor_div_mod(x, y).first;
}
template <class T1, class T2>
constexpr div_detail::div_type_t<T1, T2> floor_mod(T1 x, T2 y) {
    static_assert(div_detail::integral_non_bool_v<T1>);
    static_assert(div_detail::integral_non_bool_v<T2>);
    assert(y != 0);
    return floor_div_mod(x, y).second;
}
template <class T1, class T2>
constexpr div_detail::div_type_t<T1, T2> ceil_div(T1 x, T2 y) {
    static_assert(div_detail::integral_non_bool_v<T1>);
    static_assert(div_detail::integral_non_bool_v<T2>);
    assert(y != 0);

    using T = div_detail::div_type_t<T1, T2>;

    auto [q, r] = floor_div_mod(x, y);
    return r == 0 ? q : static_cast<T>(q + T{1});
}

template <class T, size_t N>
auto make_vector(vector<size_t> &sizes, T const &x) {
    if constexpr (N == 1) {
        return vector(sizes[0], x);
    } else {
        size_t size = sizes[N - 1];
        sizes.pop_back();
        return vector(size, make_vector<T, N - 1>(sizes, x));
    }
}
template <class T, size_t N>
auto make_vector(size_t const (&sizes)[N], T const &x = T()) {
    vector<size_t> s(N);
    rep(i, N) { s[i] = sizes[N - i - 1]; }
    return make_vector<T, N>(s, x);
}
template <class T, size_t N> auto make_vector(vector<int> &sizes, T const &x) {
    if constexpr (N == 1) {
        return vector(sizes[0], x);
    } else {
        int size = sizes[N - 1];
        sizes.pop_back();
        return vector(size, make_vector<T, N - 1>(sizes, x));
    }
}
template <class T, size_t N>
auto make_vector(int const (&sizes)[N], T const &x = T()) {
    vector<int> s(N);
    rep(i, N) { s[i] = sizes[N - i - 1]; }
    return make_vector<T, N>(s, x);
}
template <class T, size_t Hd, size_t... Tl> auto make_array() {
    if constexpr (sizeof...(Tl) == 0) {
        return array<T, Hd>{};
    } else {
        return array<decltype(make_array<T, Tl...>()), Hd>{};
    }
}

constexpr int inf32 = 1'000'000'001;
constexpr ll inf64 = 2'000'000'000'000'000'001;

constexpr ull ten_powers[20] = {1,
                                10,
                                100,
                                1000,
                                10000,
                                100000,
                                1000000,
                                10000000,
                                100000000,
                                1000000000,
                                10000000000,
                                100000000000,
                                1000000000000,
                                10000000000000,
                                100000000000000,
                                1000000000000000,
                                10000000000000000,
                                100000000000000000,
                                1000000000000000000,
                                10000000000000000000ULL};

constexpr ull two_powers[64] = {1,
                                2,
                                4,
                                8,
                                16,
                                32,
                                64,
                                128,
                                256,
                                512,
                                1024,
                                2048,
                                4096,
                                8192,
                                16384,
                                32768,
                                65536,
                                131072,
                                262144,
                                524288,
                                1048576,
                                2097152,
                                4194304,
                                8388608,
                                16777216,
                                33554432,
                                67108864,
                                134217728,
                                268435456,
                                536870912,
                                1073741824,
                                2147483648,
                                4294967296,
                                8589934592,
                                17179869184,
                                34359738368,
                                68719476736,
                                137438953472,
                                274877906944,
                                549755813888,
                                1099511627776,
                                2199023255552,
                                4398046511104,
                                8796093022208,
                                17592186044416,
                                35184372088832,
                                70368744177664,
                                140737488355328,
                                281474976710656,
                                562949953421312,
                                1125899906842624,
                                2251799813685248,
                                4503599627370496,
                                9007199254740992,
                                18014398509481984,
                                36028797018963968,
                                72057594037927936,
                                144115188075855872,
                                288230376151711744,
                                576460752303423488,
                                1152921504606846976,
                                2305843009213693952,
                                4611686018427387904,
                                9223372036854775808ULL};

template <class T, template <class...> class Heap = priority_queue>
using min_heap = Heap<T, vector<T>, greater<>>;

template <class S, S e> constexpr S e_const() { return e; }
template <class S1, S1 e1, class S2, S2 e2>
constexpr pair<S1, S2> e_const_pair() {
    return {e1, e2};
}
template <class S> S op_min(S a, S b) { return min(a, b); }
template <class S> S op_max(S a, S b) { return max(a, b); }
template <class S> pair<S, S> op_minmax(pair<S, S> a, pair<S, S> b) {
    auto [a1, a2] = a;
    auto [b1, b2] = b;
    return {min(a1, b1), max(a2, b2)};
}
template <class S> S op_add(S a, S b) { return a + b; }
template <class S1, class S2>
pair<S1, S2> op_add_pair(pair<S1, S2> a, pair<S1, S2> b) {
    auto [a1, a2] = a;
    auto [b1, b2] = b;
    return {a1 + b1, a2 + b2};
}
template <class F1, class F2, class S> S mapping_affine(pair<F1, F2> f, S x) {
    auto [a, b] = f;
    return a * x + b;
}
template <class F1, class F2, class S>
pair<S, S> mapping_minmax_affine(pair<F1, F2> f, pair<S, S> x) {
    auto [a, b] = f;
    auto [l, r] = x;
    if (a >= 0) {
        return {a * l + b, a * r + b};
    } else {
        return {a * r + b, a * l + b};
    }
}
template <class F1, class F2, class S1, class S2>
pair<S1, S2> mapping_len_and_affine(pair<F1, F2> f, pair<S1, S2> x) {
    auto [a, b] = f;
    auto [x1, x2] = x;
    return {x1, a * x2 + b * x1};
}
template <class F1, class F2>
pair<F1, F2> composition_affine(pair<F1, F2> f, pair<F1, F2> g) {
    auto [a_f, b_f] = f;
    auto [a_g, b_g] = g;
    return {a_f * a_g, a_f * b_g + b_f};
}

template <class M, class S, S e> constexpr M mint_const() { return M(e); }
template <class M1, class S1, S1 e1, class M2, class S2, S2 e2>
constexpr pair<M1, M2> mint_pair() {
    return {M1(e1), M2(e2)};
}

#ifdef ATCODER_SEGTREE_HPP
template <class S, S e>
using segtree_min = segtree<S, op_min<S>, e_const<S, e>>;
template <class S, S e>
using segtree_max = segtree<S, op_max<S>, e_const<S, e>>;
template <class S> using segtree_add = segtree<S, op_add<S>, e_const<S, 0>>;
template <class M, class S = int>
using segtree_add_mint = segtree<M, op_add<M>, mint_const<M, S, 0>>;
#endif

#ifdef ATCODER_LAZYSEGTREE_HPP
// f の傾きが非負であることを仮定する
template <class S, S e>
using lazy_segtree_min =
    lazy_segtree<S, op_min<S>, e_const<S, e>, pair<S, S>,
                 mapping_affine<S, S, S>, composition_affine<S, S>,
                 e_const_pair<S, 1, S, 0>>;
// f の傾きが非負であることを仮定する
template <class S, S e>
using lazy_segtree_max =
    lazy_segtree<S, op_max<S>, e_const<S, e>, pair<S, S>,
                 mapping_affine<S, S, S>, composition_affine<S, S>,
                 e_const_pair<S, 1, S, 0>>;
template <class S, S e_min, S e_max>
using lazy_segtree_minmax =
    lazy_segtree<pair<S, S>, op_minmax<S>, e_const_pair<S, e_min, S, e_max>,
                 pair<S, S>, mapping_minmax_affine<S, S, S>,
                 composition_affine<S, S>, e_const_pair<S, 1, S, 0>>;
template <class S>
using lazy_segtree_add =
    lazy_segtree<pair<int, S>, op_add_pair<int, S>, e_const_pair<int, 0, S, 0>,
                 pair<S, S>, mapping_len_and_affine<S, S, int, S>,
                 composition_affine<S, S>, e_const_pair<S, 1, S, 0>>;
template <class M, class S = int>
using lazy_segtree_add_mint =
    lazy_segtree<pair<int, M>, op_add_pair<int, M>,
                 mint_pair<int, int, 0, M, S, 0>, pair<M, M>,
                 mapping_len_and_affine<M, M, int, M>, composition_affine<M, M>,
                 mint_pair<M, S, 1, M, S, 0>>;
#endif

// 数列を mod m 上で見たとき、区間に +1 または -1 を加える操作の最小回数を求める。
// 区間に整数 x を加える操作の最小 sum |x| と同値である。
// a, b は同じ長さで、各要素は [0, m) を仮定する。
// T は 64 bit 整数型、m <= 10^9 を想定する。
// 平均計算量 O(N)。

#include <algorithm>
#include <cassert>
#include <cstddef>
#include <type_traits>
#include <vector>

template <class T>
T minimum_mod_range_increment_decrement_operations(const std::vector<T> &a,
                                                   const std::vector<T> &b,
                                                   T m) {
    static_assert(std::is_integral_v<T>, "T must be integer.");
    static_assert(sizeof(T) >= sizeof(long long),
                  "T must be at least 64-bit integer type.");

    assert(a.size() == b.size());
    assert(m > 0);

    const std::size_t n = a.size();
    std::vector<T> differences;
    differences.reserve(n + 1);

    auto mod_difference = [m](T from, T to) -> T {
        return from <= to ? to - from : m - (from - to);
    };

    auto add_mod_difference = [m](std::size_t &quotient, T &remainder, T diff) {
        if (remainder >= m - diff) {
            remainder -= m - diff;
            ++quotient;
        } else {
            remainder += diff;
        }
    };

    T previous = 0;
    std::size_t negative_count = 0;
    T remainder = 0;
    for (std::size_t i = 0; i < n; ++i) {
        if constexpr (std::is_signed_v<T>) {
            assert(0 <= a[i]);
            assert(0 <= b[i]);
        }
        assert(a[i] < m);
        assert(b[i] < m);

        const T current = mod_difference(a[i], b[i]);
        const T diff = mod_difference(previous, current);
        differences.emplace_back(diff);
        add_mod_difference(negative_count, remainder, diff);
        previous = current;
    }

    const T last = mod_difference(previous, T(0));
    differences.emplace_back(last);
    add_mod_difference(negative_count, remainder, last);

    assert(remainder == 0);
    assert(negative_count <= n + 1);

    const std::size_t keep_count = n + 1 - negative_count;
    if (0 < keep_count && keep_count < differences.size()) {
        std::nth_element(differences.begin(),
                         differences.begin() +
                             static_cast<std::ptrdiff_t>(keep_count),
                         differences.end());
    }
    T answer = 0;
    for (std::size_t i = 0; i < keep_count; ++i) {
        answer += differences[i];
    }
    return answer;
}

void solve() {
    int n;
    ll m;
    ::in(n);
    std::vector<ll> a(n), b(n);
    ::in(m);
    rep(i, n) { ::in(a[i]); }
    rep(i, n) { ::in(b[i]); }

    out(minimum_mod_range_increment_decrement_operations(a, b, m));
}

int main(void) {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    cerr << fixed << setprecision(15);
    int t = 1;
    // ::in(t);
    while (t--) {
        solve();
    }
    return 0;
}