Submission #51046291

---

Source Code Expand

#pragma region template

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

const long long INF = 1001001001;
const long long INFL = 1001001001001001001;
const double MYPI = 3.14159265358979;
const double epsilon = 1e-10;

using mint = modint1000000007;
using mint1 = modint998244353;

typedef long long ll;
typedef __int128_t lll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> pl;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<vvl> vvvl;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<vvd> vvvd;
typedef vector<mint> vm;
typedef vector<vm> vvm;
typedef vector<vvm> vvvm;
typedef vector<mint1> vm1;
typedef vector<vm1> vvm1;
typedef vector<vvm1> vvvm1;
typedef vector<modint> vm2;
typedef vector<vm2> vvm2;
typedef vector<vvm2> vvvm2;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<vvb> vvvb;
typedef vector<char> vc;
typedef vector<vc> vvc;
typedef vector<vvc> vvvc;
typedef vector<pl> vp;
typedef tuple<ll, ll, ll> tt;
typedef vector<tuple<ll, ll, ll>> vt;
typedef vector<string> vs;

#define overload3(a, b, c, d, ...) d
#define overload4(a, b, c, d, e, ...) e
#define overload5(a, b, c, d, e, f, ...) f
#define overload6(a, b, c, d, e, f, g, ...) g
#define pb push_back
#define eb emplace_back
#define MP make_pair
#define REP0(n) for (int _ = 0; _ < (n); _++)
#define REP1(i, n) for (int i = 0; i < (n); i++)
#define REP2(i, l, r) for (int i = (l); i < (r); i++)
#define REP3(i, l, r, d) for (int i = (l); i < (r); i += (d))
#define REP(...) overload4(__VA_ARGS__, REP3, REP2, REP1, REP0)(__VA_ARGS__)
#define REPP(i, n) for (int i = 1; i <= (n); i++)
#define RREP1(i, n) for (int i = (n)-1; i >= 0; i--)
#define RREP2(i, l, r) for (int i = (r)-1; i >= (l); i--)
#define RREP3(i, l, r, d) for (int i = (r)-1; i >= (l); i -= (d))
#define RREP(...) overload4(__VA_ARGS__, RREP3, RREP2, RREP1)(__VA_ARGS__)
#define RREPP(i, n) for (int i = (n); i > 0; i--)
#define EACH1(e, a) for (auto &e : a)
#define EACH2(x, y, a) for (auto &[x, y] : a)
#define EACH3(x, y, z, a) for (auto &[x, y, z] : a)
#define EACH(...) overload4(__VA_ARGS__, EACH3, EACH2, EACH1)(__VA_ARGS__)
#define ALL1(x) begin(x), end(x)
#define ALL2(x, a) begin(x), begin(x) + a
#define ALL3(x, a, b) begin(x) + a, begin(x) + b
#define ALL(...) overload3(__VA_ARGS__, ALL3, ALL2, ALL1)(__VA_ARGS__)
#define RALL1(i) (i).rbegin(), (i).rend()
#define RALL2(i, a) (i).rend() - a, (i).rend()
#define RALL3(i, a, b) (i).rend() - b, (i).rend() - a
#define RALL(...) overload3(__VA_ARGS__, RALL3, RALL2, RALL1)(__VA_ARGS__)
#define sz(x) (int)x.size()
#define LB(a, x) (lower_bound(a.begin(), a.end(), x) - a.begin())
#define UB(a, x) (upper_bound(a.begin(), a.end(), x) - a.begin())
#define FLG(x, i) (((x) >> (i)) & 1)
#define CNTBIT(x) __builtin_popcountll(x)
#define TOPBIT(t) (t == 0 ? -1 : 63 - __builtin_clzll(t))
#define BTMBIT(t) (t == 0 ? 64 : __builtin_ctzll(t))
#define IN(x, a, b) ((a) <= (x) && (x) < (b))
#define INT(...)                                                               \
    int __VA_ARGS__;                                                           \
    input(__VA_ARGS__)
#define STR(...)                                                               \
    string __VA_ARGS__;                                                        \
    input(__VA_ARGS__)
