Submission #68327282

---

Source Code Expand

#pragma GCC optimize "-O3,omit-frame-pointer,inline,unroll-all-loops,fast-math"

#include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;

// ===== MACROS =====
#define FOR(i, n, m) for (int i = n; i < (int)m; ++i)
#define REP(i, n) FOR (i, 0, n)
#define REP_1(i, n) for (int i = 1; i <= (int)n; ++i)
#define RFOR(i, n, m) for (int i = (int)n - 1; i >= (int)m; --i)
#define RREP(i, n) RFOR(i, n, 0)
#define RREP_1(i, n) for (int i = (int)n; i >= 1; --i)

#define ALL(v) v.begin(), v.end()
#define RALL(v) v.rbegin(), v.rend()
#define SIZE(v) (int)v.size()
#define EMPTY(v) v.empty()
#define SORT(v) sort(ALL(v))
#define RSORT(v) sort(RALL(v))
#define REVERSE(v) reverse(ALL(v))
#define UNIQUE(v) (SORT(v), v.erase(unique(ALL(v)), v.end()))

#define PB push_back
#define EB emplace_back
#define MP make_pair

// ===== UTILITY MACROS =====
#define YES() cout << "YES\n"
#define NO() cout << "NO\n"
#define Yes() cout << "Yes\n"
#define No() cout << "No\n"
#define YESNO(cond) cout << ((cond) ? "YES" : "NO") << '\n'
#define YesNo(cond) cout << ((cond) ? "Yes" : "No") << '\n'

#define IN(x, a, b) ((a) <= (x) && (x) < (b))
#define BETWEEN(x, a, b) ((a) <= (x) && (x) <= (b))

#define FASTIO() \
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
#define PRECISION(n) cout << fixed << setprecision(n)

// ===== TYPE ALIASES =====
using P = pair<int, int>;
using ll = long long;
using ull = unsigned long long;
using ld = long double;

template <class T>
using min_queue = priority_queue<T, vector<T>, greater<T>>;
template <class T>
using max_queue = priority_queue<T>;

struct uint64_hash {
    static inline uint64_t rotr(uint64_t x, unsigned k) {
        return (x >> k) | (x << (8U * sizeof(uint64_t) - k));
    }
    static inline uint64_t hash_int(uint64_t x) noexcept {
        auto h1 = x * (uint64_t)(0xA24BAED4963EE407);
        auto h2 = rotr(x, 32U) * (uint64_t)(0x9FB21C651E98DF25);
        auto h = rotr(h1 + h2, 32U);
        return h;
    }
    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM =
            std::chrono::steady_clock::now().time_since_epoch().count();
        return hash_int(x + FIXED_RANDOM);
    }
};

template <typename K, typename V, typename Hash = uint64_hash>
using hash_map = __gnu_pbds::gp_hash_table<K, V, Hash>;
template <typename K, typename Hash = uint64_hash>
using hash_set = hash_map<K, __gnu_pbds::null_type, Hash>;

template <typename T, size_t MAXSIZE>
struct fast_queue {
    T data[MAXSIZE];
    size_t head, tail;
    fast_queue() : head(0), tail(0) {}
    inline void push(const T &x) { data[tail++] = x; }
    inline void emplace(T &&x) { data[tail++] = std::move(x); }
    inline T front() const { return data[head]; }
    inline void pop() { head++; }
    inline bool empty() const { return head == tail; }
    inline size_t size() const { return tail - head; }
    inline void clear() { head = tail = 0; }
    inline T *begin() { return data + head; }
    inline T *end() { return data + tail; }
    inline const T *begin() const { return data + head; }
    inline const T *end() const { return data + tail; }
};

template <typename K, typename V, size_t MAXSIZE>
struct fast_map {
    struct Entry {
        K key;
        V value;
        bool used;
        Entry() : used(false) {}
    };
    vector<Entry> data;
    size_t element_count;

    fast_map() : data(MAXSIZE), element_count(0) {}

    inline size_t hash(const K &key) const {
        return std::hash<K>{}(key) % data.size();
    }

    inline size_t find_pos(const K &key) const {
        size_t pos = hash(key);
        while (data[pos].used && data[pos].key != key) {
            pos = (pos + 1) % MAXSIZE;
        }
        return pos;
    }

