#if !defined(MYLOCAL) // 提出時用テンプレート #pragma GCC optimize("Ofast") #include #if !defined(_MSC_VER) && __has_include() #include using namespace atcoder; #endif using namespace std; using ll = long long; using dd = double; using vll = vector; using vdd = vector

; using vvll = vector; using vvdd = vector; using vvvll = vector; using vvvdd = vector; using vvvvll = vector; using pll = pair; using tll = tuple; using qll = tuple; using vpll = vector; using vtll = vector; using vqll = vector; using vvpll = vector; using vvtll = vector; using vvqll = vector; using namespace chrono; constexpr ll LLINF = 1001001001001001001; struct Fast { Fast() { cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(numeric_limits::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 rep1(n) for (ll i = 0; i < (n); ++i) #define rep2(i, n) for (ll i = 0; i < (n); ++i) #define rep3(i, a, b) for (ll i = (a); i < (b); ++i) #define rep4(i, a, b, c) for (ll i = (a); i < (b); i += (c)) #define rep(...) overload4(__VA_ARGS__, rep4, rep3, rep2, rep1)(__VA_ARGS__) #define rrep1(n) for (ll i = n - 1; i >= 0; --i) #define rrep2(i, n) for (ll i = n - 1; i >= 0; --i) #define rrep3(i, a, b) for (ll i = b - 1; i >= a; --i) #define rrep(...) overload3(__VA_ARGS__, rrep3, rrep2, rrep1)(__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 inline bool chmax(T &a, T b) { if (a < b) { a = b; return true; } return false; } template inline bool chmin(T &a, T b) { if (a > b) { a = b; return true; } return false; } template inline T MaxE(vector &v, ll S, ll E) { T m = v[S]; rep(i, S, E) chmax(m, v[i]); return m; } template inline T MinE(vector &v, ll S, ll E) { T m = v[S]; rep(i, S, E) chmin(m, v[i]); return m; } template inline T MaxE(vector &v) { return MaxE(v, 0, (ll)v.size() - 1); } template inline T MinE(vector &v) { return MinE(v, 0, (ll)v.size() - 1); } template inline auto maxe(T &&v, ll S, ll E) { return *max_element(ALL(v, S, E)); } template inline auto maxe(T &&v) { return *max_element(ALL(v)); } template inline auto mine(T &&v, ll S, ll E) { return *min_element(ALL(v, S, E)); } template inline auto mine(T &&v) { return *min_element(ALL(v)); } template inline T Sum(vector &v, ll S, ll E) { T s = T(); rep(i, S, E) s += v[i]; return s; } template inline T Sum(vector &v) { return Sum(v, 0, v.size() - 1); } template::type::value_type> inline U sum(T &&v, ll S, ll E) { return accumulate(all(v, S, E), U()); } template inline auto sum(T &&v) { return sum(v, 0, v.end() - v.begin() - 1); } template 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 inline pair &operator+=(pair &a, const pair &b) { a.first += b.first; a.second += b.second; return a; } template inline pair &operator-=(pair &a, const pair &b) { a.first -= b.first; a.second -= b.second; return a; } template inline pair &operator*=(pair &a, const pair &b) { a.first *= b.first; a.second *= b.second; return a; } template inline pair &operator/=(pair &a, const pair &b) { a.first /= b.first; a.second /= b.second; return a; } template inline pair &operator%=(pair &a, const pair &b) { a.first %= b.first; a.second %= b.second; return a; } template inline pair &operator+=(pair &a, R b) { a.first += b; a.second += b; return a; } template inline pair &operator-=(pair &a, R b) { a.first -= b; a.second -= b; return a; } template inline pair &operator*=(pair &a, R b) { a.first *= b; a.second *= b; return a; } template inline pair &operator/=(pair &a, R b) { a.first /= b; a.second /= b; return a; } template inline pair &operator%=(pair &a, R b) { a.first %= b; a.second %= b; return a; } template inline pair operator+(const pair &a, R b) { pair c = a; return c += b; } template inline pair operator-(const pair &a, R b) { pair c = a; return c -= b; } template inline pair operator*(const pair &a, R b) { pair c = a; return c *= b; } template inline pair operator/(const pair &a, R b) { pair c = a; return c /= b; } template inline pair operator%(const pair &a, R b) { pair c = a; return c %= b; } template inline pair operator-(R b, const pair &a) { pair c = -a; return c += b; } template inline pair operator-(const pair &a, const pair &b) { pair c = a; return c -= b; } template inline pair operator-(const pair &a) { pair c = a; return c *= (-1); } template inline ostream &operator<<(ostream &os, const pair &a) { return os << a.first << ' ' << a.second; } // tuple用テンプレート出力用のみ template inline ostream &operator<<(ostream &os, const tuple &a) { return os << get<0>(a) << ' ' << get<1>(a) << ' ' << get<2>(a); } template inline ostream &operator<<(ostream &os, const tuple &a) { return os << get<0>(a) << ' ' << get<1>(a) << ' ' << get<2>(a) << ' ' << get<3>(a); } // vector用テンプレート template inline vector &operator+=(vector &a, const vector &b) { for (ll i = 0; i < (ll)a.size(); i++) a[i] += b[i]; return a; } template inline vector &operator-=(vector &a, const vector &b) { for (ll i = 0; i < (ll)a.size(); i++) a[i] -= b[i]; return a; } template inline vector &operator*=(vector &a, const vector &b) { for (ll i = 0; i < (ll)a.size(); i++) a[i] *= b[i]; return a; } template inline vector &operator/=(vector &a, const vector &b) { for (ll i = 0; i < (ll)a.size(); i++) a[i] /= b[i]; return a; } template inline vector &operator%=(vector &a, const vector &b) { for (ll i = 0; i < (ll)a.size(); i++) a[i] %= b[i]; return a; } template inline vector &operator+=(vector &a, S b) { for (T &e : a) e += b; return a; } template inline vector &operator-=(vector &a, S b) { for (T &e : a) e -= b; return a; } template inline vector &operator*=(vector &a, S b) { for (T &e : a) e *= b; return a; } template inline vector &operator/=(vector &a, S b) { for (T &e : a) e /= b; return a; } template inline vector &operator%=(vector &a, S b) { for (T &e : a) e %= b; return a; } template inline vector operator+(const vector &a, S b) { vector c = a; return c += b; } template inline vector operator-(const vector &a, S b) { vector c = a; return c -= b; } template inline vector operator*(const vector &a, S b) { vector c = a; return c *= b; } template inline vector operator/(const vector &a, S b) { vector c = a; return c /= b; } template inline vector operator%(const vector &a, S b) { vector c = a; return c %= b; } template inline vector operator-(S b, const vector &a) { vector c = -a; return c += b; } template inline vector operator-(const vector &a, const vector &b) { vector c = a; return c -= b; } template inline vector operator-(const vector &a) { vector c = a; return c *= (-1); } template inline ostream &operator<<(ostream &os, const vector &a) { for (ll i = 0; i < (ll)a.size(); i++) os << (i > 0 ? " " : "") << a[i]; return os; } // array用テンプレート template inline array &operator+=(array &a, const array &b) { for (ll i = 0; i < (ll)S; i++) a[i] += b[i]; return a; } template inline array &operator-=(array &a, const array &b) { for (ll i = 0; i < (ll)S; i++) a[i] -= b[i]; return a; } template inline array &operator*=(array &a, const array &b) { for (ll i = 0; i < (ll)S; i++) a[i] *= b[i]; return a; } template inline array &operator/=(array &a, const array &b) { for (ll i = 0; i < (ll)S; i++) a[i] /= b[i]; return a; } template inline array &operator%=(array &a, const array &b) { for (ll i = 0; i < (ll)S; i++) a[i] %= b[i]; return a; } template inline array &operator+=(array &a, R b) { for (T &e : a) e += b; return a; } template inline array &operator-=(array &a, R b) { for (T &e : a) e -= b; return a; } template inline array &operator*=(array &a, R b) { for (T &e : a) e *= b; return a; } template inline array &operator/=(array &a, R b) { for (T &e : a) e /= b; return a; } template inline array &operator%=(array &a, R b) { for (T &e : a) e %= b; return a; } template inline array operator+(const array &a, R b) { array c = a; return c += b; } template inline array operator-(const array &a, R b) { array c = a; return c -= b; } template inline array operator*(const array &a, R b) { array c = a; return c *= b; } template inline array operator/(const array &a, R b) { array c = a; return c /= b; } template inline array operator%(const array &a, R b) { array c = a; return c %= b; } template inline array operator-(R b, const array &a) { array c = -a; return c += b; } template inline array operator-(const array &a, const array &b) { array c = a; return c -= b; } template inline array operator-(const array &a) { array c = a; return c *= (-1); } template inline ostream &operator<<(ostream &os, const array &a) { for (ll i = 0; i < (ll)S; i++) os << (i > 0 ? " " : "") << a[i]; return os; } template struct view1d; template struct view1dIter { view1d *vw = nullptr; ll idx = LLINF; view1dIter() {} view1dIter(view1d *vw_, ll idx_) : vw(vw_), idx(idx_) {} view1dIter(const view1dIter &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 &it) const { return idx - it.idx; } bool operator<(const view1dIter &it) const { return idx < it.idx; } bool operator>(const view1dIter &it) const { return idx > it.idx; } bool operator<=(const view1dIter &it) const { return idx <= it.idx; } bool operator>=(const view1dIter &it) const { return idx >= it.idx; } bool operator!=(const view1dIter &it) const { return idx != it.idx; } bool operator==(const view1dIter &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 struct view1d { using Sll = array; 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{...}等と書くため、使い勝手悪い。将来廃止するかも。 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 auto &operator=(const Q &b) { rep(i, 0, len - 1)(*this)[i] = b; return *this; } template auto &operator+=(const Q &b) { rep(i, 0, len - 1)(*this)[i] += b; return *this; } template auto &operator-=(const Q &b) { rep(i, 0, len - 1)(*this)[i] -= b; return *this; } template auto &operator*=(const Q &b) { rep(i, 0, len - 1)(*this)[i] *= b; return *this; } template auto &operator/=(const Q &b) { rep(i, 0, len - 1)(*this)[i] /= b; return *this; } template auto &operator%=(const Q &b) { rep(i, 0, len - 1)(*this)[i] %= b; return *this; } auto &operator=(const string &b) { return CpSeq(b); } template auto &operator=(const char (&b)[Q]) { return *this = string(b); } template auto &operator=(const vector &b) { return CpSeq(b); } template auto &operator+=(const vector &b) { return PlSeq(b); } template auto &operator-=(const vector &b) { return MnSeq(b); } template auto &operator*=(const vector &b) { return PrSeq(b); } template auto &operator/=(const vector &b) { return DvSeq(b); } template auto &operator%=(const vector &b) { return RmSeq(b); } template auto &operator=(const view1d &b) { return CpSeq(b); } template auto &operator+=(const view1d &b) { return PlSeq(b); } template auto &operator-=(const view1d &b) { return MnSeq(b); } template auto &operator*=(const view1d &b) { return PrSeq(b); } template auto &operator/=(const view1d &b) { return DvSeq(b); } template auto &operator%=(const view1d &b) { return RmSeq(b); } template auto &CpSeq(const Q &b) { rep(i, 0, min(sz(b), len) - 1)(*this)[i] = b[i]; return *this; } template auto &PlSeq(const Q &b) { rep(i, 0, min(sz(b), len) - 1)(*this)[i] += b[i]; return *this; } template auto &MnSeq(const Q &b) { rep(i, 0, min(sz(b), len) - 1)(*this)[i] -= b[i]; return *this; } template auto &PrSeq(const Q &b) { rep(i, 0, min(sz(b), len) - 1)(*this)[i] *= b[i]; return *this; } template auto &DvSeq(const Q &b) { rep(i, 0, min(sz(b), len) - 1)(*this)[i] /= b[i]; return *this; } template auto &RmSeq(const Q &b) { rep(i, 0, min(sz(b), len) - 1)(*this)[i] %= b[i]; return *this; } // template static bool eq(const Q &a,const P &b){ // return equals(ALL(a),ALL(b)); // } template 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 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 bool operator==(const view1d &b) { return eq(*this, b); } template bool operator==(const Q &b) { return eq(*this, b); } template friend bool operator==(const Q &a, const view1d &b) { return eq(a, b); } template bool operator==(const char (&b)[Q]) { return eq(*this, string(b)); } template bool operator!=(const view1d &b) { return !(*this == b); } template bool operator!=(const Q &b) { return !(*this == b); } template friend bool operator!=(const Q &a, const view1d &b) { return !(a == b); } template bool operator<(const view1d &b) { return lt(*this, b); } template bool operator<(const Q &b) { return lt(*this, b); } template friend bool operator<(const Q &a, const view1d &b) { return lt(a, b); } template bool operator>(const view1d &b) { return lt(b, *this); } template bool operator>(const Q &b) { return lt(b, *this); } template friend bool operator>(const Q &a, const view1d &b) { return lt(b, a); } template bool operator<=(const view1d &b) { return !(*this > b); } template bool operator<=(const Q &b) { return !(*this > b); } template friend bool operator<=(const Q &a, const view1d &b) { return !(a > b); } template bool operator>=(const view1d &b) { return !(*this < b); } template bool operator>=(const Q &b) { return !(*this < b); } template friend bool operator>=(const Q &a, const view1d &b) { return !(a < b); } /*---- getter ----*/ ll size() const { return len; } R &operator[](ll i) { return const_cast(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 tov(){ vector vvv(len); rep(i,0,len-1) vvv[i]=(*this)[i]; // return vvv; } operator vector() { vector 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(this, 0); } auto end() { return view1dIter(this, len); } /*---- view設定 ----*/ view1d &dmy(R dmy_) { dummy = dmy_; return *this; } // ダミー値セット template view1d &st(Q... s_) { // 始点set 負は末尾からの位置 this->s = RevIfNeg(SllD(s_...)); this->len = AutoLen(this->s, this->d, this->dsize); return *this; } template view1d &en(Q... e_) { // 終了条件再設定負は末尾から this->len = Len(s, RevIfNeg(SllD(e_...)), d); return *this; } template view1d &dir(Q... d_) { // 方向set、長さはdata端まで this->d = SllD(d_...); this->len = AutoLen(this->s, this->d, this->dsize); return *this; } template view1d &mv(Q... s_) { this->s += SllD(s_...); return *this; } // 平行移動 view1d &size(ll len_) { len = len_; return *this; } // 長さset template view1d &size(Q &v) { len = (ll)v.size(); return *this; } // 長さset view1d &rev() { s += d * (len - 1); d *= -1; return *this; } // 反転 /*---- utility ----*/ template 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 static ll Len(array s,array e,array // d){ ll ret=LLINF; 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 = LLINF; 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 LLINF; if (d < 0) { s = -s; e = -e; d = -d; } if (s > e) return 0; return (e - s) / d + 1; } /*---- 可変長引数をSllに変換 ----*/ template static Sll SllD(Q... args) { return SllRec(0, args...); } template 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 using V = vector; template using VV = V>; template using VVV = V>>; using Vs = V; using VVs = VV; using ll1 = array; using ll2 = array; using ll3 = array; auto &OrgAt_(V &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 &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 &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 &dat, ll1 &dsz) { dsz = {sz(dat)}; } static void SetDsize(string &dat, ll1 &dsz) { dsz = {sz(dat)}; } static void SetDsize(VV &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 &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 iterator; using value_type = R; }; template using V = vector; template using VV = V>; template using VVV = V>>; template view1d(VVV) -> view1d, 3, T>; template view1d(VV) -> view1d, 2, T>; template view1d(V) -> view1d