#define CHAR(...)                                                              \
    char __VA_ARGS__;                                                          \
    input(__VA_ARGS__)
#define DBL(...)                                                               \
    double __VA_ARGS__;                                                        \
    input(__VA_ARGS__)
#define LD(...)                                                                \
    long double __VA_ARGS__;                                                   \
    input(__VA_ARGS__)
#define VL1(a, n)                                                              \
    vector<long long> a(n);                                                    \
    for (int I = 0; I < (n); I++)                                              \
    cin >> a[I]
#define VL2(a, b, n)                                                           \
    vector<long long> a(n), b(n);                                              \
    for (int I = 0; I < (n); I++)                                              \
    cin >> a[I] >> b[I]
#define VL3(a, b, c, n)                                                        \
    vector<long long> a(n), b(n), c(n);                                        \
    for (int I = 0; I < (n); I++)                                              \
    cin >> a[I] >> b[I] >> c[I]
#define VL4(a, b, c, d, n)                                                     \
    vector<long long> a(n), b(n), c(n), d(n);                                  \
    for (int I = 0; I < (n); I++)                                              \
    cin >> a[I] >> b[I] >> c[I] >> d[I]
#define VL5(a, b, c, d, e, n)                                                  \
    vector<long long> a(n), b(n), c(n), d(n), e(n);                            \
    for (int I = 0; I < (n); I++)                                              \
    cin >> a[I] >> b[I] >> c[I] >> d[I] >> e[I]
#define VL(...) overload6(__VA_ARGS__, VL5, VL4, VL3, VL2, VL1)(__VA_ARGS__)
#define VD1(a, n)                                                              \
    vector<double> a(n);                                                       \
    for (int I = 0; I < (n); I++)                                              \
    cin >> a[I]
#define VD2(a, b, n)                                                           \
    vector<double> a(n), b(n);                                                 \
    for (int I = 0; I < (n); I++)                                              \
    cin >> a[I] >> b[I]
#define VD3(a, b, c, n)                                                        \
    vector<double> a(n), b(n), c(n);                                           \
    for (int I = 0; I < (n); I++)                                              \
    cin >> a[I] >> b[I] >> c[I]
#define VD4(a, b, c, d, n)                                                     \
    vector<double> a(n), b(n), c(n), d(n);                                     \
    for (int I = 0; I < (n); I++)                                              \
    cin >> a[I] >> b[I] >> c[I] >> d[I]
#define VD5(a, b, c, d, e, n)                                                  \
    vector<double> a(n), b(n), c(n), d(n), e(n);                               \
    for (int I = 0; I < (n); I++)                                              \
    cin >> a[I] >> b[I] >> c[I] >> d[I] >> e[I]
#define VD(...) overload6(__VA_ARGS__, VD5, VD4, VD3, VD2, VD1)(__VA_ARGS__)
#define VVL(a, n, m)                                                           \
    vector<vector<long long>> a(n, vector<long long>(m));                      \
    for (int I = 0; I < (n); I++)                                              \
        for (int J = 0; J < (m); J++)                                          \
    cin >> a[I][J]
#define VVC(s, n, m)                                                           \
    vector<vector<char>> s(n, vector<char>(m));                                \
    for (int I = 0; I < (n); I++)                                              \
        for (int J = 0; J < (m); J++)                                          \
    cin >> s[I][J]
#define VS(s, n)                                                               \
    vector<string> s(n);                                                       \
    for (int I = 0; I < (n); I++)                                              \
        cin >> s[I];

ostream &operator<<(ostream &os, const modint &a) { return os << a.val(); }
ostream &operator<<(ostream &os, const modint1000000007 &a) {
    return os << a.val();
}
ostream &operator<<(ostream &os, const modint998244353 &a) {
    return os << a.val();
}
template <typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &a) {
    return os << a.first << " " << a.second;
}
template <typename T1, typename T2, typename T3>
ostream &operator<<(ostream &os, const tuple<T1, T2, T3> &a) {
    return os << get<0>(a) << " " << get<1>(a) << " " << get<2>(a);
}