    inline V &operator[](const K &key) {
        size_t pos = find_pos(key);
        if (!data[pos].used) {
            data[pos].key = key;
            data[pos].value = V{};
            data[pos].used = true;
            element_count++;
        }
        return data[pos].value;
    }

    inline const V &at(const K &key) const {
        size_t pos = find_pos(key);
        if (!data[pos].used || data[pos].key != key) {
            throw std::out_of_range("FastHashTable: key not found");
        }
        return data[pos].value;
    }

    inline V &at(const K &key) {
        size_t pos = find_pos(key);
        if (!data[pos].used || data[pos].key != key) {
            throw std::out_of_range("FastHashTable: key not found");
        }
        return data[pos].value;
    }

    inline size_t count(const K &key) const {
        size_t pos = find_pos(key);
        return (data[pos].used && data[pos].key == key) ? 1 : 0;
    }

    inline bool erase(const K &key) {
        size_t pos = find_pos(key);
        if (data[pos].used && data[pos].key == key) {
            data[pos].used = false;
            element_count--;
            return true;
        }
        return false;
    }

    inline size_t size() const { return element_count; }
    inline bool empty() const { return element_count == 0; }

    inline bool find(const K &key, V &result) const {
        if (count(key)) {
            result = at(key);
            return true;
        }
        return false;
    }

    inline bool contains(const K &key) const { return count(key) > 0; }

    inline void clear() {
        for (size_t i = 0; i < data.size(); i++) {
            data[i].used = false;
        }
        element_count = 0;
    }

    struct iterator {
        Entry *ptr;
        Entry *end_ptr;

        iterator(Entry *p, Entry *e) : ptr(p), end_ptr(e) {
            while (ptr < end_ptr && !ptr->used) ptr++;
        }

        pair<K, V> operator*() const { return {ptr->key, ptr->value}; }
        iterator &operator++() {
            do {
                ptr++;
            } while (ptr < end_ptr && !ptr->used);
            return *this;
        }
        bool operator!=(const iterator &other) const {
            return ptr != other.ptr;
        }
        bool operator==(const iterator &other) const {
            return ptr == other.ptr;
        }
    };

    iterator begin() {
        return iterator(data.data(), data.data() + data.size());
    }
    iterator end() {
        return iterator(data.data() + data.size(), data.data() + data.size());
    }
};

// ===== NUMBER SORTING =====
inline void radix_sort_impl(vector<int> &arr) {
    constexpr int BITS = 8;
    constexpr int BUCKETS = 1 << BITS;
    constexpr int MASK = BUCKETS - 1;

    vector<int> temp(arr.size());
    vector<int> count(BUCKETS);

    for (int shift = 0; shift < 32; shift += BITS) {
        fill(count.begin(), count.end(), 0);
        for (int x : arr) count[(x >> shift) & MASK]++;
        for (int i = 1; i < BUCKETS; i++) count[i] += count[i - 1];
        for (int i = arr.size() - 1; i >= 0; i--) {
            int x = arr[i];
            temp[--count[(x >> shift) & MASK]] = x;
        }
        arr = temp;
    }
}

inline void counting_sort_impl(vector<int> &arr, int max_val) {
    vector<int> count(max_val + 1, 0);
    for (auto x : arr) count[x]++;

    int pos = 0;
    for (int i = 0; i <= max_val; i++) {
        while (count[i]--) {
            arr[pos++] = i;
        }
    }
}

void fast_sort(vector<int> &arr) {
    if (arr.empty()) return;
    int max_val = *max_element(arr.begin(), arr.end());
    if (max_val <= (int)arr.size()) {
        counting_sort_impl(arr, max_val);
    } else {
        radix_sort_impl(arr);
    }
}

// ===== CONSTANTS =====
constexpr int INF = 1000000100;
constexpr ll INFL = (ll)1000000000000001000LL;
constexpr ll MOD = 998244353;
constexpr ld PI = 3.141592653589793238462643383279;
constexpr ld EPS = 1e-9;

// ===== DIRECTIONS =====
constexpr int dx4[] = {0, 1, 0, -1};
constexpr int dy4[] = {1, 0, -1, 0};
constexpr int dx8[] = {0, 1, 1, 1, 0, -1, -1, -1};
constexpr int dy8[] = {1, 1, 0, -1, -1, -1, 0, 1};

