Submission #69284027

---

Source Code Expand

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

// #include <boost/multiprecision/cpp_int.hpp>
// using namespace boost::multiprecision;



// #pragma GCC optimize("O3")
// #pragma GCC target("avx2")
// #pragma GCC optimize("unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

using ll = long long;
using ull = unsigned long long;
using ld = long double;
using sb = set<bool>;
using si = set<int>;
using sl = set<ll>;
using sd = set<double>;
using sc = set<char>;
using ss = set<string>;
using msb = multiset<bool>;
using msi = multiset<int>;
using msl = multiset<ll>;
using msd = multiset<double>;
using msc = multiset<char>;
using mss = multiset<string>;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
using vb = vector<bool>;
using vi = vector<int>;
using vl = vector<ll>;
using vd = vector<double>;
using vc = vector<char>;
using vs = vector<string>;
using vsb = vector<sb>;
using vsi = vector<si>;
using vsl = vector<sl>;
using vsd = vector<sd>;
using vsc = vector<sc>;
using vss = vector<ss>;
using vmsb = vector<msb>;
using vmsi = vector<msi>;
using vmsl = vector<msl>;
using vmsd = vector<msd>;
using vmsc = vector<msc>;
using vmss = vector<mss>;
using vpii = vector<pii>;
using vpil = vector<pil>;
using vpli = vector<pli>;
using vpll = vector<pll>;
using vvb = vector<vb>;
using vvi = vector<vi>;
using vvl = vector<vl>;
using vvd = vector<vd>;
using vvc = vector<vc>;
using vvs = vector<vs>;
using vvsb = vector<vsb>;
using vvsi = vector<vsi>;
using vvsl = vector<vsl>;
using vvsd = vector<vsd>;
using vvsc = vector<vsc>;
using vvss = vector<vss>;
using vvmsb = vector<vmsb>;
using vvmsi = vector<vmsi>;
using vvmsl = vector<vmsl>;
using vvmsd = vector<vmsd>;
using vvmsc = vector<vmsc>;
using vvmss = vector<vmss>;
using vvpii = vector<vpii>;
using vvpil = vector<vpil>;
using vvpli = vector<vpli>;
using vvpll = vector<vpll>;
using vvvb = vector<vvb>;
using vvvi = vector<vvi>;
using vvvl = vector<vvl>;
using vvvd = vector<vvd>;
using vvvc = vector<vvc>;
using vvvs = vector<vvs>;

#define ca const auto&
#define en "\n"
// #define en endl
#define yes cout << "Yes" << en;
#define no cout << "Yes" << en;
#define Yes     \
    {           \
        yes;    \
        return; \
    }
#define No      \
    {           \
        no;     \
        return; \
    }
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define repb(i, n) for (ll i = (ll)(n) - 1; i >= 0; i--)
#define repr(i, min, max) for (ll i = (ll)(min); i <= (ll)(max); i++)
#define reprb(i, min, max) for (ll i = (ll)(max); i >= (ll)(min); i--)
#define repc2(i0, i1, n) repr(i0, 0, n - 2) repr(i1, i0 + 1, n - 1)
#define repc3(i0, i1, i2, n) repr(i0, 0, n - 3) repr(i1, i0 + 1, n - 2) repr(i2, i1 + 1, n - 1)
#define repc4(i0, i1, i2, i3, n) \
    repr(i0, 0, n - 4) repr(i1, i0 + 1, n - 3) repr(i2, i1 + 1, n - 2) repr(i3, i2 + 1, n - 1)
#define repx(i0, i1, n0, n1) rep(i0, n0) rep(i1, n1)
#define reprx(i0, i1, n0_min, n0_max, n1_min, n1_max) repr(i0, n0_min, n0_max) repr(i1, n1_min, n1_max)
#define repx3(i0, i1, i2, n0, n1, n2) rep(i0, n0) rep(i1, n1) rep(i2, n2)
#define reprx3(i0, i1, i2, n0_min, n0_max, n1_min, n1_max, n2_min, n2_max) \
    repr(i0, n0_min, n0_max) repr(i1, n1_min, n1_max) repr(i2, n2_min, n2_max)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define bin(x) (1ll << (x))
#define fill_(x) setfill(' ') << setw(x)
#define fill0(x) setfill('0') << setw(x)
#define prec(x) fixed << setprecision(x)
#define fi first
#define se second