struct IoSetup {
    IoSetup() {
        ios::sync_with_stdio(false);
        cin.tie(0);
        cout << fixed << setprecision(15);
    }
} iosetup;

#ifdef LOCAL
#include <debug_print.hpp>
#define debug(...) debug_print::multi_print(#__VA_ARGS__, __VA_ARGS__)
#else
#define debug(...) (static_cast<void>(0))
#endif

template <typename T> using minheap = priority_queue<T, vector<T>, greater<T>>;

template <typename T> using maxheap = priority_queue<T>;

template <class... T> void input(T &...a) { (cin >> ... >> a); }

template <typename... T> constexpr auto min(T... a) {
    return min(initializer_list<common_type_t<T...>>{a...});
}
template <typename... T> constexpr auto max(T... a) {
    return max(initializer_list<common_type_t<T...>>{a...});
}

template <typename T1, typename T2> bool chmax(T1 &x, const T2 &y) {
    return x < y ? x = y, true : false;
}
template <typename T1, typename T2> bool chmin(T1 &x, const T2 &y) {
    return x > y ? x = y, true : false;
}

void OUT() { cout << '\n'; }

template <typename T, typename... Ts> void OUT(const T &a, const Ts &...b) {
    cout << a;
    (cout << ... << (cout << " ", b));
    cout << '\n';
}

template <typename T> void OUT(const vector<T> &res) {
    for (int i = 0; i < (int)res.size(); i++) {
        cout << res[i] << " ";
    }
    cout << '\n';
}

template <typename T> void OUT_(const T &a) { cout << a << " "; }

template <typename T> void OUTN(const vector<T> &res, long long margin = 0) {
    for (int i = 0; i < (int)res.size(); i++) {
        cout << res[i] + (T)margin << '\n';
    }
}

template <typename T> void OUTN_(const vector<T> &res, long long margin = 0) {
    for (int i = 0; i < (int)res.size(); i++) {
        cout << res[i] + (T)margin << " ";
    }
    cout << '\n';
}

template <typename T>
void OUTNN(const vector<vector<T>> &res, long long margin = 0) {
    for (int i = 0; i < (int)res.size(); i++) {
        for (int j = 0; j < (int)res[i].size(); j++) {
            cout << res[i][j] + (T)margin << " ";
        }
        cout << '\n';
    }
}

void YES(const bool &res = true, bool Capital = false) {
    if (Capital)
        cout << (res ? "YES" : "NO") << '\n';
    else
        cout << (res ? "Yes" : "No") << '\n';
}

void FIRST(const bool &res = true, bool Capital = false) {
    if (Capital)
        cout << (res ? "FIRST" : "SECOND") << '\n';
    else
        cout << (res ? "First" : "Second") << '\n';
}

template <typename T> void DEC(vector<T> &a, long long dif = 1) {
    for (auto &x : a)
        x -= (T)dif;
}
template <typename T> void DEC(vector<T> &a, vector<T> &b, long long dif = 1) {
    for (auto &x : a)
        x -= (T)dif;
    for (auto &x : b)
        x -= (T)dif;
}
template <typename T> void DEC(vector<vector<T>> &a, long long dif = 1) {
    for (auto &v : a)
        for (auto &x : v)
            x -= (T)dif;
}

template <typename T> void INC(vector<T> &a, long long dif = 1) {
    for (auto &x : a)
        x += (T)dif;
}
template <typename T> void INC(vector<T> &a, vector<T> &b, long long dif = 1) {
    for (auto &x : a)
        x += (T)dif;
    for (auto &x : b)
        x += (T)dif;
}
template <typename T> void INC(vector<vector<T>> &a, long long dif = 1) {
    for (auto &v : a)
        for (auto &x : v)
            x += (T)dif;
}

template <typename T> T SUM(const vector<T> &a) {
    return accumulate(a.begin(), a.end(), (T)0);
}
template <typename T> T SUM(const vector<vector<T>> &a) {
    T ret = 0;
    for (int i = 0; i < (int)a.size(); i++)
        ret += accumulate(a[i].begin(), a[i].end(), (T)0);
    return ret;
}