// ===== DEBUG MACROS =====
const std::string COLOR_RESET = "\033[0m", BRIGHT_GREEN = "\033[1;32m",
                  BRIGHT_RED = "\033[1;31m", BRIGHT_CYAN = "\033[1;36m",
                  NORMAL_CROSSED = "\033[0;9;37m",
                  RED_BACKGROUND = "\033[1;41m", NORMAL_FAINT = "\033[0;2m";

#ifdef LOCAL
#define dbg(x)                                                         \
    std::cerr << BRIGHT_CYAN << #x << COLOR_RESET << " = " << (x)      \
              << NORMAL_FAINT << " (L" << __LINE__ << ") " << __FILE__ \
              << COLOR_RESET << std::endl
#define dbgif(cond, x)                                                      \
    ((cond) ? std::cerr << BRIGHT_CYAN << #x << COLOR_RESET << " = " << (x) \
                        << NORMAL_FAINT << " (L" << __LINE__ << ") "        \
                        << __FILE__ << COLOR_RESET << std::endl             \
            : std::cerr)
#define msg(s)                                                          \
    std::cerr << BRIGHT_GREEN << s << NORMAL_FAINT << " (L" << __LINE__ \
              << ") " << __FILE__ << COLOR_RESET << std::endl
#else
#define dbg(x) 0
#define dbgif(cond, x) 0
#define msg(s) 0
#endif

// ===== PAIR OPERATORS =====
template <class T1, class T2>
std::pair<T1, T2> operator+(const std::pair<T1, T2> &l,
                            const std::pair<T1, T2> &r) {
    return std::make_pair(l.first + r.first, l.second + r.second);
}
template <class T1, class T2>
std::pair<T1, T2> operator-(const std::pair<T1, T2> &l,
                            const std::pair<T1, T2> &r) {
    return std::make_pair(l.first - r.first, l.second - r.second);
}

// ===== I/O OPERATORS =====
template <class IStream, class T>
IStream &operator>>(IStream &is, std::vector<T> &vec) {
    for (auto &v : vec) is >> v;
    return is;
}
template <class OStream, class T>
OStream &operator<<(OStream &os, const std::vector<T> &vec);
template <class OStream, class T, size_t sz>
OStream &operator<<(OStream &os, const std::array<T, sz> &arr);
template <class OStream, class T, class TH>
OStream &operator<<(OStream &os, const std::unordered_set<T, TH> &vec);
template <class OStream, class T, class U>
OStream &operator<<(OStream &os, const std::pair<T, U> &pa);
template <class OStream, class T>
OStream &operator<<(OStream &os, const std::deque<T> &vec);
template <class OStream, class T>
OStream &operator<<(OStream &os, const std::set<T> &vec);
template <class OStream, class T>
OStream &operator<<(OStream &os, const std::multiset<T> &vec);
template <class OStream, class T>
OStream &operator<<(OStream &os, const std::unordered_multiset<T> &vec);
template <class OStream, class T, class U>
OStream &operator<<(OStream &os, const std::pair<T, U> &pa);
template <class OStream, class TK, class TV>
OStream &operator<<(OStream &os, const std::map<TK, TV> &mp);
template <class OStream, class TK, class TV, class TH>
OStream &operator<<(OStream &os, const std::unordered_map<TK, TV, TH> &mp);
template <class OStream, class... T>
OStream &operator<<(OStream &os, const std::tuple<T...> &tpl);
template <class OStream, class T>
OStream &operator<<(OStream &os, const std::vector<T> &vec) {
    os << '[';
    for (auto v : vec) os << v << ',';
    os << ']';
    return os;
}
template <class OStream, class T, size_t sz>
OStream &operator<<(OStream &os, const std::array<T, sz> &arr) {
    os << '[';
    for (auto v : arr) os << v << ',';
    os << ']';
    return os;
}
template <class... T>
std::istream &operator>>(std::istream &is, std::tuple<T...> &tpl) {
    std::apply([&is](auto &&...args) { ((is >> args), ...); }, tpl);
    return is;
}
template <class OStream, class... T>
OStream &operator<<(OStream &os, const std::tuple<T...> &tpl) {
    os << '(';
    std::apply([&os](auto &&...args) { ((os << args << ','), ...); }, tpl);
    return os << ')';
}
template <class OStream, class T, class TH>
OStream &operator<<(OStream &os, const std::unordered_set<T, TH> &vec) {
    os << '{';
    for (auto v : vec) os << v << ',';
    os << '}';
    return os;
}
template <class OStream, class T>
OStream &operator<<(OStream &os, const std::deque<T> &vec) {
    os << "deq[";
    for (auto v : vec) os << v << ',';
    os << ']';
    return os;
}
template <class OStream, class T>
OStream &operator<<(OStream &os, const std::set<T> &vec) {
    os << '{';
    for (auto v : vec) os << v << ',';
    os << '}';
    return os;
}
template <class OStream, class T>
OStream &operator<<(OStream &os, const std::multiset<T> &vec) {
    os << '{';
    for (auto v : vec) os << v << ',';
    os << '}';
    return os;
}
template <class OStream, class T>
OStream &operator<<(OStream &os, const std::unordered_multiset<T> &vec) {
    os << '{';
    for (auto v : vec) os << v << ',';
    os << '}';
    return os;
}
template <class OStream, class T, class U>
OStream &operator<<(OStream &os, const std::pair<T, U> &pa) {
    return os << '(' << pa.first << ',' << pa.second << ')';
}
template <class OStream, class TK, class TV>
OStream &operator<<(OStream &os, const std::map<TK, TV> &mp) {
    os << '{';
    for (auto v : mp) os << v.first << "=>" << v.second << ',';
    os << '}';
    return os;
}
template <class OStream, class TK, class TV, class TH>
OStream &operator<<(OStream &os, const std::unordered_map<TK, TV, TH> &mp) {
    os << '{';
    for (auto v : mp) os << v.first << "=>" << v.second << ',';
    os << '}';
    return os;
}