const short infs = 32767;
const int inf = 2147483647;
const ll infl = 9223372036854775807;
const int mod9 = 998244353;
const int mod10 = 1000000007;

template <typename T>
inline void in(vector<T>& v);
template <typename T, typename U>
inline void in(pair<T, U>& p);
template <typename... Ts>
inline void in(tuple<Ts...>& t);
template <typename T>
inline void in(set<T>& st, ll n);
template <typename T>
inline void in(multiset<T>& st, ll n);

template <typename T = ll>
inline T in() {
    T x;
    cin >> x;
    return x;
}
inline void in(bool& x) {
    cin >> x;
}
inline void in(short& x) {
    cin >> x;
}
inline void in(int& x) {
    cin >> x;
}
inline void in(ll& x) {
    cin >> x;
}
inline void in(ull& x) {
    cin >> x;
}
inline void in(double& x) {
    cin >> x;
}
inline void in(ld& x) {
    cin >> x;
}
inline void in(char& x) {
    cin >> x;
}
inline void in(string& x) {
    cin >> x;
}
template <size_t n>
inline void in(bitset<n>& x) {
    cin >> x;
}
template <typename... Args>
inline void in(Args&... args) {
    (in(args), ...);
}
template <typename T>
inline void in(vector<T>& v) {
    for (auto& e : v) in(e);
}
template <typename T, typename... Args>
inline void in(vector<T>& v0, Args&... args) {
    rep(i, v0.size()) {
        cin >> v0[i];
        ((cin >> args[i]), ...);
    }
}
template <typename T, typename U>
void in(pair<T, U>& p) {
    in(p.fi);
    in(p.se);
}
template <typename... Ts>
inline void in(tuple<Ts...>& t) {
    auto f = [&t]<size_t... Is>(index_sequence<Is...>) { ((cin >> get<Is>(t)), ...); };
    f(index_sequence_for<Ts...>{});
}
template <typename T>
inline void in(set<T>& st, ll n) {
    rep(i, n) {
        st.insert(in<T>());
    }
}
template <typename T>
void in(multiset<T>& st, ll n) {
    rep(i, n) {
        st.insert(in<T>());
    }
}

template <typename T, typename... Args>
inline void lab(const T& x, const Args&... args) {
    cout << x;
    ((cout << ' ' << args), ...);
    cout << ": ";
}