template <typename T> T MAX(const vector<T> &a) {
    return *max_element(a.begin(), a.end());
}
template <typename T> T MAX(const vector<vector<T>> &a) {
    T ret = -INFL;
    for (int i = 0; i < (int)a.size(); i++)
        for (int j = 0; j < (int)a[i].size(); j++)
            if (ret < a[i][j])
                ret = a[i][j];
    return ret;
}

template <typename T> int ARGMAX(const vector<T> &a) {
    int ret = 0;
    for (int i = 1; i < (int)a.size(); i++)
        if (a[ret] < a[i])
            ret = i;
    return ret;
}
template <typename T> pair<int, int> ARGMAX(const vector<vector<T>> &a) {
    pair<int, int> ret = {0, 0};
    for (int i = 0; i < (int)a.size(); i++)
        for (int j = 0; j < (int)a[i].size(); j++)
            if (a[ret.first][ret.second] < a[i][j])
                ret = {i, j};
    return ret;
}

template <typename T> T MIN(const vector<T> &a) {
    return *min_element(a.begin(), a.end());
}
template <typename T> T MIN(const vector<vector<T>> &a) {
    T ret = INFL;
    for (int i = 0; i < (int)a.size(); i++)
        for (int j = 0; j < (int)a[i].size(); j++)
            if (ret > a[i][j])
                ret = a[i][j];
    return ret;
}

template <typename T> int ARGMIN(const vector<T> &a) {
    int ret = 0;
    for (int i = 1; i < (int)a.size(); i++)
        if (a[ret] > a[i])
            ret = i;
    return ret;
}
template <typename T> pair<int, int> ARGMIN(const vector<vector<T>> &a) {
    pair<int, int> ret = {0, 0};
    for (int i = 0; i < (int)a.size(); i++)
        for (int j = 0; j < (int)a[i].size(); j++)
            if (a[ret.first][ret.second] > a[i][j])
                ret = {i, j};
    return ret;
}

template <typename T> int SIGN(const T &a) {
    if (abs(a) < epsilon)
        return 0;
    return a > 0 ? 1 : -1;
}

template <typename T> vector<T> UNIQ(vector<T> a) {
    sort(a.begin(), a.end());
    a.erase(unique(a.begin(), a.end()), a.end());
    return a;
}

template <typename T> vector<T> sorted(vector<T> a, bool Descending = false) {
    sort(a.begin(), a.end());
    if (Descending)
        reverse(a.begin(), a.end());
    return a;
}

template <typename T> vector<T> cumsum(const vector<T> &a) {
    int n = (int)a.size();
    vector<T> ret(n + 1, (T)0);
    for (int i = 0; i < n; i++)
        ret[i + 1] = ret[i] + a[i];
    return ret;
}
template <typename T> vector<vector<T>> cumsum(const vector<vector<T>> &a) {
    int n = (int)a.size(), m = (int)a[0].size();
    vector<vector<T>> ret(n + 1, vector<T>(m + 1, (T)0));
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            ret[i + 1][j + 1] = ret[i + 1][j] + a[i][j];
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            ret[i + 1][j + 1] += ret[i][j + 1];
    return ret;
}
template <typename T>
vector<vector<vector<T>>> cumsum(const vector<vector<vector<T>>> &a) {
    int n = (int)a.size(), m = (int)a[0].size(), l = (int)a[0][0].size();
    vector<vector<vector<T>>> ret(
        n + 1, vector<vector<T>>(m + 1, vector<T>(l + 1, (T)0)));
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            for (int k = 0; k < l; k++)
                ret[i + 1][j + 1][k + 1] = ret[i + 1][j + 1][k] + a[i][j][k];
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            for (int k = 0; k < l; k++)
                ret[i + 1][j + 1][k + 1] += ret[i][j + 1][k + 1];
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            for (int k = 0; k < l; k++)
                ret[i + 1][j + 1][k + 1] += ret[i + 1][j][k + 1];
    return ret;
}
template <typename T> void cumsum_inplace(vector<T> &a) {
    int n = (int)a.size();
    for (int i = 0; i < n - 1; i++)
        a[i + 1] += a[i];
}
template <typename T> void cumsum_inplace(vector<vector<T>> &a) {
    int n = (int)a.size(), m = (int)a[0].size();
    for (int i = 0; i < n - 1; i++)
        for (int j = 0; j < m; j++)
            a[i + 1][j] += a[i][j];
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m - 1; j++)
            a[i][j + 1] += a[i][j];
}
template <typename T> void cumsum_inplace(vector<vector<vector<T>>> &a) {
    int n = (int)a.size(), m = (int)a[0].size(), l = (int)a[0][0].size();
    for (int i = 0; i < n - 1; i++)
        for (int j = 0; j < m; j++)
            for (int k = 0; k < l; k++)
                a[i + 1][j][k] += a[i][j][k];
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m - 1; j++)
            for (int k = 0; k < l; k++)
                a[i][j + 1][k] += a[i][j][k];
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            for (int k = 0; k < l - 1; k++)
                a[i][j][k + 1] += a[i][j][k];
}