// ===== BIT OPERATIONS =====
__attribute__((always_inline)) inline ull bit(ull x) { return 1ull << x; }
__attribute__((always_inline)) inline void setbit(ull &a, int b,
                                                  ull value = 1) {
    a = (a & ~bit(b)) | (value << b);
}
__attribute__((always_inline)) inline ull getbit(ull a, int b) {
    return (a >> b) & 1;
}
__attribute__((always_inline)) inline ull lsb(ull a) {
    return __builtin_ctzll(a);
}
__attribute__((always_inline)) inline int msb(uint64_t bb) {
    return __builtin_clzll(bb) ^ 63;
}

// ===== CHMAX/CHMIN =====
template <typename T>
inline bool chmax(T &a, T b) {
    return a < b && (a = b, true);
}
template <typename T>
inline bool chmin(T &a, T b) {
    return a > b && (a = b, true);
}

// ===== TIMER =====
struct Timer {
    chrono::time_point<chrono::high_resolution_clock> start_time;
    chrono::duration<double> elapsed;
    Timer() : elapsed(0) {}
    double elapsed_seconds() const {
        return elapsed.count() +
               chrono::duration<double>(chrono::high_resolution_clock::now() -
                                        start_time)
                   .count();
    }
    void reset() { elapsed = chrono::duration<double>::zero(); }
};

// ===== RANDOM NUMBER GENERATOR =====
struct RNG {
    uint64_t s[2];
    RNG(ull seed) { reset(seed); }
    RNG() { reset(0); }
    using result_type = int;
    static __attribute__((always_inline)) inline uint64_t rotl(const uint64_t x,
                                                               int k) {
        return (x << k) | (x >> (64 - k));
    }
    inline void reset(ull seed) {
        struct splitmix64_state {
            ull s;
            ull splitmix64() {
                ull result = (s += 0x9E3779B97f4A7C15);
                result = (result ^ (result >> 30)) * 0xBF58476D1CE4E5B9;
                result = (result ^ (result >> 27)) * 0x94D049BB133111EB;
                return result ^ (result >> 31);
            }
        };
        splitmix64_state sm{seed};
        s[0] = sm.splitmix64();
        s[1] = sm.splitmix64();
    }
    ull next() {
        const uint64_t s0 = s[0];
        uint64_t s1 = s[1];
        const uint64_t result = rotl(s0 * 5, 7) * 9;
        s1 ^= s0;
        s[0] = rotl(s0, 24) ^ s1 ^ (s1 << 16);
        s[1] = rotl(s1, 37);
        return result;
    }
    inline int operator()() { return next(); }
    inline int operator()(int r) { return next() % r; }
    inline int operator()(int l, int r) { return l + (next() % (r - l + 1)); }
    inline double d() { return (double)operator()() / 4294967296.0; }
    inline double d(double l, double r) { return l + d() * (r - l); }
    template <class T>
    void shuffle(vector<T> &v) {
        int sz = v.size();
        for (int i = sz; i > 1; i--) {
            int p = operator()(i);
            swap(v[i - 1], v[p]);
        }
    }
    template <class T>
    inline T sample(vector<T> const &v) {
        return v[operator()(v.size())];
    }
} rng;

