#845404 (C++17) No.2233 Average

提出ソース
結果

問題	No.2233 Average
ユーザー	first_vil
提出日時	2023-03-03 21:32:48
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	253 ms / 2,000 ms
コード長	43,339 bytes
コンパイル時間	4,909 ms
コンパイル使用メモリ	290,884 KB
実行使用メモリ	6,944 KB
最終ジャッジ日時	2024-09-17 22:25:21
合計ジャッジ時間	7,948 ms
ジャッジサーバーID （参考情報）	judge6 / judge1
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,812 KB
testcase_01	AC	2 ms 6,940 KB
testcase_02	AC	1 ms 6,940 KB
testcase_03	AC	2 ms 6,940 KB
testcase_04	AC	1 ms 6,940 KB
testcase_05	AC	2 ms 6,940 KB
testcase_06	AC	1 ms 6,940 KB
testcase_07	AC	2 ms 6,944 KB
testcase_08	AC	140 ms 6,940 KB
testcase_09	AC	221 ms 6,940 KB
testcase_10	AC	219 ms 6,944 KB
testcase_11	AC	206 ms 6,940 KB
testcase_12	AC	181 ms 6,940 KB
testcase_13	AC	42 ms 6,944 KB
testcase_14	AC	126 ms 6,944 KB
testcase_15	AC	161 ms 6,944 KB
testcase_16	AC	48 ms 6,940 KB
testcase_17	AC	62 ms 6,940 KB
testcase_18	AC	253 ms 6,940 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code
#if !defined(MYLOCAL)  // 提出時用テンプレート

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#if !defined(_MSC_VER) && __has_include(<atcoder/all>)
#include <atcoder/all>
using namespace atcoder;
#endif
using namespace std;
using ll = long long;
using dd = double;
using vll = vector<ll>;
using vdd = vector<dd>;
using vvll = vector<vll>;
using vvdd = vector<vdd>;
using vvvll = vector<vvll>;
using vvvdd = vector<vvdd>;
using vvvvll = vector<vvvll>;
using pll = pair<ll, ll>;
using tll = tuple<ll, ll, ll>;
using qll = tuple<ll, ll, ll, ll>;
using vpll = vector<pll>;
using vtll = vector<tll>;
using vqll = vector<qll>;
using vvpll = vector<vpll>;
using vvtll = vector<vtll>;
using vvqll = vector<vqll>;
using namespace chrono;
constexpr ll INF = 1001001001001001001;
struct Fast {
    Fast() {
        cin.tie(0);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(numeric_limits<double>::max_digits10);
    }
} fast;
#define REPS(i, S, E) for (ll i = (S); i <= (E); i++)
#define REP(i, N) REPS(i, 0, (N)-1)
#define DEPS(i, S, E) for (ll i = (E); i >= (S); i--)
#define DEP(i, N) DEPS(i, 0, (N)-1)
#define EXPAND(x) x  // VS用おまじない
#define overload3(_1, _2, _3, name, ...) name
#define overload4(_1, _2, _3, _4, name, ...) name
#define overload5(_1, _2, _3, _4, _5, name, ...) name
#define rep3(i, S, E) for (ll i = (S); i <= (E); i++)
#define rep4(i, S, E, t) for (ll i = (S); i <= (E); i += (t))
#define rep(...) EXPAND(overload4(__VA_ARGS__, rep4, rep3, _, _)(__VA_ARGS__))
#define dep3(i, E, S) for (ll i = (E); i >= (S); i--)
#define dep4(i, E, S, t) for (ll i = (E); i >= (S); i -= (t))
#define dep(...) EXPAND(overload4(__VA_ARGS__, dep4, dep3, _, _)(__VA_ARGS__))
#define each2(e, v) for (auto &&e : v)
#define each3(a, b, v) for (auto &&[a, b] : v)
#define each4(a, b, c, v) for (auto &&[a, b, c] : v)
#define each5(a, b, c, d, v) for (auto &&[a, b, c, d] : v)
#define each(...) \
    EXPAND(overload5(__VA_ARGS__, each5, each4, each3, each2, _)(__VA_ARGS__))
#define ALL1(v) (v).begin(), (v).end()
#define ALL2(v, E) (v).begin(), (v).begin() + ((E) + 1)
#define ALL3(v, S, E) (v).begin() + (S), (v).begin() + ((E) + 1)
#define ALL(...) EXPAND(overload3(__VA_ARGS__, ALL3, ALL2, ALL1)(__VA_ARGS__))
#define all ALL
#define RALL1(v) (v).rbegin(), (v).rend()
#define RALL2(v, E) (v).rbegin(), (v).rbegin() + ((E) + 1)
#define RALL3(v, S, E) (v).rbegin() + (S), (v).rbegin() + ((E) + 1)
#define RALL(...) \
    EXPAND(overload3(__VA_ARGS__, RALL3, RALL2, RALL1)(__VA_ARGS__))