template <typename T = long long> struct Edge {
    int from, to;
    T cost;
    int idx;
    Edge() = default;
    Edge(int from, int to, T cost = 1, int idx = -1)
        : from(from), to(to), cost(cost), idx(idx) {}
    operator int() const { return to; }
};

template <typename T = long long> struct Graph {
    vector<vector<Edge<T>>> g;
    int es;
    Graph() = default;
    explicit Graph(int n) : g(n), es(0) {}
    size_t size() const { return g.size(); }
    void add_directed_edge(int from, int to, T cost = 1) {
        g[from].emplace_back(from, to, cost, es++);
    }
    void add_edge(int from, int to, T cost = 1) {
        g[from].emplace_back(from, to, cost, es);
        g[to].emplace_back(to, from, cost, es++);
    }
    inline vector<Edge<T>> &operator[](const int &k) { return g[k]; }
    inline const vector<Edge<T>> &operator[](const int &k) const {
        return g[k];
    }
};

template <typename T = long long> using Edges = vector<Edge<T>>;

template <typename T> struct Enumeration {
  private:
    static vector<T> _fact, _finv, _inv;
    inline static void expand(size_t sz) {
        if (_fact.size() < sz + 1) {
            int pre_sz = max(1, (int)_fact.size());
            _fact.resize(sz + 1, T(1));
            _finv.resize(sz + 1, T(1));
            _inv.resize(sz + 1, T(1));
            for (int i = pre_sz; i <= (int)sz; i++) {
                _fact[i] = _fact[i - 1] * T(i);
            }
            _finv[sz] = T(1) / _fact[sz];
            for (int i = (int)sz - 1; i >= pre_sz; i--) {
                _finv[i] = _finv[i + 1] * T(i + 1);
            }
            for (int i = pre_sz; i <= (int)sz; i++) {
                _inv[i] = _finv[i] * _fact[i - 1];
            }
        }
    }

  public:
    explicit Enumeration(size_t sz = 0) { expand(sz); }
    static inline T fact(int k) {
        expand(k);
        return _fact[k];
    }
    static inline T finv(int k) {
        expand(k);
        return _finv[k];
    }
    static inline T inv(int k) {
        expand(k);
        return _inv[k];
    }
    static T P(int n, int r) {
        if (r < 0 || n < r)
            return 0;
        return fact(n) * finv(n - r);
    }
    static T C(int p, int q) {
        if (q < 0 || p < q)
            return 0;
        return fact(p) * finv(q) * finv(p - q);
    }
};

template <typename T> vector<T> Enumeration<T>::_fact = vector<T>();
template <typename T> vector<T> Enumeration<T>::_finv = vector<T>();
template <typename T> vector<T> Enumeration<T>::_inv = vector<T>();