// ===== COMBINATORICS =====
struct modint {
    ll n;

   public:
    modint() : n(0) {}
    modint(ll x) : n(((x % MOD) + MOD) % MOD) {}

    ll val() const { return n; }

    modint pow(ll m) const {
        modint r = 1, a = *this;
        while (m > 0) {
            if (m & 1) r *= a;
            a *= a;
            m >>= 1;
        }
        return r;
    }

    modint inv() const { return pow(MOD - 2); }

    modint &operator++() { return *this += 1; }
    modint &operator--() { return *this -= 1; }
    modint operator++(int) {
        modint ret = *this;
        ++*this;
        return ret;
    }
    modint operator--(int) {
        modint ret = *this;
        --*this;
        return ret;
    }

    modint operator+() const { return *this; }
    modint operator-() const { return modint() - *this; }

    friend bool operator==(const modint &lhs, const modint &rhs) {
        return lhs.n == rhs.n;
    }
    friend bool operator!=(const modint &lhs, const modint &rhs) {
        return lhs.n != rhs.n;
    }
    friend bool operator<(const modint &lhs, const modint &rhs) {
        return lhs.n < rhs.n;
    }
    friend bool operator<=(const modint &lhs, const modint &rhs) {
        return lhs.n <= rhs.n;
    }
    friend bool operator>(const modint &lhs, const modint &rhs) {
        return lhs.n > rhs.n;
    }
    friend bool operator>=(const modint &lhs, const modint &rhs) {
        return lhs.n >= rhs.n;
    }

    friend modint &operator+=(modint &lhs, const modint &rhs) {
        lhs.n += rhs.n;
        if (lhs.n >= MOD) lhs.n -= MOD;
        return lhs;
    }
    friend modint &operator-=(modint &lhs, const modint &rhs) {
        lhs.n -= rhs.n;
        if (lhs.n < 0) lhs.n += MOD;
        return lhs;
    }
    friend modint &operator*=(modint &lhs, const modint &rhs) {
        lhs.n = (lhs.n * rhs.n) % MOD;
        return lhs;
    }
    friend modint &operator/=(modint &lhs, const modint &rhs) {
        return lhs *= rhs.inv();
    }

    friend modint operator+(const modint &lhs, const modint &rhs) {
        modint res = lhs;
        res += rhs;
        return res;
    }
    friend modint operator-(const modint &lhs, const modint &rhs) {
        modint res = lhs;
        res -= rhs;
        return res;
    }
    friend modint operator*(const modint &lhs, const modint &rhs) {
        modint res = lhs;
        res *= rhs;
        return res;
    }
    friend modint operator/(const modint &lhs, const modint &rhs) {
        modint res = lhs;
        res /= rhs;
        return res;
    }

    friend istream &operator>>(istream &is, modint &m) {
        ll x;
        is >> x;
        m = modint(x);
        return is;
    }
    friend ostream &operator<<(ostream &os, const modint &m) {
        return os << m.n;
    }
};

using mi = modint;

struct Comb {
    vector<mi> fact, inv_fact;
    Comb(int n) : fact(n + 1), inv_fact(n + 1) {
        fact[0] = 1;
        for (int i = 1; i <= n; i++) {
            fact[i] = fact[i - 1] * i;
        }

        inv_fact[n] = fact[n].inv();
        for (int i = n - 1; i >= 0; i--) {
            inv_fact[i] = inv_fact[i + 1] * (i + 1);
        }
    }
    mi C(int n, int k) {
        if (n < 0 || k < 0 || n < k) return 0;
        return fact[n] * inv_fact[k] * inv_fact[n - k];
    }

    mi P(int n, int k) {
        if (n < 0 || k < 0 || n < k) return 0;
        return fact[n] * inv_fact[n - k];
    }

    mi H(int n, int k) {
        if (n < 0 || k < 0) return 0;
        return C(n + k - 1, k);
    }