inline void out() {
    cout << en;
}
template <typename T>
inline void out(const T& x) {
    cout << x << en;
}
template <typename... Args>
inline void out(const Args&... args) {
    ((cout << args << ' '), ...);
    cout << en;
}
template <typename T>
inline void out(const vector<T>& v1, char c = '-') {
    if (c == 'd' && v1.size() == 0) cout << "null";
    if (c == '-' || c == 'd') {
        for (ca v0 : v1) cout << v0 << ' ';
        cout << en;
    } else if (c == 'n') {
        for (ca v0 : v1) cout << v0;
        cout << en;
    } else if (c == 'e') {
        for (ca v0 : v1) cout << v0 << en;
    } else {
        cerr << "error: 第2引数が有効ではありません ('-', 'n', 'e', 'd')\n";
        exit(1);
    }
}
template <typename T>
inline void out(const vector<vector<T>>& v2, char c = '-') {
    if (c == 'd' && v2.size() == 0) cout << "null at all";
    if (c == '-' || c == 'd') {
        for (ca v1 : v2) {
            if (v1.size() == 0 && c == 'd') cout << "null";
            for (ca v0 : v1) {
                cout << v0 << ' ';
            }
            cout << en;
        }
        if (c == 'd') cout << "---" << en;
    } else if (c == 'n') {
        for (ca v1 : v2) {
            for (ca v0 : v1) {
                cout << v0;
            }
            cout << en;
        }
    } else {
        cerr << "error: 第2引数が有効ではありません ('-', 'n', 'd')\n";
        exit(1);
    }
}
template <typename T>
inline void out(vector<vector<vector<T>>> v3, char c = '-') {
    if (c == '-') {
        for (ca v2 : v3) {
            for (ca v1 : v2) {
                for (ca v0 : v1) {
                    cout << v0 << ' ';
                }
                cout << "  ";
            }
            cout << en;
        }
    } else if (c == 'e') {
        for (ca v2 : v3) {
            for (ca v1 : v2) {
                for (ca v0 : v1) {
                    cout << v0 << ' ';
                }
                cout << en;
            }
            cout << en;
        }
    }
}
template <typename T, typename U>
inline void out(const pair<T, U>& p, char c = '-') {
    cout << p.fi << ':' << p.se;
    if (c == '-') cout << en;
}
template <typename T, typename U>
inline void out(const vector<pair<T, U>>& vp, char c = '-') {
    for (ca p : vp) {
        cout << p.fi << ':' << p.se;
        if (c == 'e') {
            cout << en;
        } else {
            cout << ' ';
        }
    }
    if (c == '-') cout << en;
}
// '-', 'e', 'd'
template <typename T>
inline void out(const set<T>& s, char c = '-') {
    if (c == 'd' && s.empty() == true) cout << "null";
    for (auto itr = s.begin(); itr != s.end(); itr++) {
        cout << *itr;
        if (c == 'e') {
            cout << en;
        } else {
            cout << ' ';
        }
    }
    if (c != 'e') cout << en;
}
// '-', 'e', 'd'
template <typename T>
inline void out(const multiset<T>& ms, char c = '-') {
    if (c == 'd' && ms.empty() == true) cout << "null";
    for (auto itr = ms.begin(); itr != ms.end(); itr++) {
        cout << *itr;
        if (c == 'e') {
            cout << en;
        } else {
            cout << ' ';
        }
    }
    if (c != 'e') cout << en;
}
// '-', 'e', 'd'
template <typename T>
inline void out(const unordered_set<T>& us, char c = '-') {
    if (c == 'd' && us.empty() == true) cout << "null";
    for (auto itr = us.begin(); itr != us.end(); itr++) {
        cout << *itr;
        if (c == 'e') {
            cout << en;
        } else {
            cout << ' ';
        }
    }
    if (c != 'e') cout << en;
}
// '-', 'e', 'd'
template <typename T>
inline void out(const unordered_multiset<T>& ums, char c = '-') {
    if (c == 'd' && ums.empty() == true) cout << "null";
    for (auto itr = ums.begin(); itr != ums.end(); itr++) {
        cout << *itr;
        if (c == 'e') {
            cout << en;
        } else {
            cout << ' ';
        }
    }
    if (c != 'e') cout << en;
}
// '-', 'd'
template <typename T>
inline void out(const vector<set<T>>& v, char c = '-') {
    if (c == 'd' && v.size() == 0) cout << "null";
    for (ca s : v) {
        if (s.empty() && c == 'd') cout << "null";
        for (auto itr = s.begin(); itr != s.end(); itr++) cout << *itr << ' ';
        cout << en;
    }
}
// '-', 'd'
template <typename T>
inline void out(const vector<multiset<T>>& v, char c = '-') {
    if (c == 'd' && v.size() == 0) cout << "null";
    for (ca ms : v) {
        if (ms.empty() && c == 'd') cout << "null";
        for (auto itr = ms.begin(); itr != ms.end(); itr++) cout << *itr << ' ';
        cout << en;
    }
}
// '-', 'd'
template <typename T>
inline void out(const vector<unordered_set<T>>& v, char c = '-') {
    if (c == 'd' && v.size() == 0) cout << "null";
    for (ca us : v) {
        if (us.empty() && c == 'd') cout << "null";
        for (auto itr = us.begin(); itr != us.end(); itr++) cout << *itr << ' ';
        cout << en;
    }
}
// '-', 'd'
template <typename T>
inline void out(const vector<unordered_multiset<T>>& v, char c = '-') {
    if (c == 'd' && v.size() == 0) cout << "null";
    for (ca ums : v) {
        if (ums.empty() && c == 'd') cout << "null";
        for (auto itr = ums.begin(); itr != ums.end(); itr++) cout << *itr << ' ';
        cout << en;
    }
}
template <typename T, typename U>
inline void out(map<T, U> m, char c = '-') {
    for (ca e : m) {
        if (c == '-') {
            cout << e.fi << ":" << e.se << " ";
        } else if (c == 'e') {
            cout << e.fi << ":" << e.se << en;
        }
    }
    if (c == '-') cout << en;
}
template <typename T>
inline void out(queue<T> q, char c = '-') {
    if (c == 'd' && q.empty() == true) cout << "null";
    while (!q.empty()) {
        cout << q.front() << ' ';
        q.pop();
    }
    cout << en;
}
template <typename T>
inline void out(vector<queue<T>> vq, char c = '-') {
    if (c == 'd' && vq.size() == 0) cout << "null at all\n";
    for (ca q : vq) {
        while (!q.empty()) {
            cout << q.front() << ' ';
            q.pop();
        }
        cout << en;
    }
}
template <typename T>
inline void out(queue<vector<T>> qv, char c = '-') {
    if (c == 'd' && qv.empty() == true) cout << "null at all\n";
    while (!qv.empty()) {
        for (ca v : qv.front()) {
            cout << v << ' ';
        }
        qv.pop();
        cout << en;
    }
}
template <typename T>
inline void out(priority_queue<T> pq, char c = '-') {
    if (c == 'd' && pq.empty() == true) cout << "null";
    while (!pq.empty()) {
        cout << pq.top() << ' ';
        pq.pop();
    }
    cout << en;
}
template <typename T>
inline void out(stack<T> s, char c = '-') {
    if (c == 'd' && s.empty() == true) cout << "null";
    while (!s.empty()) {
        cout << s.top() << ' ';
        s.pop();
    }
    cout << en;
}
template <typename T>
inline void out(deque<T> d, char c = '-') {
    if (c == 'd' && d.empty() == true) {
        cout << "null" << en;
        return;
    }
    if (c == 'd') cout << "front  ";
    rep(i, d.size()) cout << d.at(i) << ' ';
    if (c == 'd') cout << " back";
    cout << en;
}