template <typename T>
T norm1(const pair<T, T> &a, const pair<T, T> &b = {(T)0, (T)0}) {
    return abs(a.first - b.first) + abs(a.second - b.second);
}
template <typename T>
T norm22(const pair<T, T> &a, const pair<T, T> &b = {(T)0, (T)0}) {
    return (a.first - b.first) * (a.first - b.first) +
           (a.second - b.second) * (a.second - b.second);
}
template <typename T>
double norm2(const pair<T, T> &a, const pair<T, T> &b = {(T)0, (T)0}) {
    return sqrt(norm22(a, b));
}

long long powll(long long a, long long n) {
    assert(n >= 0);
    if (n == 0)
        return 1;
    long long ret = 1;
    while (n) {
        if (n & 1)
            ret *= a;
        a *= a;
        n >>= 1;
    }
    return ret;
}

vector<int> str_to_vl(const string &s) {
    vector<int> ret(s.size());
    if (s.size() == 0)
        return ret;
    if (0 <= s[0] - 'A' && s[0] - 'A' < 26)
        for (int i = 0; i < (int)s.size(); i++)
            ret[i] = s[i] - 'A';
    else if (0 <= s[0] - 'a' && s[0] - 'a' < 26)
        for (int i = 0; i < (int)s.size(); i++)
            ret[i] = s[i] - 'a';
    else if (0 <= s[0] - '0' && s[0] - '0' < 10)
        for (int i = 0; i < (int)s.size(); i++)
            ret[i] = s[i] - '0';
    else
        assert(0);
    return ret;
}

// 0-indexed
int TOPDIGIT(long long x) {
    assert(x >= 0);
    int ret = 0;
    while (x >= 10) {
        x /= 10;
        ret++;
    }
    return ret;
}

template <typename T> vector<pair<T, int>> sorti(const vector<T> &a) {
    vector<pair<T, int>> ret(a.size());
    for (int i = 0; i < (int)a.size(); i++) {
        ret[i] = {a[i], i};
    }
    sort(ret.begin(), ret.end());
    return ret;
}
template <typename T1, typename T2>
vector<tuple<T1, T2, int>> sorti(const vector<T1> &a, const vector<T2> &b) {
    assert(a.size() == b.size());
    vector<tuple<T1, T2, int>> ret(a.size());
    for (int i = 0; i < (int)a.size(); i++) {
        ret[i] = {a[i], b[i], i};
    }
    sort(ret.begin(), ret.end());
    return ret;
}
template <typename T1, typename T2, typename T3>
vector<tuple<T1, T2, T3, int>> sorti(const vector<T1> &a, const vector<T2> &b,
                                     const vector<T3> &c) {
    assert(a.size() == b.size() && a.size() == c.size());
    vector<tuple<T1, T2, T3, int>> ret(a.size());
    for (int i = 0; i < (int)a.size(); i++) {
        ret[i] = {a[i], b[i], c[i], i};
    }
    sort(ret.begin(), ret.end());
    return ret;
}

// 高々小数第 k 位までの実数を 10^k 倍して整数化
ll decimal_to_ll(const string &s, int k) {
    int n = s.size();
    for (int i = 0; i < n; i++) {
        if (s[i] == '.') {
            ll ret = stoll(s.substr(0, i) + s.substr(i + 1));
            for (int j = 0; j < k - (n - 1 - i); j++)
                ret *= 10;
            return ret;
        }
    }
    ll ret = stoll(s);
    for (int i = 0; i < k; i++)
        ret *= 10;
    return ret;
}

template <typename F>
long long bisect_ll(const F &is_ok, long long ok, long long ng) {
    // while(!is_ok(ok)){
    //     ok <<= 1;
    // 	assert(ok < (1LL << 62));
    // }
    while (abs(ok - ng) > 1) {
        long long mid = (ok + ng) / 2;
        is_ok(mid) ? ok = mid : ng = mid;
    }
    return ok;
}

template <typename F>
double bisect_double(const F &is_ok, double ok, double ng) {
    // while(!is_ok(ok)){
    //     ok *= 2;
    //     assert(ok < (1LL << 62));
    // }
    while (abs(ok - ng) > epsilon) {
        double mid = (ok + ng) / 2;
        is_ok(mid) ? ok = mid : ng = mid;
    }
    return ok;
}