    // n! / (k1! * k2! * ... * kn!)
    mi multinomial(int n, const vector<int> &ks) {
        mi res = fact[n];
        for (int k : ks) {
            if (k < 0 || k > n) return 0;
            res *= inv_fact[k];
        }
        return res;
    }

    // 1 / (n + 1) * C(2n, n)
    mi catalan(int n) { return C(2 * n, n) * mi(n + 1).inv(); }
};

// ===== DATA STRUCTURES =====
struct IndexSet {
    vector<int> que;
    vector<int> pos;

    IndexSet(int n) : pos(n, -1) {}

    void add(int v) {
        pos[v] = que.size();
        que.push_back(v);
    }

    void remove(int v) {
        int p = pos[v];
        int b = que.back();
        que[p] = b;
        que.pop_back();
        pos[b] = p;
        pos[v] = -1;
    }

    bool contains(int v) const { return pos[v] != -1; }

    int size() const { return que.size(); }
};

struct UnionFind {
    vector<int> data;
    vector<int> a;
    vector<int> b;

    UnionFind() = default;

    explicit UnionFind(size_t sz) : data(sz, -1), a(sz, 0), b(sz, 0) {}

    int unite(int x, int y) {
        x = find(x), y = find(y);
        if (x == y) return false;
        if (data[x] > data[y]) swap(x, y);
        data[x] += data[y];
        data[y] = x;
        a[x] += a[y];
        b[x] += b[y];
        int ret = min(a[x], b[x]);
        a[x] -= ret;
        b[x] -= ret;
        return ret;
    }

    int find(int k) {
        if (data[k] < 0) return (k);
        return data[k] = find(data[k]);
    }

    int size(int k) { return -data[find(k)]; }

    bool same(int x, int y) { return find(x) == find(y); }

    vector<vector<int>> groups() {
        int n = (int)data.size();
        vector<vector<int>> ret(n);
        for (int i = 0; i < n; ++i) {
            ret[find(i)].emplace_back(i);
        }
        ret.erase(remove_if(begin(ret), end(ret),
                            [&](const vector<int> &v) { return v.empty(); }),
                  end(ret));
        return ret;
    }
};

template <typename Monoid>
struct SegmentTree {
    using S = typename Monoid::S;

   private:
    int n, sz;

    vector<S> seg;

    Monoid m;

   public:
    SegmentTree() = default;

    explicit SegmentTree(Monoid m, int n) : m(m), n(n) {
        sz = 1;
        while (sz < n) sz <<= 1;
        seg.assign(2 * sz, m.e());
    }

    explicit SegmentTree(Monoid m, const vector<S> &v)
        : SegmentTree(m, (int)v.size()) {
        build(v);
    }

    void build(const vector<S> &v) {
        assert(n == (int)v.size());
        for (int k = 0; k < n; k++) seg[k + sz] = v[k];
        for (int k = sz - 1; k > 0; k--) {
            seg[k] = m.op(seg[2 * k + 0], seg[2 * k + 1]);
        }
    }

    void set(int k, const S &x) {
        k += sz;
        seg[k] = x;
        while (k >>= 1) {
            seg[k] = m.op(seg[2 * k + 0], seg[2 * k + 1]);
        }
    }

    S get(int k) const { return seg[k + sz]; }

    S operator[](int k) const { return get(k); }

    void apply(int k, const S &x) {
        k += sz;
        seg[k] = m.op(seg[k], x);
        while (k >>= 1) {
            seg[k] = m.op(seg[2 * k + 0], seg[2 * k + 1]);
        }
    }

    S prod(int l, int r) const {
        if (l >= r) return m.e();
        S L = m.e(), R = m.e();
        for (l += sz, r += sz; l < r; l >>= 1, r >>= 1) {
            if (l & 1) L = m.op(L, seg[l++]);
            if (r & 1) R = m.op(seg[--r], R);
        }
        return m.op(L, R);
    }

    S all_prod() const { return seg[1]; }

    template <typename C>
    int find_first(int l, const C &check) const {
        if (l >= n) return n;
        l += sz;
        S sum = m.e();
        do {
            while ((l & 1) == 0) l >>= 1;
            if (check(m.op(sum, seg[l]))) {
                while (l < sz) {
                    l <<= 1;
                    auto nxt = m.op(sum, seg[l]);
                    if (not check(nxt)) {
                        sum = nxt;
                        l++;
                    }
                }
                return l + 1 - sz;
            }
            sum = m.op(sum, seg[l++]);
        } while ((l & -l) != l);
        return n;
    }