inline void yn_out(bool b) {
    cout << (b ? "Yes" : "No") << en;
}
inline void yn_out(vb v) {
    for (ca b : v) cout << (b ? "Yes" : "No") << en;
}

// 小さいなら更新 trueを返す
template <typename T, typename U>
bool chmin(T& a, U b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
// 大きいなら更新 trueを返す
template <typename T, typename U>
bool chmax(T& a, U b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

// 範囲内かどうか返す min <= x <= max
template <typename T, typename U = ll, typename V = ll>
bool inrange(T x, U min, V max) {
    return min <= x && x <= max;
}
// 範囲内かどうか返す min <= p <= max
template <typename T, typename U = ll, typename V = ll, typename W = ll, typename X = ll, typename Y = ll>
bool inrange(pair<T, U> p, pair<V, W> min, pair<X, Y> max) {
    return inrange(p.fi, min.fi, max.fi) && inrange(p.se, min.se, max.se);
}

template <typename T, typename U>
pair<T, U> p_move(pair<T, U> x, ll d) {
    const vi di = {1, 0, -1, 0, 1, 1, -1, -1};
    const vi dj = {0, 1, 0, -1, 1, -1, 1, -1};
    return {x.fi + di[d], x.se + dj[d]};
}
template <typename T, typename U, typename V, typename W>
auto man_dist(pair<T, U> x, pair<V, W> y) {
    return abs(x.fi - y.fi) + abs(x.se - y.se);
}
template <typename T, typename U, typename V, typename W>
auto euc_dist_sq(pair<T, U> x, pair<V, W> y) {
    return (x.fi - y.fi) * (x.fi - y.fi) + (x.se - y.se) * (x.se - y.se);
}

// 10進数の10^iの位を出力
ll digit(const ll& n, const ll& p) {
    ll d = 1;
    rep(i, p) d *= 10;
    return n / d % 10;
}

ll modinv(ll x, ll m) {
    auto euclid = [](auto self, ll a, ll b) -> pll {
        if (b == 0) {
            return make_pair(1, 0);
        } else {
            auto [_x, _y] = self(self, b, a % b);
            return make_pair(_y, -(a / b) * _y + _x);
        }
    };
    auto [i, p] = euclid(euclid, x, m);
    return i < 0 ? i + m : i;
}

// コラボレーション(nCr)を計算
// 逆元を求めるmodinvが必要
ll ncr(ll n, ll r, ll mod = 0) {
    if (n < 1 || n < r) return 0;
    ll ans = 1;
    if (mod == 0) {
        rep(i, min(r, n - r)) {
            ans = ans * (n - i) / (i + 1);
        }
    } else {
        rep(i, min(r, n - r)) {
            ans *= n - i;
            ans %= mod;
            ans *= modinv(i + 1, mod);
            ans %= mod;
        }
    }
    return ans;
}

ll powz(ll x, ll y, ll mod = 0) {
    vl v(63, x);
    rep(i, 62) {
        if (mod == 0 && y < bin(i + 1)) break;
        v[i + 1] = v[i] * v[i];
        if (mod != 0) v[i + 1] %= mod;
    }
    ll ans = 1;
    rep(i, 63) {
        if ((y >> i) & 1) {
            ans *= v[i];
            if (mod != 0) ans %= mod;
        }
    }
    return ans;
}

ll sqrtz(ll x) {
    if (x < 0) {
        cerr << "error: sqrtz()はx<0について定義されません" << flush;
        exit(1);
    }

    ll l = 0, r = 3037000500;
    while (l + 1 != r) {
        ll m = (l + r) / 2;
        if (m * m <= x) {
            l = m;
        } else {
            r = m;
        }
    }
    return l;
}

ll log10z(ll x) {
    if (x <= 0) {
        cerr << "error x: " << x;
        exit(1);
    }
    ll ans = 0;
    while (x >= 10) {
        x /= 10;
        ans++;
    }
    return ans;
}

template <typename T, typename U>
T mod(T x, U y) {
    if (y <= 0) {
        cerr << "error y: " << y;
        exit(1);
    }
    if (x >= 0) {
        return x % y;
    } else {
        return x % y + y;
    }
}

// 回文の判定
bool palindrome(string s) {
    int l = s.size();
    rep(i, l / 2) {
        if (s[i] != s[l - 1 - i]) return false;
    }
    return true;
}

// 2点を通るax+by+c=0の[a,b,c]を出力
tuple<ll, ll, ll> line(pll p0, pll p1) {
    ll a = p1.se - p0.se;
    ll b = p0.fi - p1.fi;
    ll c = -(a * p0.fi + b * p0.se);
    if (a < 0 || (a == 0 && b < 0) || (a == 0 && b == 0 && c < 0)) {
        a = -a;
        b = -b;
        c = -c;
    }
    ll d = gcd(a, gcd(b, c));
    a /= d;
    b /= d;
    c /= d;
    return {a, b, c};
}
// ax+by+c=0がp(x,y)を通るか判定
bool cross(tuple<ll, ll, ll> l, pll p) {
    auto [a, b, c] = l;
    auto [x, y] = p;
    return a * x + b * y + c == 0;
}

// next_permutation()のcollaboration版
// vは要素数r, 第2引数はn
template <class Iterator, typename T>
bool next_collaboration(Iterator first, Iterator last, T k) {
    auto i = last;
    do {
        --i;
        ++(*i);

        auto j = i;
        ++j;
        for (; j != last; ++j) {
            *j = *(j - 1) + 1;
        }
        if (*(last - 1) < k) {
            return true;
        }
    } while (i != first);
    return false;
}

// n個の要素をr通りから選ぶ方法の列挙 (r^n通り)
template <typename T>
bool next_repetition_oriented(vector<T>& v, T r) {
    repb(i, v.size()) {
        if (v[i] != r - 1) {
            v[i]++;
            repr(j, i + 1, v.size() - 1) {
                v[j] = 0;
            }
            return true;
        }
    }
    return false;
}

template <typename T = int>
inline vector<T> make_prime_list(ll x) {
    if (x <= 0) return {};
    vector<T> list(1, 2);
    T n = 3;
    for (;;) {
        bool flag = true;
        for (ca e : list) {
            if (e * e > n) break;
            if (n % e == 0) {
                flag = false;
                break;
            }
        }
        if (flag) {
            if (n > x) break;
            list.emplace_back(n);
        }
        n += 2;
    }
    return list;
}

// 素因数を(因数, 指数)で出力
// 1.6e6 num/s (1 <= num < 1e5)
template <typename T>
inline vector<pair<T, T>> prime_factorization_list(T n) {
    if (n == 1) return {};
    if (n < 1) cout << "The number is out of range\n";
    vector<pair<T, T>> ans;
    T i = 2;
    T end = n;
    while (n != 1) {
        if (i * i > n) break;
        if (n % i == 0) {
            ans.emplace_back(make_pair(i, 0));
            while (n % i == 0) {
                n /= i;
                ans[ans.size() - 1].se++;
            }
        }
        i++;
    }
    if (n != 1) ans.emplace_back(make_pair(n, 1));
    return ans;
}

// 約数を出力
template <typename T>
inline void make_divisor(const vector<pair<T, T>>& list, vector<T>& ans, T num, T index) {
    if (index >= list.size()) {
        ans.emplace_back(num);
        return;
    }
    for (T i = 0; i <= list[index].se; i++) {
        make_divisor(list, ans, num * powz(list[index].fi, i), index + 1);
    }
}
template <typename T>
inline vector<T> divisor_list(T n) {
    auto list = prime_factorization_list(n);
    vector<T> ans;
    const T begin = 1, index = 0;
    make_divisor(list, ans, begin, index);
    sort(all(ans));
    return ans;
}

template <typename T>
vector<vector<T>> rotate(const vector<vector<T>>& a, ll d) {
    ll n = a.size();
    if (n == 0) return a;
    ll m = a[0].size();
    vector<vector<T>> res;

    switch (mod(d, 4)) {
        case 0:
            return a;
        case 1:
            res = vector<vector<T>>(m, vector<T>(n));
            repx(i, j, n, m) {
                res[j][n - 1 - i] = a[i][j];
            }
            break;
        case 2:
            res = vector<vector<T>>(n, vector<T>(m));
            repx(i, j, n, m) {
                res[n - 1 - i][m - 1 - j] = a[i][j];
            }
            break;
        case 3:
            res = vector<vector<T>>(m, vector<T>(n));
            repx(i, j, n, m) {
                res[m - 1 - j][i] = a[i][j];
            }
            break;
    }
    return res;
}

vs rotate(const vs& a, ll d) {
    ll n = a.size();
    if (n == 0) return a;
    ll m = a[0].size();
    vs res;

    string s;
    switch (mod(d, 4)) {
        case 0:
            return a;
        case 1:
            rep(i, n) s += ' ';
            res = vs(m, s);

            repx(i, j, n, m) {
                res[j][n - 1 - i] = a[i][j];
            }
            break;
        case 2:
            rep(i, m) s += ' ';
            res = vs(n, s);

            repx(i, j, n, m) {
                res[n - 1 - i][m - 1 - j] = a[i][j];
            }
            break;
        case 3:
            rep(i, n) s += ' ';
            res = vs(m, s);

            repx(i, j, n, m) {
                res[m - 1 - j][i] = a[i][j];
            }
            break;
    }
    return res;
}


// UnionFind
// pathへのアクセスはroot()で更新されるため無効
// valueに値を格納可能 標準型はll
template <typename T = ll>
struct UnionFind {
   private:
    vl path;
    vl side;
    vector<T> value;

   public:
    void init(ll n) {
        path.resize(n);
        iota(all(path), 0);
        side.assign(n, 1);
        value.assign(n, 0);
    }
    void init(ll n, T v) {
        path.resize(n);
        iota(all(path), 0);
        side.assign(n, 1);
        value.assign(n, v);
    }
    ll root(ll x) {
        if (path[x] == x) {
            return x;
        } else {
            return path[x] = root(path[x]);
        }
    }
    bool same(ll x, ll y) {
        return root(x) == root(y);
    }
    // x <- y 結合したらtrue
    bool unite(ll x, ll y) {
        if (same(x, y)) return false;
        side[root(x)] += side[root(y)];
        // value[root(x)] += value[root(y)]; //適宜変更
        path[root(y)] = root(x);
        return true;
    }
    // 集合の要素数を返す
    ll count(ll x) {
        return side[root(x)];
    }
    // 集合に格納された値を参照渡しで取得
    // 結合後に実行
    T& element(ll x) {
        return value[root(x)];
    }
};

// 区間内の和を求める
template <typename T = ll>
struct BinaryIndexedTree {
   private:
    vector<T> a;

   public:
    BinaryIndexedTree(ll n) {
        init(n);
    }
    void init(ll n) {
        a.resize(n + 1);
    }
    // p番目の要素にxだけ加算
    void add(ll p, T x) {
        p++;
        rep(i, 31) {
            if ((p >> i) & 1) {
                a[p] += x;
                p += bin(i);
                if (p >= static_cast<ll>(a.size())) break;
            }
        }
    }
    // [l,r]の要素の和を取得
    T get(ll l, ll r) {
        r++;
        T ans = 0;
        rep(i, 31) {
            if ((r >> i) & 1) {
                ans += a[r];
                r -= bin(i);
            }
            if ((l >> i) & 1) {
                ans -= a[l];
                l -= bin(i);
            }
        }
        return ans;
    }
    // p番目の要素にxを代入
    void set(ll p, T x) {
        add(p, x - get(p, p));
    }
};

// 区間内の最大最小を求める
// 標準の型はll
template <typename T = ll>
struct MinMaxSegmentTree {
   private:
    ll n;
    vector<T> min_tree;
    vector<T> max_tree;

    void build(const vector<T>& v, ll i, ll start, ll end) {
        if (start == end) {
            min_tree[i] = v[start];
            max_tree[i] = v[start];
        } else {
            int m = (start + end) / 2;
            build(v, i * 2, start, m);
            build(v, i * 2 + 1, m + 1, end);
            min_tree[i] = std::min(min_tree[i * 2], min_tree[i * 2 + 1]);
            max_tree[i] = std::max(max_tree[i * 2], max_tree[i * 2 + 1]);
        }
    }
    T query(ll i, ll start, ll end, ll l, ll r, bool mode) {
        if (r < start || end < l) {
            if (mode)
                return numeric_limits<T>::max();
            else
                return numeric_limits<T>::min();
        }
        if (l <= start && end <= r) {
            if (mode)
                return min_tree[i];
            else
                return max_tree[i];
        }
        int mid = (start + end) / 2;
        T l_value = query(i * 2, start, mid, l, r, mode);
        T r_value = query(i * 2 + 1, mid + 1, end, l, r, mode);
        if (mode)
            return std::min(l_value, r_value);
        else
            return std::max(l_value, r_value);
    }

   public:
    MinMaxSegmentTree(vector<T> v) {
        init(v);
    }
    void init(vector<T> v) {
        n = v.size();
        ll _n = 1;
        while (_n < n) _n *= 2;
        _n *= 2;

        min_tree.resize(_n, numeric_limits<T>::max());
        max_tree.resize(_n, numeric_limits<T>::min());
        build(v, 1, 0, n - 1);
    }
    T min(ll l, ll r) {
        return query(1, 0, n - 1, l, r, 1);
    }
    T max(ll l, ll r) {
        return query(1, 0, n - 1, l, r, 0);
    }
};

ll solve();

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    // ll sum = 0;
    // rep(_, 1000) {
    //     sum += solve();
    // }
    // out(sum / 1000);

    solve();
    cout << flush;
    return 0;
}

//   _   _   __         __                           __
//  | | / | / /        /_/  __                 __   / /
//  | |/  |/ / __ ___ __ __/ /_  ___        __/ /_ / /_    ___
//  | / / / / / ／__// //_  __/／__ \      /_  __//  _ \ ／__ \
//  |  /|  / / ／   / /  / /_ / ____/       / /_ / / / // ____/
//  |_/ |_/ /_/    /_/   \__/ \___／        \__//_/ /_/ \___／
//       _____
//      / __  \                              ____
//     / /_ノ / __ ___  ___    ___   __ ___ /___ \ ________
//    / ____／ / ／__/／ _ \ ／ _ \ / ／__/／ _  //  _   _ \
//   / /      / ／   / /_/ // /_/ // ／   / /_/ // / / / / /
//  /_/      /_/     \___／ \__  //_/     \____//_/ /_/ /_/
//        ___              ___/ /             __   __
//      ／__/             /___／             / /  / /
//   __/ /_ __ ___  ___   ________          / /__/ / ___   __ ___  ___
//  /_  __// ／__/／ _ \ /  _   _ \        / ___  /／__ \ / ／__/／__ \
//   / /  / ／   / /_/ // / / / / /       / /  / // ____// ／   / ____/
//  /_/  /_/     \___／/_/ /_/ /_/       /_/  /_/ \___／/_/     \___／
//
/////////////////////////////////////////////////////////////////////////
// 2025/09/13


// #define DEBUG

const ll small = 5057206339;
const ll border = 250;

struct IO {
    ll n = 500, m = 50, l = 998000000000000ll, u = 1002000000000000ll;
    vl a;
    vl b;
    vl x;
    ll range;

    IO() {
        a.assign(n, 0);
        b.assign(m, 0);
        x.assign(n, 0);
        range = (u - l) * 1.3 / border;
    }
    void input_nmlu() {
        in(n, m, l, u);
        a.assign(n, 0);
        b.assign(m, 0);
        x.assign(n, 0);
    }
    void output_a() {
        // out(a);

        rep(i, border) {
            cout << a[i] - range << ' ';
        }
        repr(i, border, n - 1) {
            cout << a[i] << ' ';
        }
        cout << endl;
    }
    void input_b() {
        in(b);
    }
    void output_x() {
        out(x);
        cout << flush;
    }

    ll score() {
        ll res = 0;
        vl sum(m, -range);
        rep(i, n) {
            if (x[i] == 0) continue;
            sum[x[i] - 1] += a[i];
        }

        rep(i, m) {
            res += abs(sum[i] - b[i]);
            // out(abs(sum[i] - b[i]));
            // cout << flush;
            // cin.ignore();
        }
        // return res;
        return round((20 - log10(1 + res)) * 5e7);
    }

    void random_b() {
        random_device rd;
        mt19937 mt(rd());
        uniform_int_distribution<ll> rand(l, u);

        rep(i, b.size()) {
            b[i] = rand(mt);
        }
    }
};


ll solve() {
    IO io;
    io.input_nmlu();

    auto& n = io.n;
    auto& m = io.m;
    auto& l = io.l;
    auto& u = io.u;
    auto& a = io.a;
    auto& b = io.b;
    auto& x = io.x;
    auto& range = io.range;




    rep(i, border) {
        a[i] = l + (u - l) * (i + 0.5) / border;
    }
    double range_min = 0;
    double range_max = range * 2;
    repr(i, border, n - 1) {
        a[i] = range_min + (range_max - range_min) * ((i + 0.5 - border) / (n - border));
    }
    // out(a);


    io.output_a();
    io.input_b();
    // io.random_b();



    vpll b_rank;
    {
        rep(i, b.size()) {
            ll dist = infl;
            {
                auto it = lower_bound(all(a), b[i]);
                if (it != a.end()) chmin(dist, abs(b[i] - *it));
                if (it != a.begin()) {
                    it--;
                    chmin(dist, abs(b[i] - *it));
                }
            }

            b_rank.emplace_back(dist, i);
        }
    }
    sort(all(b_rank));
    set<pll> st;
    rep(i, a.size()) {
        st.insert({a[i], i});
    }


#ifdef DEBUG
    out(b_rank);
    for (ca[e1, e2] : st) cout << e1 << ':' << e2 << ' ';
    out();
    out();
#endif

    vl distance;
    for (ca[_, i_b] : b_rank) {
        ll dist = infl;
        ll i_a = -1;
        auto it = st.lower_bound({b[i_b], -1});
        if (it != st.end()) {
            if (chmin(dist, abs(b[i_b] - (*it).fi))) i_a = (*it).se;
        }
        if (it != st.begin()) {
            it--;
            if (chmin(dist, abs(b[i_b] - (*it).fi))) i_a = (*it).se;
        }
        distance.emplace_back(dist);
        x[i_a] = i_b + 1;
        st.erase({a[i_a], i_a});

#ifdef DEBUG
        out(_, i_b);
        out(dist, i_a, a[i_a], b[i_b]);
        out();
        cout << flush;
        cin.ignore();
#endif
    }


    vl sum(m);
    rep(i, n) {
        if (x[i] == 0) continue;
        sum[x[i] - 1] += a[i];
    }



    set<pll> st2;
    rep(i, a.size()) {
        st2.insert({a[i], i});
    }
    rep(i, m) {
        ll target = b[i] - (sum[i] - range);
        ll dist = infl;
        ll i_a = -1;

        auto it = st2.lower_bound({target, -1});
        if (it != st2.end()) {
            if (chmin(dist, abs(target - (*it).fi))) i_a = (*it).se;
        }
        if (it != st2.begin()) {
            it--;
            if (chmin(dist, abs(target - (*it).fi))) i_a = (*it).se;
        }
        x[i_a] = i + 1;
        st2.erase({a[i_a], i_a});
    }








    io.output_x();
    // out(io.score());
    // out();

    // for (ca e : st2) {
    //     cout << e.fi << ' ';
    // }
    // cout << en;

    // for (ca d : distance) out(d);
    // out(reduce(all(distance)) / distance.size());

    // return reduce(all(distance)) / distance.size();
    return io.score();
}

Submission Info

Compile Error

Main.cpp:1025:1: warning: multi-line comment [-Wcomment]
 1025 | //  | / / / / / ／__// //_  __/／__ \      /_  __//  _ \ ／__ \
      | ^
Main.cpp:1031:1: warning: multi-line comment [-Wcomment]
 1031 | //    / ____／ / ／__/／ _ \ ／ _ \ / ／__/／ _  //  _   _ \
      | ^
Main.cpp:1037:1: warning: multi-line comment [-Wcomment]
 1037 | //  /_  __// ／__/／ _ \ /  _   _ \        / ___  /／__ \ / ／__/／__ \
      | ^

Judge Result