long long max(const int &a, const long long &b) { return max((long long)a, b); }
long long min(const int &a, const long long &b) { return min((long long)a, b); }

const vector<int> dy = {1, 0, -1, 0, 1, 1, -1, -1};
const vector<int> dx = {0, 1, 0, -1, -1, 1, 1, -1};

random_device seed_gen;
mt19937_64 rnd;

// [low, high] の範囲の値を持つ長さ len のランダムベクトルを生成
vector<long long> random_vl(int len, long long low, long long high) {
    uniform_int_distribution<long long> dist(low, high);
    vector<long long> ret(len);
    for (int i = 0; i < len; i++)
        ret[i] = dist(rnd);
    return ret;
};

vector<int> random_permutation(int len) {
    uniform_int_distribution<int> dist(1, len);
    vector<int> ret(len);
    set<int> se;
    for (int i = 0; i < len; i++) {
        int tmp = dist(rnd);
        while (se.count(tmp))
            tmp = dist(rnd);
        ret[i] = tmp;
        se.insert(ret[i]);
    }
    return ret;
};

#pragma endregion template

//----------------------------- コピペゾーン ---------------------------------

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

#define int long long

struct Solver {
    void solve() {
        // Write here.
        INT(n);
        VL(a, n);
        INT(m);
        VL(b, m);
        INT(l);
        VL(c, l);
        set<ll> se;
        REP(i, n)REP(j, m)REP(k, l)se.insert(a[i] + b[j] + c[k]);
        INT(q);
        VL(x, q);
        REP(i, q){
            YES(se.count(x[i]));
        }
    }

    int solve_test(int n, vl a) {
        // Write the test program.
        return 0;
    }

    int solve_naive(int n, vl a) {
        // Write a naive but correct program.
        return 0;
    }

    void random_test() {
        rnd.seed(seed_gen());

        uniform_int_distribution<int> dist_n(4, 10), dist_m(4, 10),
            dist_a(1, 20), dist_b(1, 20);

        for (int test = 1; test <= 100; test++) {
            int N = dist_n(rnd), M = dist_m(rnd);
            vl A = random_vl(N, 3, 20);
            auto Output = solve_test(N, A), Answer = solve_naive(N, A);
            if (Output != Answer) {
                cout << "Wrong Answer on Test #" << test << '\n';
                debug(N);
                debug(A);
                debug(Answer);
                debug(Output);
                break;
            }
        }
    }
};

signed main() {
    int T = 1;
    // cin >> T;

    Solver solver;
    while (T--)
        solver.solve();

    // solver.random_test();

    return 0;
}

Submission Info

Compile Error

Main.cpp:1: warning: ignoring ‘#pragma region template’ [-Wunknown-pragmas]
    1 | #pragma region template
      | 
Main.cpp:691: warning: ignoring ‘#pragma endregion template’ [-Wunknown-pragmas]
  691 | #pragma endregion template
      | 
Main.cpp: In member function ‘long long int Solver::solve_test(long long int, vl)’:
Main.cpp:717:24: warning: unused parameter ‘n’ [-Wunused-parameter]
  717 |     int solve_test(int n, vl a) {
      |                        ^
Main.cpp:717:30: warning: unused parameter ‘a’ [-Wunused-parameter]
  717 |     int solve_test(int n, vl a) {
      |                           ~~~^
Main.cpp: In member function ‘long long int Solver::solve_naive(long long int, vl)’:
Main.cpp:722:25: warning: unused parameter ‘n’ [-Wunused-parameter]
  722 |     int solve_naive(int n, vl a) {
      |                         ^
Main.cpp:722:31: warning: unused parameter ‘a’ [-Wunused-parameter]
  722 |     int solve_naive(int n, vl a) {
      |                            ~~~^
Main.cpp: In member function ‘void Solver::random_test()’:
Main.cpp:734:34: warning: unused variable ‘M’ [-Wunused-variable]
  734 |             int N = dist_n(rnd), M = dist_m(rnd);
      |                                  ^

Judge Result