    template <typename C>
    int find_last(int r, const C &check) const {
        if (r <= 0) return -1;
        r += sz;
        S sum = m.e();
        do {
            r--;
            while (r > 1 and (r & 1)) r >>= 1;
            if (check(m.op(seg[r], sum))) {
                while (r < sz) {
                    r = (r << 1) + 1;
                    auto nxt = m.op(seg[r], sum);
                    if (not check(nxt)) {
                        sum = nxt;
                        r--;
                    }
                }
                return r - sz;
            }
            sum = m.op(seg[r], sum);
        } while ((r & -r) != r);
        return -1;
    }
};

struct MinIdxMonoid {
    using S = pair<ll, int>;
    static constexpr S op(const S &a, const S &b) {
        return a.first <= b.first ? a : b;
    }
    static constexpr S e() { return {INFL, -1}; }
};

struct MaxIdxMonoid {
    using S = pair<ll, int>;
    static constexpr S op(const S &a, const S &b) {
        return a.first >= b.first ? a : b;
    }
    static constexpr S e() { return {-INFL, -1}; }
};

template <int N>
struct MatrixMonoid {
    using S = array<array<mi, N>, N>;
    static constexpr S op(const S &a, const S &b) {
        S c = {};
        REP (i, N)
            REP (j, N)
                REP (k, N) {
                    c[i][j] += c[i][j] + a[i][k] * b[k][j];
                }
        return c;
    }
    static constexpr S e() {
        S identity = {};
        REP (i, N) identity[i][i] = 1;
        return identity;
    }
};

struct Monoid {
    // using S = ?;
    // static constexpr S op(const S &a, const S &b) {}
    // static constexpr S e() {}
};

template <int char_size>
struct TrieNode {
    int nxt[char_size];

    int exist;
    vector<int> accept;

    TrieNode() : exist(0) { memset(nxt, -1, sizeof(nxt)); }
};

template <int char_size, int margin>
struct Trie {
    using Node = TrieNode<char_size>;

    vector<Node> nodes;
    int root;

    Trie() : root(0) { nodes.push_back(Node()); }

    void update_direct(int node, int id) { nodes[node].accept.push_back(id); }

    void update_child(int node, int child, int id) { ++nodes[node].exist; }

    void add(const string &str, int str_index, int node_index, int id) {
        if (str_index == str.size()) {
            update_direct(node_index, id);
        } else {
            const int c = str[str_index] - margin;
            if (nodes[node_index].nxt[c] == -1) {
                nodes[node_index].nxt[c] = (int)nodes.size();
                nodes.push_back(Node());
            }
            add(str, str_index + 1, nodes[node_index].nxt[c], id);
            update_child(node_index, nodes[node_index].nxt[c], id);
        }
    }

    void add(const string &str, int id) { add(str, 0, 0, id); }

    void add(const string &str) { add(str, nodes[0].exist); }

    void query(const string &str, const function<void(int)> &f, int str_index,
               int node_index) {
        for (auto &idx : nodes[node_index].accept) f(idx);
        if (str_index == str.size()) {
            return;
        } else {
            const int c = str[str_index] - margin;
            if (nodes[node_index].nxt[c] == -1) return;
            query(str, f, str_index + 1, nodes[node_index].nxt[c]);
        }
    }

    void query(const string &str, const function<void(int)> &f) {
        query(str, f, 0, 0);
    }

    int count() const { return (nodes[0].exist); }

    int size() const { return ((int)nodes.size()); }
};

// ===== INSERT CODE HERE =====

constexpr bool MULTI_TESTCASE = false;

void solve() {
    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    REP (i, n) cin >> a[i];
    sort(ALL(a));
    vector<ll> sum(n, a[0]);
    FOR (i, 1, n) sum[i] = sum[i - 1] + a[i];
    REP (i, q) {
        ll b;
        cin >> b;
        if (a.back() < b) {
            cout << -1 << endl;
            continue;
        }
        int it = lower_bound(ALL(a), b) - a.begin();
        auto ans = sum[it] - a[it] + (n - it) * (b - 1) + 1;
        cout << ans << endl;
    }
}

int main() {
    FASTIO();
    PRECISION(20);
    int t = 1;

    if (MULTI_TESTCASE) cin >> t;
    while (t--) {
        solve();
    }
}

Submission Info

Judge Result