#define rall RALL
template<class T> inline bool chmax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmin(T &a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline T MaxE(vector<T> &v, ll S, ll E) {
    T m = v[S];
    rep(i, S, E) chmax(m, v[i]);
    return m;
}
template<class T> inline T MinE(vector<T> &v, ll S, ll E) {
    T m = v[S];
    rep(i, S, E) chmin(m, v[i]);
    return m;
}
template<class T> inline T MaxE(vector<T> &v) {
    return MaxE(v, 0, (ll)v.size() - 1);
}
template<class T> inline T MinE(vector<T> &v) {
    return MinE(v, 0, (ll)v.size() - 1);
}
template<class T> inline auto maxe(T &&v, ll S, ll E) {
    return *max_element(ALL(v, S, E));
}
template<class T> inline auto maxe(T &&v) { return *max_element(ALL(v)); }
template<class T> inline auto mine(T &&v, ll S, ll E) {
    return *min_element(ALL(v, S, E));
}
template<class T> inline auto mine(T &&v) { return *min_element(ALL(v)); }
template<class T> inline T Sum(vector<T> &v, ll S, ll E) {
    T s = T();
    rep(i, S, E) s += v[i];
    return s;
}
template<class T> inline T Sum(vector<T> &v) { return Sum(v, 0, v.size() - 1); }
template<class T, class U = typename remove_reference<T>::type::value_type>
inline U sum(T &&v, ll S, ll E) {
    return accumulate(all(v, S, E), U());
}
template<class T> inline auto sum(T &&v) {
    return sum(v, 0, v.end() - v.begin() - 1);
}
template<class T> inline ll sz(T &&v) { return (ll)v.size(); }
inline ll CEIL(ll a, ll b) {
    return (a < 0) ? -(-a / b) : (a + b - 1) / b;
}  // 負もOK
inline ll FLOOR(ll a, ll b) { return -CEIL(-a, b); }  // 負もOK

// pair用テンプレート
template<class T, class S>
inline pair<T, S> &operator+=(pair<T, S> &a, const pair<T, S> &b) {
    a.first += b.first;
    a.second += b.second;
    return a;
}
template<class T, class S>
inline pair<T, S> &operator-=(pair<T, S> &a, const pair<T, S> &b) {
    a.first -= b.first;
    a.second -= b.second;
    return a;
}
template<class T, class S>
inline pair<T, S> &operator*=(pair<T, S> &a, const pair<T, S> &b) {
    a.first *= b.first;
    a.second *= b.second;
    return a;
}
template<class T, class S>
inline pair<T, S> &operator/=(pair<T, S> &a, const pair<T, S> &b) {
    a.first /= b.first;
    a.second /= b.second;
    return a;
}
template<class T, class S>
inline pair<T, S> &operator%=(pair<T, S> &a, const pair<T, S> &b) {
    a.first %= b.first;
    a.second %= b.second;
    return a;
}
template<class T, class S, class R>
inline pair<T, S> &operator+=(pair<T, S> &a, R b) {
    a.first += b;
    a.second += b;
    return a;
}
template<class T, class S, class R>
inline pair<T, S> &operator-=(pair<T, S> &a, R b) {
    a.first -= b;
    a.second -= b;
    return a;
}
template<class T, class S, class R>
inline pair<T, S> &operator*=(pair<T, S> &a, R b) {
    a.first *= b;
    a.second *= b;
    return a;
}
template<class T, class S, class R>
inline pair<T, S> &operator/=(pair<T, S> &a, R b) {
    a.first /= b;
    a.second /= b;
    return a;
}
template<class T, class S, class R>
inline pair<T, S> &operator%=(pair<T, S> &a, R b) {
    a.first %= b;
    a.second %= b;
    return a;
}
template<class T, class S, class R>
inline pair<T, S> operator+(const pair<T, S> &a, R b) {
    pair<T, S> c = a;
    return c += b;
}
template<class T, class S, class R>
inline pair<T, S> operator-(const pair<T, S> &a, R b) {
    pair<T, S> c = a;
    return c -= b;
}
template<class T, class S, class R>
inline pair<T, S> operator*(const pair<T, S> &a, R b) {
    pair<T, S> c = a;
    return c *= b;
}
template<class T, class S, class R>
inline pair<T, S> operator/(const pair<T, S> &a, R b) {
    pair<T, S> c = a;
    return c /= b;
}
template<class T, class S, class R>
inline pair<T, S> operator%(const pair<T, S> &a, R b) {
    pair<T, S> c = a;
    return c %= b;
}
template<class T, class S, class R>
inline pair<T, S> operator-(R b, const pair<T, S> &a) {
    pair<T, S> c = -a;
    return c += b;
}
template<class T, class S>
inline pair<T, S> operator-(const pair<T, S> &a, const pair<T, S> &b) {
    pair<T, S> c = a;
    return c -= b;
}
template<class T, class S> inline pair<T, S> operator-(const pair<T, S> &a) {
    pair<T, S> c = a;
    return c *= (-1);
}
template<class T, class S>
inline ostream &operator<<(ostream &os, const pair<T, S> &a) {
    return os << a.first << ' ' << a.second;
}

// tuple用テンプレート 出力用のみ
template<class T, class S, class R>
inline ostream &operator<<(ostream &os, const tuple<T, S, R> &a) {
    return os << get<0>(a) << ' ' << get<1>(a) << ' ' << get<2>(a);
}
template<class T, class S, class R, class Q>
inline ostream &operator<<(ostream &os, const tuple<T, S, R, Q> &a) {
    return os << get<0>(a) << ' ' << get<1>(a) << ' ' << get<2>(a) << ' '
              << get<3>(a);
}

// vector用テンプレート
template<class T>
inline vector<T> &operator+=(vector<T> &a, const vector<T> &b) {
    for (ll i = 0; i < (ll)a.size(); i++) a[i] += b[i];
    return a;
}
template<class T>
inline vector<T> &operator-=(vector<T> &a, const vector<T> &b) {
    for (ll i = 0; i < (ll)a.size(); i++) a[i] -= b[i];
    return a;
}
template<class T>
inline vector<T> &operator*=(vector<T> &a, const vector<T> &b) {
    for (ll i = 0; i < (ll)a.size(); i++) a[i] *= b[i];
    return a;
}
template<class T>
inline vector<T> &operator/=(vector<T> &a, const vector<T> &b) {
    for (ll i = 0; i < (ll)a.size(); i++) a[i] /= b[i];
    return a;
}
template<class T>
inline vector<T> &operator%=(vector<T> &a, const vector<T> &b) {
    for (ll i = 0; i < (ll)a.size(); i++) a[i] %= b[i];
    return a;
}
template<class T, class S> inline vector<T> &operator+=(vector<T> &a, S b) {
    for (T &e : a) e += b;
    return a;
}
template<class T, class S> inline vector<T> &operator-=(vector<T> &a, S b) {
    for (T &e : a) e -= b;
    return a;
}
template<class T, class S> inline vector<T> &operator*=(vector<T> &a, S b) {
    for (T &e : a) e *= b;
    return a;
}
template<class T, class S> inline vector<T> &operator/=(vector<T> &a, S b) {
    for (T &e : a) e /= b;
    return a;
}
template<class T, class S> inline vector<T> &operator%=(vector<T> &a, S b) {
    for (T &e : a) e %= b;
    return a;
}
template<class T, class S> inline vector<T> operator+(const vector<T> &a, S b) {
    vector<T> c = a;
    return c += b;
}
template<class T, class S> inline vector<T> operator-(const vector<T> &a, S b) {
    vector<T> c = a;
    return c -= b;
}
template<class T, class S> inline vector<T> operator*(const vector<T> &a, S b) {
    vector<T> c = a;
    return c *= b;
}
template<class T, class S> inline vector<T> operator/(const vector<T> &a, S b) {
    vector<T> c = a;
    return c /= b;
}
template<class T, class S> inline vector<T> operator%(const vector<T> &a, S b) {
    vector<T> c = a;
    return c %= b;
}
template<class T, class S> inline vector<T> operator-(S b, const vector<T> &a) {
    vector<T> c = -a;
    return c += b;
}
template<class T>
inline vector<T> operator-(const vector<T> &a, const vector<T> &b) {
    vector<T> c = a;
    return c -= b;
}
template<class T> inline vector<T> operator-(const vector<T> &a) {
    vector<T> c = a;
    return c *= (-1);
}
template<class T> inline ostream &operator<<(ostream &os, const vector<T> &a) {
    for (ll i = 0; i < (ll)a.size(); i++) os << (i > 0 ? " " : "") << a[i];
    return os;
}

// array用テンプレート
template<class T, size_t S>
inline array<T, S> &operator+=(array<T, S> &a, const array<T, S> &b) {
    for (ll i = 0; i < (ll)S; i++) a[i] += b[i];
    return a;
}
template<class T, size_t S>
inline array<T, S> &operator-=(array<T, S> &a, const array<T, S> &b) {
    for (ll i = 0; i < (ll)S; i++) a[i] -= b[i];
    return a;
}
template<class T, size_t S>
inline array<T, S> &operator*=(array<T, S> &a, const array<T, S> &b) {
    for (ll i = 0; i < (ll)S; i++) a[i] *= b[i];
    return a;
}
template<class T, size_t S>
inline array<T, S> &operator/=(array<T, S> &a, const array<T, S> &b) {
    for (ll i = 0; i < (ll)S; i++) a[i] /= b[i];
    return a;
}
template<class T, size_t S>
inline array<T, S> &operator%=(array<T, S> &a, const array<T, S> &b) {
    for (ll i = 0; i < (ll)S; i++) a[i] %= b[i];
    return a;
}
template<class T, size_t S, class R>
inline array<T, S> &operator+=(array<T, S> &a, R b) {
    for (T &e : a) e += b;
    return a;
}
template<class T, size_t S, class R>
inline array<T, S> &operator-=(array<T, S> &a, R b) {
    for (T &e : a) e -= b;
    return a;
}
template<class T, size_t S, class R>
inline array<T, S> &operator*=(array<T, S> &a, R b) {
    for (T &e : a) e *= b;
    return a;
}
template<class T, size_t S, class R>
inline array<T, S> &operator/=(array<T, S> &a, R b) {
    for (T &e : a) e /= b;
    return a;
}
template<class T, size_t S, class R>
inline array<T, S> &operator%=(array<T, S> &a, R b) {
    for (T &e : a) e %= b;
    return a;
}
template<class T, size_t S, class R>
inline array<T, S> operator+(const array<T, S> &a, R b) {
    array<T, S> c = a;
    return c += b;
}
template<class T, size_t S, class R>
inline array<T, S> operator-(const array<T, S> &a, R b) {
    array<T, S> c = a;
    return c -= b;
}
template<class T, size_t S, class R>
inline array<T, S> operator*(const array<T, S> &a, R b) {
    array<T, S> c = a;
    return c *= b;
}
template<class T, size_t S, class R>
inline array<T, S> operator/(const array<T, S> &a, R b) {
    array<T, S> c = a;
    return c /= b;
}
template<class T, size_t S, class R>
inline array<T, S> operator%(const array<T, S> &a, R b) {
    array<T, S> c = a;
    return c %= b;
}
template<class T, size_t S, class R>
inline array<T, S> operator-(R b, const array<T, S> &a) {
    array<T, S> c = -a;
    return c += b;
}
template<class T, size_t S>
inline array<T, S> operator-(const array<T, S> &a, const array<T, S> &b) {
    array<T, S> c = a;
    return c -= b;
}
template<class T, size_t S> inline array<T, S> operator-(const array<T, S> &a) {
    array<T, S> c = a;
    return c *= (-1);
}
template<class T, size_t S>
inline ostream &operator<<(ostream &os, const array<T, S> &a) {
    for (ll i = 0; i < (ll)S; i++) os << (i > 0 ? " " : "") << a[i];
    return os;
}

template<class T, size_t S, class R> struct view1d;
template<class T, size_t S, class R> struct view1dIter {
    view1d<T, S, R> *vw = nullptr;
    ll idx = INF;
    view1dIter() {}
    view1dIter(view1d<T, S, R> *vw_, ll idx_) : vw(vw_), idx(idx_) {}
    view1dIter(const view1dIter<T, S, R> &it) : vw(it.vw), idx(it.idx) {}
    R &operator*() { return (*vw)[idx]; }
    R &operator*() const { return (*vw)[idx]; }
    R &operator[](ll i) { return (*vw)[idx + i]; }
    R &operator[](ll i) const { return (*vw)[idx + i]; }
    auto &operator++() {
        idx++;
        return *this;
    }
    auto &operator--() {
        idx--;
        return *this;
    }
    auto operator++(int) {
        auto it = *this;
        idx++;
        return it;
    }
    auto operator--(int) {
        auto it = *this;
        idx--;
        return it;
    }
    auto &operator+=(ll n) {
        idx += n;
        return *this;
    }
    auto &operator-=(ll n) {
        idx -= n;
        return *this;
    }
    auto operator+(ll n) {
        auto it = *this;
        return it += n;
    }
    auto operator-(ll n) {
        auto it = *this;
        return it -= n;
    }
    ll operator-(const view1dIter<T, S, R> &it) const { return idx - it.idx; }
    bool operator<(const view1dIter<T, S, R> &it) const { return idx < it.idx; }
    bool operator>(const view1dIter<T, S, R> &it) const { return idx > it.idx; }
    bool operator<=(const view1dIter<T, S, R> &it) const {
        return idx <= it.idx;
    }
    bool operator>=(const view1dIter<T, S, R> &it) const {
        return idx >= it.idx;
    }
    bool operator!=(const view1dIter<T, S, R> &it) const {
        return idx != it.idx;
    }
    bool operator==(const view1dIter<T, S, R> &it) const {
        return idx == it.idx;
    }
    using iterator_category = random_access_iterator_tag;
    using value_type = R;
    using difference_type = ll;
    using pointer = R *;
    using reference = R &;
};
template<class T, size_t S, class R> struct view1d {
    using Sll = array<ll, S>;
    T &data;         // 参照先データ
    Sll dsize;       // 参照先データ各軸のサイズ
    Sll s = Sll();   // view先頭
    Sll d = Sll();   // view方向
    ll len;          // view長さ
    R &dummy;        // 範囲外の値参照
    R dummyj = R();  // 範囲外の値実体
    /*---- コンストラクタ ----*/
    view1d(T &v) : data(v), dummy(dummyj) {
        SetDsize(v, dsize);
        d[S - 1] = 1;
        len = dsize[S - 1];
    }
    // このコンストラクタは、マイナス座標指定を末尾にしない(暫定)
    // 代入時Array<ll,2>{...}等と書くため、使い勝手悪い。将来廃止するかも。
    view1d(T &v, Sll s, Sll e, Sll d)
        : data(v), s(s), d(d), len(Len(s, e, d)), dummy(dummyj) {
        SetDsize(v, dsize);
    }
    view1d(T &v, Sll s, Sll d, ll len, R &dmy_)
        : data(v), s(s), d(d), len(len), dummy(dmy_) {
        SetDsize(v, dsize);
    }

    /*---- 演算 ----*/
    template<class Q> auto &operator=(const Q &b) {
        rep(i, 0, len - 1)(*this)[i] = b;
        return *this;
    }
    template<class Q> auto &operator+=(const Q &b) {
        rep(i, 0, len - 1)(*this)[i] += b;
        return *this;
    }
    template<class Q> auto &operator-=(const Q &b) {
        rep(i, 0, len - 1)(*this)[i] -= b;
        return *this;
    }
    template<class Q> auto &operator*=(const Q &b) {
        rep(i, 0, len - 1)(*this)[i] *= b;
        return *this;
    }
    template<class Q> auto &operator/=(const Q &b) {
        rep(i, 0, len - 1)(*this)[i] /= b;
        return *this;
    }
    template<class Q> auto &operator%=(const Q &b) {
        rep(i, 0, len - 1)(*this)[i] %= b;
        return *this;
    }
    auto &operator=(const string &b) { return CpSeq(b); }
    template<size_t Q> auto &operator=(const char (&b)[Q]) {
        return *this = string(b);
    }
    template<class Q> auto &operator=(const vector<Q> &b) { return CpSeq(b); }
    template<class Q> auto &operator+=(const vector<Q> &b) { return PlSeq(b); }
    template<class Q> auto &operator-=(const vector<Q> &b) { return MnSeq(b); }
    template<class Q> auto &operator*=(const vector<Q> &b) { return PrSeq(b); }
    template<class Q> auto &operator/=(const vector<Q> &b) { return DvSeq(b); }
    template<class Q> auto &operator%=(const vector<Q> &b) { return RmSeq(b); }
    template<class Q, size_t P, class O>
    auto &operator=(const view1d<Q, P, O> &b) {
        return CpSeq(b);
    }
    template<class Q, size_t P, class O>
    auto &operator+=(const view1d<Q, P, O> &b) {
        return PlSeq(b);
    }
    template<class Q, size_t P, class O>
    auto &operator-=(const view1d<Q, P, O> &b) {
        return MnSeq(b);
    }
    template<class Q, size_t P, class O>
    auto &operator*=(const view1d<Q, P, O> &b) {
        return PrSeq(b);
    }
    template<class Q, size_t P, class O>
    auto &operator/=(const view1d<Q, P, O> &b) {
        return DvSeq(b);
    }
    template<class Q, size_t P, class O>
    auto &operator%=(const view1d<Q, P, O> &b) {
        return RmSeq(b);
    }
    template<class Q> auto &CpSeq(const Q &b) {
        rep(i, 0, min(sz(b), len) - 1)(*this)[i] = b[i];
        return *this;
    }
    template<class Q> auto &PlSeq(const Q &b) {
        rep(i, 0, min(sz(b), len) - 1)(*this)[i] += b[i];
        return *this;
    }
    template<class Q> auto &MnSeq(const Q &b) {
        rep(i, 0, min(sz(b), len) - 1)(*this)[i] -= b[i];
        return *this;
    }
    template<class Q> auto &PrSeq(const Q &b) {
        rep(i, 0, min(sz(b), len) - 1)(*this)[i] *= b[i];
        return *this;
    }
    template<class Q> auto &DvSeq(const Q &b) {
        rep(i, 0, min(sz(b), len) - 1)(*this)[i] /= b[i];
        return *this;
    }
    template<class Q> auto &RmSeq(const Q &b) {
        rep(i, 0, min(sz(b), len) - 1)(*this)[i] %= b[i];
        return *this;
    }
    // template<class Q,class P> static bool eq(const Q &a,const P &b){
    //	return equals(ALL(a),ALL(b));
    // }
    template<class Q, class P> static bool eq(const Q &a, const P &b) {
        if ((ll)a.size() != (ll)b.size()) return false;
        rep(i, 0, (ll)a.size() - 1) {
            if (a[i] != b[i]) return false;
        }
        return true;
    }
    template<class Q, class P> static bool lt(const Q &a, const P &b) {
        ll n = min((ll)a.size(), (ll)b.size());
        rep(i, 0, n - 1) {
            if (a[i] < b[i]) return true;
            if (a[i] > b[i]) return false;
        }
        return (ll)a.size() < (ll)b.size();
    }
    template<class Q, size_t P, class O>
    bool operator==(const view1d<Q, P, O> &b) {
        return eq(*this, b);
    }
    template<class Q> bool operator==(const Q &b) { return eq(*this, b); }
    template<class Q>
    friend bool operator==(const Q &a, const view1d<T, S, R> &b) {
        return eq(a, b);
    }
    template<size_t Q> bool operator==(const char (&b)[Q]) {
        return eq(*this, string(b));
    }
    template<class Q, size_t P, class O>
    bool operator!=(const view1d<Q, P, O> &b) {
        return !(*this == b);
    }
    template<class Q> bool operator!=(const Q &b) { return !(*this == b); }
    template<class Q>
    friend bool operator!=(const Q &a, const view1d<T, S, R> &b) {
        return !(a == b);
    }
    template<class Q, size_t P, class O>
    bool operator<(const view1d<Q, P, O> &b) {
        return lt(*this, b);
    }
    template<class Q> bool operator<(const Q &b) { return lt(*this, b); }
    template<class Q>
    friend bool operator<(const Q &a, const view1d<T, S, R> &b) {
        return lt(a, b);
    }
    template<class Q, size_t P, class O>
    bool operator>(const view1d<Q, P, O> &b) {
        return lt(b, *this);
    }
    template<class Q> bool operator>(const Q &b) { return lt(b, *this); }
    template<class Q>
    friend bool operator>(const Q &a, const view1d<T, S, R> &b) {
        return lt(b, a);
    }
    template<class Q, size_t P, class O>
    bool operator<=(const view1d<Q, P, O> &b) {
        return !(*this > b);
    }
    template<class Q> bool operator<=(const Q &b) { return !(*this > b); }
    template<class Q>
    friend bool operator<=(const Q &a, const view1d<T, S, R> &b) {
        return !(a > b);
    }
    template<class Q, size_t P, class O>
    bool operator>=(const view1d<Q, P, O> &b) {
        return !(*this < b);
    }
    template<class Q> bool operator>=(const Q &b) { return !(*this < b); }
    template<class Q>
    friend bool operator>=(const Q &a, const view1d<T, S, R> &b) {
        return !(a < b);
    }

    /*---- getter ----*/
    ll size() const { return len; }
    R &operator[](ll i) { return const_cast<R &>(OrgAt(s + d * i)); }
    const R &operator[](ll i) const { return OrgAt(s + d * i); }
    R &at(ll i) {
        if (i < 0) i += len;
        return (*this)[i];
    }
    // vector<R> tov(){ vector<R> vvv(len);  rep(i,0,len-1) vvv[i]=(*this)[i];
    // return vvv; }
    operator vector<R>() {
        vector<R> v(len);
        rep(i, 0, len - 1) v[i] = (*this)[i];
        return v;
    }
    bool contains(R a) {
        rep(i, 0, len - 1) if ((*this)[i] == a) return true;
        return false;
    }
    auto begin() { return view1dIter<T, S, R>(this, 0); }
    auto end() { return view1dIter<T, S, R>(this, len); }
    /*---- view設定 ----*/
    view1d<T, S, R> &dmy(R dmy_) {
        dummy = dmy_;
        return *this;
    }  // ダミー値セット
    template<class... Q>
    view1d<T, S, R> &st(Q... s_) {  // 始点set 負は末尾からの位置
        this->s = RevIfNeg(SllD(s_...));
        this->len = AutoLen(this->s, this->d, this->dsize);
        return *this;
    }
    template<class... Q>
    view1d<T, S, R> &en(Q... e_) {  // 終了条件再設定 負は末尾から
        this->len = Len(s, RevIfNeg(SllD(e_...)), d);
        return *this;
    }
    template<class... Q>
    view1d<T, S, R> &dir(Q... d_) {  // 方向set、長さはdata端まで
        this->d = SllD(d_...);
        this->len = AutoLen(this->s, this->d, this->dsize);
        return *this;
    }
    template<class... Q> view1d<T, S, R> &mv(Q... s_) {
        this->s += SllD(s_...);
        return *this;
    }  // 平行移動
    view1d<T, S, R> &size(ll len_) {
        len = len_;
        return *this;
    }  // 長さset
    template<class Q> view1d<T, S, R> &size(Q &v) {
        len = (ll)v.size();
        return *this;
    }  // 長さset
    view1d<T, S, R> &rev() {
        s += d * (len - 1);
        d *= -1;
        return *this;
    }  // 反転

    /*---- utility ----*/
    template<class Q> inline static ll sz(Q &v) { return (ll)v.size(); }
    Sll RevIfNeg(Sll pos) {  //!< 負なら末尾からの位置に変換
        rep(i, 0, S - 1) if (pos[i] < 0) pos[i] += dsize[i];
        return pos;
    }
    static ll AutoLen(Sll s_, Sll d_,
                      Sll dsz) {  // 位置s_から方向d_ではみ出すまでの長さ
        Sll e = dsz - 1;
        rep(i, 0, S - 1) e[i] *= (d_[i] >= 0);  // 方向が負の軸を0にする
        return Len(s_, e, d_);
    }
    /*---- 先頭位置s、方向d、終了条件eから長さlen計算 ----*/
    // template<size_t Q> static ll Len(array<ll,Q> s,array<ll,Q> e,array<ll,Q>
    // d){ 	ll ret=INF; 	rep(i,0,Q-1) chmin(ret, Len1(s[i],e[i],d[i]));
    // return
    // ret;
    // }
    static ll Len(Sll s, Sll e, Sll d) {
        ll ret = INF;
        rep(i, 0, S - 1) chmin(ret, Len1(s[i], e[i], d[i]));
        return ret;
    }
    static ll Len1(ll s, ll e, ll d) {
        if (d == 0) return INF;
        if (d < 0) {
            s = -s;
            e = -e;
            d = -d;
        }
        if (s > e) return 0;
        return (e - s) / d + 1;
    }
    /*---- 可変長引数をSllに変換 ----*/
    template<class... Q> static Sll SllD(Q... args) {
        return SllRec(0, args...);
    }
    template<class... Q> static Sll SllRec(ll i, ll first, Q... rest) {
        Sll sll = (i == S - 1) ? Sll() : SllRec(i + 1, rest...);
        sll[i] = first;
        return sll;
    }
    static Sll SllRec(ll i) { return Sll(); }
    /*---- dataの位置posの値取得 ----*/
    const R &OrgAt(Sll pos) const {
        rep(i, 0, S - 1) {
            if (pos[i] < 0 || dsize[i] <= pos[i]) return dummy;
        }
        return OrgAt_(data, pos);
    }
    template<class Q> using V = vector<Q>;
    template<class Q> using VV = V<V<Q>>;
    template<class Q> using VVV = V<V<V<Q>>>;
    using Vs = V<string>;
    using VVs = VV<string>;
    using ll1 = array<ll, 1>;
    using ll2 = array<ll, 2>;
    using ll3 = array<ll, 3>;
    auto &OrgAt_(V<R> &dat, ll1 pos) const {
        auto [i] = pos;
        return dat[i];
    }
    auto &OrgAt_(string &dat, ll1 pos) const {
        auto [i] = pos;
        return dat[i];
    }
    auto &OrgAt_(VV<R> &dat, ll2 pos) const {
        auto [i, j] = pos;
        return dat[i][j];
    }
    auto &OrgAt_(Vs &dat, ll2 pos) const {
        auto [i, j] = pos;
        return dat[i][j];
    }
    auto &OrgAt_(VVV<R> &dat, ll3 pos) const {
        auto [i, j, k] = pos;
        return dat[i][j][k];
    }
    auto &OrgAt_(VVs &dat, ll3 pos) const {
        auto [i, j, k] = pos;
        return dat[i][j][k];
    }
    /*---- dataの各軸size取得 ----*/
    static void SetDsize(V<R> &dat, ll1 &dsz) { dsz = {sz(dat)}; }
    static void SetDsize(string &dat, ll1 &dsz) { dsz = {sz(dat)}; }
    static void SetDsize(VV<R> &dat, ll2 &dsz) { dsz = {sz(dat), sz(dat[0])}; }
    static void SetDsize(Vs &dat, ll2 &dsz) { dsz = {sz(dat), sz(dat[0])}; }
    static void SetDsize(VVV<R> &dat, ll3 &dsz) {
        dsz = {sz(dat), sz(dat[0]), sz(dat[0][0])};
    }
    static void SetDsize(VVs &dat, ll3 &dsz) {
        dsz = {sz(dat), sz(dat[0]), sz(dat[0][0])};
    }
    typedef view1dIter<T, S, R> iterator;
    using value_type = R;
};
template<class Q> using V = vector<Q>;
template<class Q> using VV = V<V<Q>>;
template<class Q> using VVV = V<V<V<Q>>>;
template<class T> view1d(VVV<T>) -> view1d<VVV<T>, 3, T>;
template<class T> view1d(VV<T>) -> view1d<VV<T>, 2, T>;
template<class T> view1d(V<T>) -> view1d<V<T>, 1, T>;
;
view1d(VV<string>)->view1d<VV<string>, 3, char>;
;
view1d(V<string>)->view1d<V<string>, 2, char>;
;
view1d(string)->view1d<string, 1, char>;
template<class T, class S> view1d(VVV<T>, S, S, S) -> view1d<VVV<T>, 3, T>;
template<class T, class S> view1d(VV<T>, S, S, S) -> view1d<VV<T>, 2, T>;
template<class T, class S> view1d(V<T>, S, S, S) -> view1d<V<T>, 1, T>;
template<class S> view1d(VV<string>, S, S, S) -> view1d<VV<string>, 3, char>;
template<class S> view1d(V<string>, S, S, S) -> view1d<V<string>, 2, char>;
template<class S> view1d(string, S, S, S) -> view1d<string, 1, char>;

template<class VIEW2D> struct view2dIter {
    VIEW2D *vw = nullptr;
    ll idx = INF;
    view2dIter() {}
    view2dIter(VIEW2D *vw_, ll idx_) : vw(vw_), idx(idx_) {}
    view2dIter(const view2dIter &it) : vw(it.vw), idx(it.idx) {}
    auto &operator*() { return (*vw)[x(idx)][y(idx)]; }
    auto &operator*() const { return (*vw)[x(idx)][y(idx)]; }
    auto &operator[](ll i) { return (*vw)[x(idx + i)][y(idx + i)]; }
    auto &operator[](ll i) const { return (*vw)[x(idx + i)][y(idx + i)]; }
    auto &operator++() {
        idx++;
        return *this;
    }
    auto &operator--() {
        idx--;
        return *this;
    }
    auto operator++(int) {
        auto it = *this;
        idx++;
        return it;
    }
    auto operator--(int) {
        auto it = *this;
        idx--;
        return it;
    }
    auto &operator+=(ll n) {
        idx += n;
        return *this;
    }
    auto &operator-=(ll n) {
        idx -= n;
        return *this;
    }
    auto operator+(ll n) {
        auto it = *this;
        return it += n;
    }
    auto operator-(ll n) {
        auto it = *this;
        return it -= n;
    }
    ll operator-(const view2dIter &it) const { return idx - it.idx; }
    bool operator<(const view2dIter &it) const { return idx < it.idx; }
    bool operator>(const view2dIter &it) const { return idx > it.idx; }
    bool operator<=(const view2dIter &it) const { return idx <= it.idx; }
    bool operator>=(const view2dIter &it) const { return idx >= it.idx; }
    bool operator!=(const view2dIter &it) const { return idx != it.idx; }
    bool operator==(const view2dIter &it) const { return idx == it.idx; }
    ll x(ll i) const { return i / vw->leny(); }
    ll y(ll i) const { return i % vw->leny(); }
    using iterator_category = random_access_iterator_tag;
    using value_type = typename VIEW2D::value_type;
    using difference_type = ll;
    using pointer = value_type *;
    using reference = value_type &;
};

template<class T, size_t S, class R> struct view2d {
    using Sll = array<ll, S>;
    T &data;         // 参照先データ
    Sll dsize;       // 参照先データ各軸のサイズ
    Sll s = Sll();   // view始点
    Sll dx = Sll();  // view x軸方向
    Sll dy = Sll();  // view y軸方向
    ll xl;           // view x軸長さ
    ll yl;           // view y軸長さ
    R dummy = R();   // 範囲外の値
    /*---- コンストラクタ ----*/
    view2d(T &v) : data(v) {
        view1d<T, S, R>::SetDsize(v, dsize);
        dx[S - 2] = 1;
        dy[S - 1] = 1;
        xl = dsize[S - 2];
        yl = dsize[S - 1];
    }
    /*---- 演算 ----*/
    // template<class Q> auto &operator =(const Q &b){ rep(i,0,xl-1) (*this)[i]
    // =b; return *this; } template<class Q,size_t P,class O> auto
    // &operator+=(const view2d<Q,P,O> &b){ 	rep(i,0,xl-1) (*this)[i]
    // return
    // PlSeq(b); }
    /*---- getter ----*/
    ll size() const { return xl; }
    array<ll, 2> shape() const { return {xl, yl}; }
    ll lenx() const { return xl; }
    ll leny() const { return yl; }
    /// pll shape() const { return {xl,yl}; }
    view1d<T, S, R> operator[](ll i) {
        return view1d(data, s + dx * i, dy, yl, dummy);
    }
    const view1d<T, S, R> operator[](ll i) const {
        return view1d(data, s + dx * i, dy, yl, dummy);
    }
    R &at(ll i, ll j) {
        if (i < 0) i += xl;
        if (j < 0) j += yl;
        return (*this)[i][j];
    }
    vector<vector<R>> tovv() {
        vector<vector<R>> vvv(xl);
        /// rep(i,0,xl-1) vvv[i]=(*this)[i].tov();  return vvv;
        rep(i, 0, xl - 1) vvv[i] = (*this)[i];
        return vvv;
    }
    operator vector<vector<R>>() {
        vector<vector<R>> v(xl);
        rep(i, 0, xl - 1) v[i] = (*this)[i];
        return v;
    }
    auto begin() { return view2dIter(this, 0); }
    auto end() { return view2dIter(this, xl * yl); }
    /* よくわからない
    #if defined(_DEBUG)
        void dump() { ::dump(tovv()); }
    #endif
    */
    /*---- view設定 ----*/
    view2d<T, S, R> &dmy(R dmy_) {
        dummy = dmy_;
        return *this;
    }  // ダミー値セット
    template<class... Q>
    view2d<T, S, R> &st(Q... s_) {  // 始点set 負は末尾からの位置
        this->s = RevIfNeg(view1d<T, S, R>::SllD(s_...));
        this->xl = view1d<T, S, R>::AutoLen(this->s, this->dx, this->dsize);
        this->yl = view1d<T, S, R>::AutoLen(this->s, this->dy, this->dsize);
        return *this;
    }
    template<class... Q>
    view2d<T, S, R> &dirx(Q... d_) {  // x軸set、長さはdata端まで
        this->dx = view1d<T, S, R>::SllD(d_...);
        this->xl = view1d<T, S, R>::AutoLen(this->s, this->dx, this->dsize);
        return *this;
    }
    template<class... Q>
    view2d<T, S, R> &diry(Q... d_) {  // y軸set、長さはdata端まで
        this->dy = view1d<T, S, R>::SllD(d_...);
        this->yl = view1d<T, S, R>::AutoLen(this->s, this->dy, this->dsize);
        return *this;
    }
    template<class... Q> view2d<T, S, R> &mv(Q... s_) {  // 平行移動
        this->s += view1d<T, S, R>::SllD(s_...);
        return *this;
    }
    view2d<T, S, R> &lenx(ll xl_) {
        xl = xl_;
        return *this;
    }
    view2d<T, S, R> &leny(ll yl_) {
        yl = yl_;
        return *this;
    }
    view2d<T, S, R> &shape(ll xl_, ll yl_) {
        xl = xl_;
        yl = yl_;
        return *this;
    }
    template<class Q> view2d<T, S, R> &shape(Q &v) {
        xl = v.lenx();
        yl = v.leny();
        return *this;
    }
    view2d<T, S, R> &rot90() {
        s += dx * (xl - 1);
        swap(xl, yl);
        swap(dx, dy);
        dy *= -1;
        return *this;
    }
    view2d<T, S, R> &rot270() {
        s += dy * (yl - 1);
        swap(xl, yl);
        swap(dx, dy);
        dx *= -1;
        return *this;
    }
    view2d<T, S, R> &rot180() {
        s += dx * (xl - 1) + dy * (yl - 1);
        dx *= -1;
        dy *= -1;
        return *this;
    }
    view2d<T, S, R> &revx() {
        s += dx * (xl - 1);
        dx *= -1;
        return *this;
    }
    view2d<T, S, R> &revy() {
        s += dy * (yl - 1);
        dy *= -1;
        return *this;
    }
    view2d<T, S, R> &swapxy() {
        swap(xl, yl);
        swap(dx, dy);
        return *this;
    }  // xy軸入替

    /*---- utility ----*/
    Sll RevIfNeg(Sll pos) {  //!< 負なら末尾からの位置に変換
        rep(i, 0, S - 1) if (pos[i] < 0) pos[i] += dsize[i];
        return pos;
    }
    using value_type = R;
};
template<class T> view2d(VVV<T>) -> view2d<VVV<T>, 3, T>;
template<class T> view2d(VV<T>) -> view2d<VV<T>, 2, T>;
;
view2d(VV<string>)->view2d<VV<string>, 3, char>;
;
view2d(V<string>)->view2d<V<string>, 2, char>;

/*
zipは参照のpairを返す。それをさらに参照するのはまずいので、コピーする。
*/
template<class ZIP> struct zipIter {
    ZIP *z = nullptr;
    ll idx = INF;
    zipIter() {}
    zipIter(ZIP *z_, ll idx_) : z(z_), idx(idx_) {}
    zipIter(const zipIter<ZIP> &it) : z(it.z), idx(it.idx) {}
    auto operator*() { return (*z)[idx]; }        // 参照ではなく値戻し
    auto operator*() const { return (*z)[idx]; }  // 同上
    auto operator[](ll i) { return (*z)[idx + i]; }        // 同上
    auto operator[](ll i) const { return (*z)[idx + i]; }  // 同上
    auto &operator++() {
        idx++;
        return *this;
    }
    auto &operator--() {
        idx--;
        return *this;
    }
    auto operator++(int) {
        auto it = *this;
        idx++;
        return it;
    }
    auto operator--(int) {
        auto it = *this;
        idx--;
        return it;
    }
    auto &operator+=(ll n) {
        idx += n;
        return *this;
    }
    auto &operator-=(ll n) {
        idx -= n;
        return *this;
    }
    auto operator+(ll n) {
        auto it = *this;
        return it += n;
    }
    auto operator-(ll n) {
        auto it = *this;
        return it -= n;
    }
    ll operator-(const zipIter<ZIP> &it) const { return idx - it.idx; }
    bool operator<(const zipIter<ZIP> &it) const { return idx < it.idx; }
    bool operator>(const zipIter<ZIP> &it) const { return idx > it.idx; }
    bool operator<=(const zipIter<ZIP> &it) const { return idx <= it.idx; }
    bool operator>=(const zipIter<ZIP> &it) const { return idx >= it.idx; }
    bool operator!=(const zipIter<ZIP> &it) const { return idx != it.idx; }
    bool operator==(const zipIter<ZIP> &it) const { return idx == it.idx; }
    using iterator_category = random_access_iterator_tag;
    using value_type = typename ZIP::value_type;
    using difference_type = ll;
    using pointer = value_type *;
    using reference = value_type &;
};

template<class T, class S> struct zip2 {
    T &t;
    S &s;
    zip2(T &t_, S &s_) : t(t_), s(s_) {}
    ll size() const { return t.end() - t.begin(); }
    auto operator[](ll i) {
        return make_pair(ref(t.begin()[i]), ref(s.begin()[i]));
    }
    auto operator[](ll i) const {
        return make_pair(ref(t.begin()[i]), ref(s.begin()[i]));
    }
    auto begin() { return zipIter(this, 0); }
    auto end() { return zipIter(this, size()); }
    using value_type = pair<typename T::value_type, typename S::value_type>;
};
template<class T, class S, class R> struct zip3 {
    T &t;
    S &s;
    R &r;
    zip3(T &t_, S &s_, R &r_) : t(t_), s(s_), r(r_) {}
    ll size() const { return t.end() - t.begin(); }
    auto operator[](ll i) {
        return make_tuple(ref(t.begin()[i]), ref(s.begin()[i]),
                          ref(r.begin()[i]));
    }
    auto operator[](ll i) const {
        return make_tuple(ref(t.begin()[i]), ref(s.begin()[i]),
                          ref(r.begin()[i]));
    }
    auto begin() { return zipIter(this, 0); }
    auto end() { return zipIter(this, size()); }
    using value_type = tuple<typename T::value_type, typename S::value_type,
                             typename R::value_type>;
};
#endif  // テンプレートend

#if __has_include(<atcoder/all>)
#include <atcoder/all>
using namespace atcoder;
#endif
struct {
    system_clock::time_point st = system_clock::now();
    ll operator()() const {
        return duration_cast<microseconds>(system_clock::now() - st).count() /
               1000;
    }
} timeget;

template<ll MOD> struct mll_ {
    ll val;
    mll_(ll v = 0) : val(v % MOD) {
        if (val < 0) val += MOD;
    }
    bool isnone() const { return val == -1; }  // true:値なし
    mll_ &none() {
        val = -1;
        return *this;
    }  // 値なしにする
    mll_ operator-() const { return -val; }
    mll_ operator+(const mll_ &b) const { return val + b.val; }
    mll_ operator-(const mll_ &b) const { return val - b.val; }
    mll_ operator*(const mll_ &b) const { return val * b.val; }
    mll_ operator/(const mll_ &b) const { return mll_(*this) /= b; }
    mll_ operator+(ll b) const { return *this + mll_(b); }
    mll_ operator-(ll b) const { return *this - mll_(b); }
    mll_ operator*(ll b) const { return *this * mll_(b); }
    friend mll_ operator+(ll a, const mll_ &b) { return b + a; }
    friend mll_ operator-(ll a, const mll_ &b) { return -b + a; }
    friend mll_ operator*(ll a, const mll_ &b) { return b * a; }
    friend mll_ operator/(ll a, const mll_ &b) { return mll_(a) / b; }
    mll_ &operator+=(const mll_ &b) {
        val = (val + b.val) % MOD;
        return *this;
    }
    mll_ &operator-=(const mll_ &b) {
        val = (val + MOD - b.val) % MOD;
        return *this;
    }
    mll_ &operator*=(const mll_ &b) {
        val = (val * b.val) % MOD;
        return *this;
    }
    mll_ &operator/=(const mll_ &b) {
        ll c = b.val, d = MOD, u = 1, v = 0;
        while (d) {
            ll t = c / d;
            c -= t * d;
            swap(c, d);
            u -= t * v;
            swap(u, v);
        }
        val = val * u % MOD;
        if (val < 0) val += MOD;
        return *this;
    }
    mll_ &operator+=(ll b) { return *this += mll_(b); }
    mll_ &operator-=(ll b) { return *this -= mll_(b); }
    mll_ &operator*=(ll b) { return *this *= mll_(b); }
    mll_ &operator/=(ll b) { return *this /= mll_(b); }
    bool operator==(const mll_ &b) const { return val == b.val; }
    bool operator!=(const mll_ &b) const { return val != b.val; }
    bool operator==(ll b) const { return *this == mll_(b); }
    bool operator!=(ll b) const { return *this != mll_(b); }
    friend bool operator==(ll a, const mll_ &b) { return mll_(a) == b.val; }
    friend bool operator!=(ll a, const mll_ &b) { return mll_(a) != b.val; }
    friend ostream &operator<<(ostream &os, const mll_ &a) {
        return os << a.val;
    }
    friend istream &operator>>(istream &is, mll_ &a) { return is >> a.val; }
    static mll_ Combination(ll a, ll b) {
        chmin(b, a - b);
        if (b < 0) return mll_(0);
        mll_ c = 1, d = 1;
        rep(i, 0, b - 1) c *= a - i;
        rep(i, 0, b - 1) d *= i + 1;
        return c / d;
    }
    enum { modll = MOD };
};

#if 0
#define MODLL (1000000007LL)
#else
#define MODLL (998244353LL)
#endif
using mll = mll_<MODLL>;
using vmll = std::vector<mll>;
using vvmll = std::vector<vmll>;
using vvvmll = std::vector<vvmll>;
using vvvvmll = std::vector<vvvmll>;

//////////////////////////////////////////

template<class T> struct SET : set<T> {
    using P = set<T>;
    typename P::iterator it = P::end();
    template<class... Args> SET(Args... args) : P(args...) {}
    SET(initializer_list<T> a) : P(a.begin(), a.end()) {}
    ll size() const { return (ll)P::size(); }
    bool insert(const T &x) {
        bool r;
        tie(it, r) = P::insert(x);
        return r;
    }
    template<class It> void insert(It st, It en) { P::insert(st, en); }
    void insert(initializer_list<T> a) { P::insert(a.begin(), a.end()); }
    template<class... A> bool emplace(A &&...a) {
        bool r;
        tie(it, r) = P::emplace(a...);
        return r;
    }
    void eraseit() { it = P::erase(it); }
    void find(const T &x) { it = P::find(x); }
    bool contains(const T &x) { return P::count(x) == 1; }
    void lower_bound(const T &x) { it = P::lower_bound(x); }
    void upper_bound(const T &x) { it = P::upper_bound(x); }
    bool isend() { return it == P::end(); }
    T getit() { return *it; }
    T next() { return *(++it); }
    T prev() { return *(--it); }
    bool nextok() { return !isend() && it != --P::end(); }
    bool prevok() { return it != P::begin(); }
    T front() { return *(it = P::begin()); }
    T back() { return *(it = --P::end()); }
    void pop_front() {
        front();
        eraseit();
    }
    void pop_back() {
        back();
        eraseit();
    }
    void push_front(const T &x) { it = P::insert(P::begin(), x); }
    void push_back(const T &x) { it = P::insert(P::end(), x); }
    void push_out(SET &b) {
        b.push_front(back());
        pop_back();
    }
    void pull_in(SET &b) {
        push_back(b.front());
        b.pop_front();
    }
};
/*
front(), back(), pop_front(), pop_back(), contains(x), push_front(x),
push_back(x) ある要素の次、前を連続して得る機能 find(x), next(), prev(),
nextok(), prevok()
*/

void cin2solve() {
    ll a, b, c, k;
    cin >> a >> b >> c >> k;

    set<tuple<ll, ll, ll>> s;
    rep(i, 0, k - 1) {
        if (s.count({a, b, c})) {
            cout << a + b + c << "\n";
            return;
        }
        s.emplace(a, b, c);
        ll x = (b + c) / 2, y = (c + a) / 2, z = (a + b) / 2;
        a = x, b = y, c = z;
    }
    cout << a + b + c << "\n";
    return;
}

//////////////////////////////////////////

int main() {
#if 0
    cin2solve();
    // generand();
#else
    ll t;
    cin >> t;
    rep(i, 0, t - 1) {
        cin2solve();
        // generand();
    }
#endif
    // cerr << timeget() <<"ms"<< endl;
    return 0;
}
yukicoder

結果

テストケース

ソースコード
