#line 1 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/common/template.hpp" #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #line 1 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/library/cpp-dump.hpp" #ifndef ONLINE_JUDGE #else #define dump(...) #define CPP_DUMP_SET_OPTION(...) #define CPP_DUMP_SET_OPTION_GLOBAL(...) #define CPP_DUMP_DEFINE_EXPORT_OBJECT(...) #define CPP_DUMP_DEFINE_EXPORT_ENUM(...) #define CPP_DUMP_DEFINE_EXPORT_OBJECT_GENERIC(...) #endif void init_cpp_dump() { // ログのラベルを行番号にする CPP_DUMP_SET_OPTION(log_label_func, cp::log_label::filename()); // 記号に色を付ける CPP_DUMP_SET_OPTION(es_value, (cp::types::es_value_t{ "\x1b[02m", // log: 灰色 "\x1b[34m", // expression: 青 "\x1b[38;5;39m", // reserved: 明るい青 "\x1b[38;5;150m", // number: 明るい緑 "\x1b[38;5;172m", // character: オレンジ "\x1b[38;5;220m", // escaped_char: 明るいオレンジ "\x1b[02m", // op: 灰色 "\x1b[32m", // identifier: 緑 "\x1b[96m", // member: 明るいシアン "\x1b[31m", // unsupported: 赤 { "\x1b[33m", // bracket_by_depth[0]: 黄色 "\x1b[35m", // bracket_by_depth[1]: マゼンタ "\x1b[36m", // bracket_by_depth[2]: シアン }, "\x1b[02m", // class_op: 灰色 "\x1b[02m", // member_op: 灰色 "", // number_op: デフォルト })); CPP_DUMP_SET_OPTION(detailed_class_es, true); CPP_DUMP_SET_OPTION(detailed_member_es, true); CPP_DUMP_SET_OPTION(detailed_number_es, true); CPP_DUMP_SET_OPTION(es_style, cp::types::es_style_t::by_syntax); } #line 7 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/common/template.hpp" #line 1 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/common/alias.hpp" #include // #include #line 1 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/bits/stdc++.h" // C++ includes used for precompiling -*- C++ -*- // Copyright (C) 2003-2022 Free Software Foundation, Inc. // // This file is part of the GNU ISO C++ Library. This library is free // software; you can redistribute it and/or modify it under the // terms of the GNU General Public License as published by the // Free Software Foundation; either version 3, or (at your option) // any later version. // This library is distributed in the hope that it will be useful, // but WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the // GNU General Public License for more details. // Under Section 7 of GPL version 3, you are granted additional // permissions described in the GCC Runtime Library Exception, version // 3.1, as published by the Free Software Foundation. // You should have received a copy of the GNU General Public License and // a copy of the GCC Runtime Library Exception along with this program; // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see // . /** @file stdc++.h * This is an implementation file for a precompiled header. */ // 17.4.1.2 Headers // C #ifndef _GLIBCXX_NO_ASSERT #include #endif #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #if __cplusplus >= 201103L #include #include #include #include #include #include #include #include #endif // C++ #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #if __cplusplus >= 201103L #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #endif #if __cplusplus >= 201402L #include #endif #if __cplusplus >= 201703L #include #include // #include #include #include #include #include #include #endif #if __cplusplus >= 202002L #include #include #include #include #if __cpp_impl_coroutine # include #endif #include #include #include #include #include #include #include #include #include #endif #if __cplusplus > 202002L #include #include #if __has_include() # include #endif #include #endif #line 7 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/common/alias.hpp" using namespace std; // using namespace std::views; // using namespace boost::multiprecision; // --- 型エイリアス --- using ll = long long; using ull = unsigned long long; template using vec = vector; template using vvec = vector>; template using vvvec = vector>>; template using p_queue = priority_queue; template using rp_queue = priority_queue, greater>; using bint = boost::multiprecision::cpp_int; // --- 黒魔術 --- #define int ll // --- 制御マクロ --- #define rep(i, n) for (ll i = 0; i < n; ++i) #define all(v) begin(v), end(v) // #define BIT(n) (1LL << (n)) #define MAX(type) numeric_limits::max() #define MIN(type) numeric_limits::min() #define yes cout << "Yes" << endl #define no cout << "No" << endl #define pb push_back #define mp make_pair #define fir first #define sec second // --- 定数 --- constexpr ll INF = 1LL << 60; // constexpr ll INF = numeric_limits::max(); inline signed bit_width(ll x) { return bit_width((ull)x); } inline ull bit_ceil(ll x) { return bit_ceil((ull)x); } #line 9 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/common/template.hpp" #line 1 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/common/concepts.hpp" template concept addable = requires(T a, T b) { { a + b } -> convertible_to; }; #line 10 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/common/template.hpp" #line 1 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/common/debug.hpp" // --- デバッグ --- #ifndef ONLINE_JUDGE #else #define line_debug() ; #define coutd(x) ; #define printd(x) ; #endif #line 11 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/common/template.hpp" #line 1 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/common/int128_t.hpp" using int128_t = __int128_t; using uint128_t = __uint128_t; using lll = int128_t; using ulll = uint128_t; // https://kenkoooo.hatenablog.com/entry/2016/11/30/163533 ostream &operator<<(ostream &dest, lll value) { ostream::sentry s(dest); if (s) { lll tmp = value < 0 ? -value : value; char buffer[128]; char *d = end(buffer); do { --d; *d = "0123456789"[tmp % 10]; tmp /= 10; } while (tmp != 0); if (value < 0) { --d; *d = '-'; } int len = end(buffer) - d; if (dest.rdbuf()->sputn(d, len) != len) { dest.setstate(ios_base::badbit); } } return dest; } lll string_to_lll(string &s) { lll ret = 0; for (int i = 0; i < s.length(); i++) if ('0' <= s[i] && s[i] <= '9') ret = 10 * ret + s[i] - '0'; return ret; } istream &operator>>(istream &src, lll &value) { string s; src >> s; value = string_to_lll(s); return src; } #line 12 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/common/template.hpp" #line 1 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/common/print.hpp" // --------------- // ----- TOC ----- template ostream &operator<<(ostream &os, const pair &p); template istream &operator>>(istream &is, pair &p); template ostream &operator<<(ostream &os, const vector &v); template ostream &operator<<(ostream &os, const vector> &v); template ostream &operator<<(ostream &os, const vector>> &v); template istream &operator>>(istream &is, vector &v); template ostream &operator<<(ostream &os, const map &mp); template ostream &operator<<(ostream &os, const set &st); template ostream &operator<<(ostream &os, const multiset &st); template ostream &operator<<(ostream &os, queue q); template ostream &operator<<(ostream &os, deque q); template ostream &operator<<(ostream &os, stack st); template ostream &operator<<(ostream &os, priority_queue pq); // --- END TOC --- // --------------- template ostream &operator<<(ostream &os, const pair &p) { os << "(" << p.first << "," << p.second << ")"; return os; } template istream &operator>>(istream &is, pair &p) { is >> p.first >> p.second; return is; } template ostream &operator<<(ostream &os, const vector &v) { os << "["; for (int i = 0; i < (int)v.size(); i++) { os << v[i] << (i + 1 != (int)v.size() ? ", " : "]"); } return os; } template ostream &operator<<(ostream &os, const vector> &v) { for (int i = 0; i < (int)v.size(); i++) { os << v[i] << endl; } return os; } template ostream &operator<<(ostream &os, const vector>> &v) { for (int i = 0; i < (int)v.size(); i++) { os << "i = " << i << endl; os << v[i]; } return os; } template istream &operator>>(istream &is, vector &v) { for (T &in : v) is >> in; return is; } template ostream &operator<<(ostream &os, const map &mp) { for (auto &[key, val] : mp) { os << key << ":" << val << " "; } return os; } template ostream &operator<<(ostream &os, const set &st) { os << "{"; auto itr = st.begin(); for (int i = 0; i < (int)st.size(); i++) { os << *itr << (i + 1 != (int)st.size() ? ", " : "}"); itr++; } return os; } template ostream &operator<<(ostream &os, const multiset &st) { auto itr = st.begin(); for (int i = 0; i < (int)st.size(); i++) { os << *itr << (i + 1 != (int)st.size() ? " " : ""); itr++; } return os; } template ostream &operator<<(ostream &os, queue q) { while (q.size()) { os << q.front() << " "; q.pop(); } return os; } template ostream &operator<<(ostream &os, deque q) { while (q.size()) { os << q.front() << " "; q.pop_front(); } return os; } template ostream &operator<<(ostream &os, stack st) { while (st.size()) { os << st.top() << " "; st.pop(); } return os; } template ostream &operator<<(ostream &os, priority_queue pq) { while (pq.size()) { os << pq.top() << " "; pq.pop(); } return os; } #line 13 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/common/template.hpp" #line 1 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/common/util.hpp" // --- Utils --- // 二分探索 template inline T bin_search(T ok, T ng, const function is_ok) { assert(is_ok(ok)); assert(!is_ok(ng)); assert(ok < ng); while (abs(ok - ng) > 1) { T mid = (ok + ng) / 2; if (is_ok(mid)) ok = mid; else ng = mid; } return ok; } // 順列全探索 inline void rep_perm(int n, function &)> f) { vec v(n); iota(v.begin(), v.end(), 0); do { f(v); } while (next_permutation(v.begin(), v.end())); } inline void rep_bit(int n, function f) { rep(i, 1LL << n) f(i); } // 配列 to string template inline string join(const vec &v, string sep = " ") { string res = ""; rep(i, v.size()) res += to_string(v[i]) + (i == v.size() - 1 ? "" : sep); return res; } template inline void join_out(ostream &os, const vec &v, string sep = " ", string end = "\n") { int n = v.size(); rep(i, n) os << v[i] << (i == n - 1 ? end : sep); } template inline void transform(vec &src, function f) { for (auto &val : src) f(val); } // ベース指定ceil inline ll ceil(ll x, ll base) { return (x + base - 1) / base * base; } // ベース指定floor inline ll floor(ll x, ll base) { return x / base * base; } // 合計値を求める // ll sum(const vec &v) { return accumulate(all(v), 0LL); } template T sum(const vec &v) { return accumulate(all(v), T()); } // 可変引数min template auto min(T... a) { return min(initializer_list>{a...}); } // 可変引数max template auto max(T... a) { return max(initializer_list>{a...}); } template bool chmax(T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; } template bool chmin(T &a, const T &b) { if (b < a) { a = b; return 1; } return 0; } // 3項間不等式 // 広義単調増加 inline bool is_increasing(int x, int y, int z) { return x <= y && y <= z; } // 半開区間[x, z)にyが含まれるか? inline bool is_contained(int x, int y, int z) { return x <= y && y < z; } // 頂点(x, y)が範囲に含まれるか inline bool is_contained(int H, int W, int x, int y) { return is_contained(0, x, H) && is_contained(0, y, W); } // rootに対し、aとbが同じ側にあるか (=は含まない) inline bool is_same_side(int root, int a, int b) { return (root < a) == (root < b); } // vector継承にする? template struct vec_accumulate : public vec { explicit vec_accumulate(vec &v) : vec(v.size()) { assert(v.size() > 0); this->at(0) = v[0]; for (int i = 1; i < v.size(); ++i) this->at(i) = this->at(i - 1) + v[i]; } // [0, i]の和 // なので、-1 <= i < size() T operator[](int i) { assert(is_contained(-1, i, this->size())); if (i == -1) return T(); return this->at(i); } }; // vector func template inline void unique_erase(vec &v) { sort(all(v)); v.erase(unique(all(v)), v.end()); } // view struct to_vec_adoptor { friend constexpr auto operator|(std::ranges::viewable_range auto &&r, to_vec_adoptor self) { auto r_common = r | std::views::common; return std::vector(r_common.begin(), r_common.end()); } }; inline constexpr to_vec_adoptor to_vec; void io_setup() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << std::fixed << std::setprecision(15); } #line 14 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/common/template.hpp" #line 1 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/math/pow.hpp" // 繰り返し2乗法 template constexpr T powi(T a, F n) { T ans = 1; while (n > 0) { if (n & 1) ans *= a; a *= a; n >>= 1; } return ans; } template constexpr T pow(T a, F n) { return powi(a, n); } constexpr ll powm(ll a, ll n, const ll mod) { lll ans = 1; while (n > 0) { if (n & 1) ans = ans * a % mod; a = ((lll)a) * a % mod; n >>= 1; } return ans; } #line 16 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/common/template.hpp" #line 2 "/home/zoi/document/kyopro/under_greeen_3/main.cpp" #line 1 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/all.hpp" #line 1 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/2d/all.hpp" #line 1 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/2d/area.hpp" #line 1 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/2d/point.hpp" class Point { public: int x, y; Point() : x(0), y(0) {} Point(int x, int y) : x(x), y(y) {} Point up() const { return Point(x - 1, y); } Point down() const { return Point(x + 1, y); } Point left() const { return Point(x, y - 1); } Point right() const { return Point(x, y + 1); } Point upper_left() const { return Point(x - 1, y - 1); } Point upper_right() const { return Point(x - 1, y + 1); } Point lower_left() const { return Point(x + 1, y - 1); } Point lower_right() const { return Point(x + 1, y + 1); } vec around4() const { return {up(), down(), left(), right()}; } vec around8() const { return {up(), up().right(), right(), right().down(), down(), down().left(), left(), left().up()}; } int manhattan() const { return std::abs(x) + std::abs(y); } int eucurid2() const { return x * x + y * y; } bool operator==(const Point &p) const { return x == p.x && y == p.y; } bool operator!=(const Point &p) const { return !(*this == p); } void operator+=(const Point &p) { x += p.x; y += p.y; } void operator-=(const Point &p) { x -= p.x; y -= p.y; } Point operator+(const Point &p) const { return Point(x + p.x, y + p.y); } Point operator-(const Point &p) const { return Point(x - p.x, y - p.y); } bool operator<(const Point &p) const { return x == p.x ? y < p.y : x < p.x; } bool operator>(const Point &p) const { return x == p.x ? y > p.y : x > p.x; } }; ostream &operator<<(ostream &os, const Point &p) { os << p.x << p.y; return os; } istream &operator>>(istream &is, Point &p) { is >> p.x >> p.y; return is; } inline bool is_contained(int H, int W, Point p) { return is_contained(H, W, p.x, p.y); } #line 4 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/2d/area.hpp" class Area { public: int H, W; bool allow_outside = false; char out_val; Area(int H, int W) : H(H), W(W), data(vector(H, string(W, '.'))) {} Area(int H, int W, char out_val) : H(H), W(W), data(vector(H, string(W, '.'))), allow_outside(true), out_val(out_val) {} string &operator[](int i) { return data[i]; } // 時計回りで90度回転 Area rotated90() const { Area ret(W, H); rep(i, H) rep(j, W) ret[j][H - i - 1] = data[i][j]; return ret; } void rotate90() { assert(H == W); data = rotated90().data; } char at(int x, int y) { if (is_contained(H, W, x, y)) return data[x][y]; else if (allow_outside) return out_val; else { cerr << "[Area::at] out of range" << endl; assert(false); } } void set(int x, int y, char val) { if (is_contained(H, W, x, y)) data[x][y] = val; else if (allow_outside) return; else { cerr << "[Area::set] out of range" << endl; assert(false); } } bool contains(int x, int y) const { return is_contained(H, W, x, y); } bool contains(Point p) const { return is_contained(H, W, p.x, p.y); } private: vec data; }; ostream &operator<<(ostream &os, Area &a) { rep(i, a.H) os << a[i] << endl; return os; } istream &operator>>(istream &is, Area &a) { rep(i, a.H) is >> a[i]; return is; } #line 4 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/2d/all.hpp" #line 1 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/2d/rect.hpp" class Rect { public: int x, y, w, h; Rect(int x, int y, int w, int h) : x(x), y(y), w(w), h(h) {} int area() const { return w * h; } }; #line 6 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/2d/all.hpp" #line 4 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/all.hpp" // #include "3d/all.hpp" // #include "convolution/all.hpp" #line 1 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/datastructure/all.hpp" #line 1 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/datastructure/comp.hpp" // https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/4/DSL_4_A template struct comp { private: const int _n; int _cmp_n; vec _raw, _comp; public: explicit comp(const vec &src) : _n(src.size()), _cmp_n(0), _raw(src), _comp(_n, 0) { sort(_raw.begin(), _raw.end()); _raw.erase(unique(_raw.begin(), _raw.end()), _raw.end()); _cmp_n = _raw.size(); rep(i, _n) _comp[i] = lower_bound(_raw.begin(), _raw.end(), src[i]) - _raw.begin(); } inline int size() const { return _n; } inline int cmp_size() const { return _cmp_n; } inline T get_raw(int complessed) { assert(0 <= complessed && complessed < _cmp_n); return _raw[complessed]; } inline T operator[](int i) { assert(0 <= i && i < _n); return _comp[i]; } inline T get_comp(int raw) { return lower_bound(_raw.begin(), _raw.end(), raw) - _raw.begin(); } }; #line 4 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/datastructure/all.hpp" #line 1 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/datastructure/dynamic-segment-tree.hpp" /** * @brief セグメント木 * * @tparam T ノードの型 */ template struct DynamicSegmentTree { private: /// 単位元 T e; /// 演算 function op; /// 要素数 int n; /// ノードの構造体 struct Node { /// ノードの値 T val; /// 初期化用の値 T e; /// 親ノード, 左の子ノード, 右の子ノード Node *p, *l_child, *r_child; /// ノードの範囲 int l, r; Node(T val, T e, int l, int r) : val(val), e(e), p(nullptr), l_child(nullptr), r_child(nullptr), l(l), r(r) {} Node(T val, Node *p, bool child_index) : val(val), e(p->e), p(p), l_child(nullptr), r_child(nullptr), l(!child_index ? p->l : p->mid()), r(!child_index ? p->mid() : p->r) { } /// ノードの範囲の中央 int mid() const { return (l + r) / 2; } /// 子ノードを取得する Node *child(bool child_index) { if (child_index == 0) { if (l_child == nullptr) l_child = new Node(e, this, 0); return l_child; } else { if (r_child == nullptr) r_child = new Node(e, this, 1); return r_child; } } /// 子ノードの情報からvalを更新する void update(auto &op) { T l_val = l_child == nullptr ? e : l_child->val; T r_val = r_child == nullptr ? e : r_child->val; val = op(l_val, r_val); } }; Node *root; public: /** * @brief 個数から空のSegmentTreeを生成する O(1) * * @param length 要素数 * @param e 単位元 * @param op 演算 */ inline explicit DynamicSegmentTree(int length, T e, function op) : e(e), op(op), n(bit_ceil(length)), root(new Node(e, e, 0, n)) {} /** * @brief i番目の要素を取得する O(log n) */ inline Node *get_node(int i) const { Node *node = root; while (node->l + 1 < node->r) { node = node->child(node->mid() <= i); } return node; } /** * @brief i番目の要素を変更する O(log n) * op * * @param i インデックス (0-indexed) * @param a 更新後の要素 */ inline void set(int i, T a) { Node *node = get_node(i); node->val = a; while (node->p != nullptr) { node = node->p; node->update(op); } } /** * @brief i番目の要素を取得する O(log n) * * @param i インデックス (0-indexed) * @return i番目の要素 */ inline T get(int i) const { return get_node(i)->val; } /** * @brief [l, r)の範囲に対するクエリを行う O(log n) * op * * @param l クエリの左端 (0-indexed) * @param r クエリの右端 (0-indexed) * @return クエリの結果 */ inline T query(int l, int r) const { return _query(root, l, r); } private: /** * @brief 特定のノードに対し、[l, r)の範囲に対するクエリを行う O(log n) * op * * @param node クエリを行うノード * @param l クエリの左端 (0-indexed) * @param r クエリの右端 (0-indexed) * @return クエリの結果 */ inline T _query(Node *node, int l, int r) const { if (r <= node->l || node->r <= l) return e; if (l <= node->l && node->r <= r) return node->val; return op(_query(node->child(0), l, r), _query(node->child(1), l, r)); } }; #line 5 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/datastructure/all.hpp" #line 1 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/datastructure/fenwick-tree.hpp" template struct FenwickTree { private: T _n; vec _data; public: explicit FenwickTree(T n) : _n(n), _data(n + 1, 0) {} explicit FenwickTree(const vec &src) : _n(src.size()), _data(_n + 1, 0) { rep(i, _n) add(i, src[i]); } void add(int i, T val) { i++; while (i <= _n) { _data[i] += val; i += i & -i; } } // [0, i] int sum(int i) const { i++; T ans = 0; while (i > 0) { ans += _data[i]; i -= i & -i; } return ans; } // [l, r) int sum(int l, int r) const { return sum(r - 1) - sum(l - 1); } }; #line 6 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/datastructure/all.hpp" #line 1 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/datastructure/imos.hpp" template struct imos { private: const int _n; vec _data; bool _is_build = false; public: explicit imos(int n) : _n(n), _data(_n + 1, 0) {} explicit imos(vec src) : _n(src.size()), _data(_n + 1, 0) { rep(i, _n) add(i, src[i]); } inline int size() const { return _n; } inline void add(int l, int r, T x) { assert(!_is_build); assert(l < r); assert(0 <= l && r <= _n); _data[l] += x; _data[r] -= x; } inline void add(int i, T x) { assert(!_is_build); assert(0 <= i && i < _n); add(i, i + 1, x); } inline void build() { rep(i, _n) _data[i + 1] += _data[i]; _is_build = true; } inline T get(int i) { assert(0 <= i && i < _n); if (!_is_build) build(); return _data[i]; } friend ostream &operator<<(ostream &os, const imos &a) { if (!a._is_build) { os << "not builded"; return os; } os << a._data; return os; } }; #line 7 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/datastructure/all.hpp" #line 1 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/datastructure/imos2d.hpp" template struct imos2d { private: const int _H, _W; vvec _data; bool _is_build = false; public: explicit imos2d(int H, int W) : _H(H), _W(W), _data(_H + 1, vec(_W + 1, 0)) {} explicit imos2d(vvec src) : _H(src.size()), _W(src[0].size()), _data(_H + 1, vec(_W + 1, 0)) { rep(x, _H) rep(y, _W) add({x, y}, src[x][y]); } inline pair size() const { return {_H, _W}; } // 半開区間 inline void add(Point a, Point b, T x) { assert(!_is_build); assert(a.x < b.x && a.y < b.y); assert(is_contained(_H, _W, a) && is_contained(_H, _W, b.upper_left())); _data[a.x][a.y] += x; _data[a.x][b.y] -= x; _data[b.x][a.y] -= x; _data[b.x][b.y] += x; } inline void add(Point a, T x) { assert(!_is_build); assert(is_contained(_H, _W, a)); add(a, a.lower_right(), x); } inline void build() { rep(x, _H) rep(y, _W) _data[x][y + 1] += _data[x][y]; rep(y, _W) rep(x, _H) _data[x + 1][y] += _data[x][y]; _is_build = true; } inline T get(Point p) const { assert(is_contained(_H, _W, p)); assert(_is_build); return _data[p.x][p.y]; } }; template ostream &operator<<(ostream &os, const imos2d &im) { rep(x, im.size().first) { rep(y, im.size().second) { os << im.get({x, y}) << " "; } os << endl; } return os; } #line 8 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/datastructure/all.hpp" #line 1 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/datastructure/lazy-segment-tree.hpp" // 参考 https://qiita.com/ningenMe/items/bf66de877e3b97d35862 /** * @brief 遅延セグメント木 * * @tparam T ノードの型 * @tparam F 操作情報の型 */ template struct LazySegmentTree { private: /// データの単位元 const T e; /// 操作の単位元 const F id; /// データの演算(ノードのマージ) const function op; /// ノードの更新 (操作の適用) const function apply; /// 操作のマージ const function merge; // 要素数 int32_t _n; int32_t _height; /// セグ木のノード情報 vec _data; /// セグ木の遅延情報 vec _lazy; /// 左の子のインデックスを返す #define L(i) (i << 1) /// 右の子のインデックスを返す #define R(i) (i << 1 | 1) /// 親のインデックスを返す #define P(i) (i >> 1) /** * @brief k番目のノードの遅延情報を解消し、子ノードに伝搬する O(log N) * merge * * @param k ノード番号 (1-indexed, seg-index) */ inline void eval(int32_t k) { if (_lazy[k] == id) return; _data[k] = apply(_lazy[k], _data[k]); if (k < _n) { _lazy[L(k)] = merge(_lazy[L(k)], _lazy[k]); _lazy[R(k)] = merge(_lazy[R(k)], _lazy[k]); } _lazy[k] = id; } public: // n: 要素数, e: 単位元, id: 操作情報の単位元, op: 演算, update: // ノードの更新(fn,val->val), merge: // 操作aがすでに行われている状態に操作bを適用したときの操作 // TODO: 2つの実装が別れているのをどうにかする /** * @brief 要素数から空のLazySegmentTreeを生成する O(length) * * @param length 要素数 * @param e 単位元 * @param id 操作情報の単位元 * @param op ノードのマージ * @param apply 操作の適用 * @param merge 操作のマージ */ explicit inline LazySegmentTree(const int32_t length, const T e, const F id, const function op, const function apply, const function merge) : e(e), id(id), op(op), apply(apply), merge(merge), _n(bit_ceil(length)), _height(bit_width(_n) - 1), _data(2 * _n, e), _lazy(2 * _n, id) {} /** * @brief 既存のベクトルからLazySegmentTreeを生成する O(length) * op * * @param data データ * @param e 単位元 * @param id 操作情報の単位元 * @param op ノードのマージ * @param apply 操作の適用 * @param merge 操作のマージ */ explicit inline LazySegmentTree(vec &data, const T e, const F id, const function op, const function apply, const function merge) : e(e), id(id), op(op), apply(apply), merge(merge), _n(bit_ceil(data.size())), _height(bit_width(_n) - 1), _data(2 * _n, e), _lazy(2 * _n, id) { rep(i, data.size()) _data[i + _n] = data[i]; for (int i = _n - 1; i > 0; --i) _data[i] = op(_data[L(i)], _data[R(i)]); } /** * @brief [l, r)の区間に対して操作fを適用する O(log N) * op * * @param l 左端 (0-indexed) * @param r 右端 (0-indexed) * @param f 操作 */ inline void set(int32_t l, int32_t r, F f) { // a, bはseg-index [a,b] int32_t a = l + _n, b = r + _n - 1; // 上から下へとlazyを伝搬させる for (int32_t i = _height; 0 < i; --i) eval(a >> i), eval(b >> i); // bを [a, b]から[a, b)にする for (b++; a < b; a >>= 1, b >>= 1) { if (a & 1) _lazy[a] = merge(_lazy[a], f), eval(a), a++; if (b & 1) --b, _lazy[b] = merge(_lazy[b], f), eval(b); } // a, bをseg-index [a,b]に戻す a = l + _n, b = r + _n - 1; // a,bを親に移しつつ、aが実在頂点の間 while ((a >>= 1), (b >>= 1), a) { if (_lazy[a] == id) { _data[a] = op(apply(_lazy[(a << 1) | 0], _data[(a << 1) | 0]), apply(_lazy[(a << 1) | 1], _data[(a << 1) | 1])); } if (_lazy[b] == id) { _data[b] = op(apply(_lazy[(b << 1) | 0], _data[(b << 1) | 0]), apply(_lazy[(b << 1) | 1], _data[(b << 1) | 1])); } } } /** * @brief [l, r)の区間に対するクエリを処理する * * @param l 左端 (0-indexed) * @param r 右端 (0-indexed) * @return T クエリの結果 */ inline T query(int32_t l, int32_t r) { // a, bはseg-index [a,b] int32_t a = l + _n, b = r + _n - 1; // 上から下へとlazyを伝搬させる for (int32_t i = _height; 0 <= i; --i) eval(a >> i), eval(b >> i); T vl = e, vr = e; // bを [a, b]から[a, b)にする for (b++; a < b; a >>= 1, b >>= 1) { if (a & 1) vl = op(vl, apply(_lazy[a], _data[a])), a++; if (b & 1) b--, vr = op(apply(_lazy[b], _data[b]), vr); } return op(vl, vr); } /** * @brief i番目の要素を取得する * * @param i インデックス (0-indexed) * @return T i番目の要素 */ inline T get(int32_t i) { return query(i, i + 1); } #undef L #undef R #undef P }; #line 9 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/datastructure/all.hpp" #line 1 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/datastructure/rbst-multiset.hpp" #line 1 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/datastructure/rbst.hpp" template struct RBST { private: /// 乱数シード生成器 random_device rd; /// 乱数生成器 mt19937 mt; /// 単位元 T e; /// 演算 function F; public: /// ノード struct node_t { /// ノードの値 T val; /// 部分木の大きさ size_t size; /// 部分木の総積 T sum; /// 左右の子 node_t *lch, *rch; /// 値のみによるノードの生成 node_t(T val) : val(val), size(1), sum(val), lch(nullptr), rch(nullptr) {} /// 値と子によるノードの生成 node_t(T val, node_t *lch, node_t *rch) : val(val), size(1), sum(val), lch(lch), rch(rch) {} }; /// ノードの値を取得 inline T val(const node_t *const t) const { return t ? t->val : e; } inline size_t size(const node_t *const t) const { return t ? t->size : 0; } inline T sum(const node_t *const t) const { return t ? t->sum : e; } inline node_t *update(node_t *const t) const { t->size = size(t->lch) + size(t->rch) + 1; t->sum = F(F(sum(t->lch), val(t)), sum(t->rch)); return t; } RBST(T e, function F) : mt(rd()), e(e), F(F) {} node_t *root = nullptr; inline node_t *merge(node_t *const l, node_t *const r) { if (!l || !r) return l ? l : r; if (mt() % (l->size + r->size) < l->size) { l->rch = merge(l->rch, r); return update(l); } else { r->lch = merge(l, r->lch); return update(r); } } inline pair split(node_t *const t, const size_t k) { if (!t) return {nullptr, nullptr}; if (k <= size(t->lch)) { auto p = split(t->lch, k); t->lch = p.second; return {p.first, update(t)}; } else { auto p = split(t->rch, k - size(t->lch) - 1); t->rch = p.first; return {update(t), p.second}; } } inline node_t *insert_at(node_t *t, const size_t k, T val) { auto [l, r] = split(t, k); return t = merge(merge(l, new node_t(val)), r); } inline void insert_at(const size_t k, T val) { if (!root) root = new node_t(val); else root = insert_at(root, k, val); } inline node_t *erase_at(node_t *t, const size_t k) { auto [l, r] = split(t, k); auto [ll, lr] = split(r, 1); return t = merge(l, lr); } inline void erase_at(const size_t k) { assert(root); assert(0 <= k); assert(k < root->size); if (root->size == 1) { delete root; root = nullptr; return; } root = erase_at(root, k); } inline T get_at(const node_t *const t, const size_t k) const { assert(t); assert(0 <= k); assert(k < t->size); if (k < size(t->lch)) return get_at(t->lch, k); if (k == size(t->lch)) return t->val; return get_at(t->rch, k - size(t->lch) - 1); } inline T get_at(const size_t k) const { return get_at(root, k); } inline T query(node_t *&t, const size_t l, const size_t r) { auto [left, mid_right] = split(t, l); auto [mid, right] = split(mid_right, r - l); T res = sum(mid); t = merge(merge(left, mid), right); return res; } inline T query(const size_t l, const size_t r) { return query(root, l, r); } inline size_t size() const { return size(root); } }; template ostream &operator<<(ostream &os, const RBST &t) { using node_t = typename RBST::node_t; auto dump = [&os](auto fn, node_t *t) { if (!t) return; fn(fn, t->lch); os << t->val << " "; fn(fn, t->rch); }; os << "RBST[ "; dump(dump, t.root); os << "]"; return os; } #line 4 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/datastructure/rbst-multiset.hpp" template struct RBSTMultiSet : public RBST { private: using node_t = typename RBST::node_t; public: inline RBSTMultiSet() : RBST(0, [](T a, T b) { return a; }) {} inline size_t lower_bound(const node_t *const t, T val) const { if (!t) return 0; if (val <= this->val(t)) return lower_bound(t->lch, val); return this->size(t->lch) + 1 + lower_bound(t->rch, val); } inline size_t lower_bound(const T val) const { return lower_bound(this->root, val); } inline size_t upper_bound(const node_t *const t, const T val) const { if (!t) return 0; if (val < t->val) return upper_bound(t->lch, val); return this->size(t->lch) + 1 + upper_bound(t->rch, val); } inline size_t upper_bound(const T val) const { return upper_bound(this->root, val); } inline void insert(const T val) { this->insert_at(lower_bound(val), val); } inline size_t count(const T val) const { return upper_bound(val) - lower_bound(val); } inline bool contains(const T val) const { int idx = lower_bound(val); return idx < this->root->size && this->get_at(idx)->val == val; } inline void erase(const T val) { int idx = lower_bound(val); if (idx < this->root->size && this->get_at(idx)->val == val) { this->erase_at(idx); } } }; #line 10 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/datastructure/all.hpp" #line 1 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/datastructure/rbst-set.hpp" template struct RBSTSet : public RBSTMultiSet { public: inline RBSTSet() : RBSTMultiSet() {} inline void insert(const T val) { if (contains(val)) return; this->insert(val, lower_bound(val)); } }; #line 11 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/datastructure/all.hpp" #line 1 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/datastructure/segment-tree.hpp" // 参考: https://qiita.com/ningenMe/items/bf66de877e3b97d35862 /** * @brief セグメント木 * * @tparam T ノードの型 */ template struct SegmentTree { private: /// 単位元 T e; /// 演算 function op; /// 要素数 int n; /// SegTreeのノード上のデータ vec data; /// 左の子のインデックスを返す #define L(i) (i << 1) /// 右の子のインデックスを返す #define R(i) (i << 1 | 1) /// 親のインデックスを返す #define P(i) (i >> 1) public: /** * @brief 個数から空のSegmentTreeを生成する O(n) * * @param length 要素数 * @param e 単位元 * @param op 演算 */ inline explicit SegmentTree(int length, T e, function op) : e(e), op(op), n(bit_ceil(length)), data(2 * n, e) {} /** * @brief 既存のベクトルからSegmentTreeを生成する O(n) * op * * @param v データ * @param e 単位元 * @param op 演算 */ inline explicit SegmentTree(const vec &v, T e, function op) : e(e), op(op), n(bit_ceil(v.size())), data(2 * n, e) { rep(i, v.size()) data[i + n] = v[i]; for (int i = n - 1; i > 0; --i) data[i] = op(data[L(i)], data[R(i)]); } /** * @brief i番目の要素を変更する O(log n) * op * * @param i インデックス (0-indexed) * @param a 更新後の要素 */ inline void set(int i, T a) { i += n; data[i] = a; while (i = P(i), i > 0) data[i] = op(data[L(i)], data[R(i)]); } /** * @brief i番目の要素を取得する O(1) * * @param i インデックス (0-indexed) * @return i番目の要素 */ inline T get(int i) const { return data[i + n]; } /** * @brief [l, r)の範囲に対するクエリを行う O(log n) * op * * @param l クエリの左端 (0-indexed) * @param r クエリの右端 (0-indexed) * @return クエリの結果 */ inline T query(int l, int r) const { T l_val = e, r_val = e; l += n, r += n; while (l < r) { if (l & 1) l_val = op(l_val, data[l++]); if (r & 1) r_val = op(data[--r], r_val); l = P(l), r = P(r); } return op(l_val, r_val); } #undef L #undef R #undef P }; #line 13 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/datastructure/all.hpp" #line 1 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/datastructure/union-find.hpp" struct UnionFind { private: int _n; vec _parents; vec _size; public: explicit UnionFind(int n) : _n(n), _parents(n), _size(n, 1) { iota(all(_parents), 0); } int find(int a) { if (_parents[a] == a) return a; else return _parents[a] = find(_parents[a]); } void merge(int a, int b) { a = find(a); b = find(b); if (a != b) { // merge後の親はa if (_size[a] < _size[b]) swap(a, b); _size[a] += _size[b]; _size[b] = 0; _parents[b] = a; } } int size(int a) { return _size[find(a)]; } bool same(int a, int b) { return find(a) == find(b); } vec> groups() { vec leaders(_n); rep(i, _n) { leaders[i] = find(i); } vec> res(_n); rep(i, _n) res[i].reserve(_size[i]); rep(i, _n) res[leaders[i]].push_back(i); res.erase(remove_if(all(res), [&](const vec &v) { return v.empty(); }), res.end()); return res; } }; using UF = UnionFind; #line 14 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/datastructure/all.hpp" #line 1 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/datastructure/weighted-union-find.hpp" template struct WeightedUnionFind { private: int _n; vec _parents; vec _size; vec _weight; T weight(int i) { find(i); return _weight[i]; } public: explicit WeightedUnionFind(int n) : _n(n), _parents(n), _size(n, 1), _weight(n) { iota(all(_parents), 0); } int find(int i) { if (_parents[i] == i) return i; const int root = find(_parents[i]); _weight[i] += _weight[_parents[i]]; return _parents[i] = root; } void merge(int a, int b, T w) { w += weight(a); w -= weight(b); a = find(a); b = find(b); if (a != b) { // merge後の親はa if (_size[a] < _size[b]) swap(a, b), w = -w; _size[a] += _size[b]; _size[b] = 0; _parents[b] = a; _weight[b] = w; } } T diff(int a, int b) { return weight(b) - weight(a); } int size(int a) { return _size[find(a)]; } bool same(int a, int b) { return find(a) == find(b); } }; template using WUF = WeightedUnionFind; #line 15 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/datastructure/all.hpp" #line 7 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/all.hpp" #line 1 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/graph/all.hpp" #line 1 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/graph/cycle.hpp" #line 1 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/graph/template.hpp" // Node template struct WeightedNode { int id; T cost = numeric_limits::max(); WeightedNode(int id, T cost) : id(id), cost(cost) {} }; template struct WeightState { public: int location; T used_cost; WeightState(int location, T used_cost) : location(location), used_cost(used_cost) {} bool operator<(const WeightState &n) const { return used_cost < n.used_cost; } bool operator>(const WeightState &n) const { return used_cost > n.used_cost; } }; // Graph struct Graph { private: const int n; const bool directed; vec> edges; public: explicit Graph(int n, bool directed = false) : n(n), directed(directed), edges(n) {} inline void add_edge(int u, int v) { edges[u].emplace_back(v); if (!directed) edges[v].emplace_back(u); } inline vec &operator[](int i) { return edges[i]; } inline int size() const { return n; } }; template struct WeightedGraph { private: const int n; const bool directed; public: vec>> edges; explicit WeightedGraph(int n, bool directed = false) : n(n), directed(directed), edges(n) {} inline void add_edge(int u, int v, T w) { edges[u].emplace_back(WeightedNode(v, w)); if (!directed) edges[v].emplace_back(WeightedNode(u, w)); } inline vec> &operator[](int i) { return edges[i]; } inline int size() const { return n; } }; // template using WeightedGraph = vec>>; template using WGraph = WeightedGraph; #line 4 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/graph/cycle.hpp" bool has_cycle(Graph &g, int start = 0) { vec seen(g.size(), 0); vec finished(g.size(), 0); auto dfs = [&](auto fn, int index) { seen[index] = 1; for (auto next : g[index]) { if (finished[next]) continue; if (seen[next] && !finished[next]) return true; if (fn(fn, next)) return true; } finished[index] = 1; return false; }; return dfs(dfs, start); } #line 2 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/graph/all.hpp" #line 1 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/graph/depth.hpp" struct TreeNodeInfo { public: TreeNodeInfo(int parent, int depth) : parent(parent), depth(depth) {} int parent; int depth; }; vec depth(Graph &graph, int root = 0) { vec result(graph.size(), TreeNodeInfo(-1, -1)); stack st; st.push(root); result[root] = TreeNodeInfo(root, 0); while (!st.empty()) { int index = st.top(); st.pop(); for (auto next : graph[index]) { if (result[next].depth != -1) continue; result[next] = TreeNodeInfo(index, result[index].depth + 1); st.push(next); } } return result; } #line 3 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/graph/all.hpp" #line 1 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/graph/diameter.hpp" int diameter(Graph &graph, int start = 0) { vec seen(graph.size(), 0); auto dfs = [&](auto fn, int index) -> pair { // max-cost, index pair result = {0, index}; seen[index] = 1; for (auto next : graph[index]) { if (seen[next]) continue; auto next_result = fn(fn, next); next_result.first += 1; result = max(result, next_result); } seen[index] = 0; return result; }; auto result = dfs(dfs, start); result = dfs(dfs, result.second); return result.first; } template int diameter(WGraph &graph, int start = 0) { auto dfs = [&](int index) -> pair { vec result(graph.size(), -1); T mx = 0; int mx_index = index; stack st; st.push(index); result[index] = 0; while (!st.empty()) { int current = st.top(); st.pop(); for (auto next : graph[current]) { if (result[next.id] >= 0) continue; st.push(next.id); result[next.id] = result[current] + next.cost; if (chmax(mx, result[next.id])) { mx_index = next.id; } } } return {mx, mx_index}; }; auto result = dfs(start); result = dfs(result.second); return result.first; } #line 4 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/graph/all.hpp" #line 1 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/graph/dijkstra.hpp" template vec dijkstra(WGraph &graph, int start) { vec way(graph.size(), INF); rp_queue> q; q.push(WeightState(start, 0)); way[start] = 0; while (!q.empty()) { WeightState current = q.top(); q.pop(); for (auto &next : graph[current.location]) { T next_cost = current.used_cost + next.cost; if (way[next.id] <= next_cost) continue; way[next.id] = next_cost; q.push(WeightState(next.id, way[next.id])); } } return way; } #line 5 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/graph/all.hpp" #line 1 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/graph/lca.hpp" struct LCA { private: Graph graph; int root; // parent[k][v] := vの2^k先の親 vec> parent; vec depth_data; public: explicit LCA(Graph &graph, int root = 0) : graph(graph), root(root), depth_data(depth(graph, root)) { int n = graph.size(); int logn = 1; while ((1 << logn) < n) logn++; parent = vector(logn, vector(n, -1LL)); for (int i = 0; i < n; i++) parent[0][i] = depth_data[i].parent; // ダブリング for (int k = 0; k + 1 < logn; k++) { for (int i = 0; i < n; i++) { if (parent[k][i] < 0) parent[k + 1][i] = -1; else parent[k + 1][i] = parent[k][parent[k][i]]; } } } int query(int u, int v) const { if (depth_data[u].depth > depth_data[v].depth) swap(u, v); int logn = parent.size(); // uとvの深さが同じになるまで親を辿る rep(k, logn) { if ((depth_data[v].depth - depth_data[u].depth) >> k & 1) { v = parent[k][v]; } } // にぶたん if (u == v) return u; for (int k = logn - 1; k >= 0; k--) { if (parent[k][u] != parent[k][v]) { u = parent[k][u]; v = parent[k][v]; } } return parent[0][u]; } }; #line 6 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/graph/all.hpp" #line 1 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/graph/topological-sort.hpp" vec topological_sort(Graph &graph) { vec result; vec deleted(graph.size(), false); vec in_count(graph.size()); rep(i, graph.size()) { for (auto next : graph[i]) { in_count[next]++; } } queue q; rep(i, graph.size()) { if (in_count[i] == 0) { q.push(i); } } while (!q.empty()) { int now = q.front(); q.pop(); result.emplace_back(now); deleted[now] = true; for (auto next : graph[now]) { if (deleted[next]) continue; in_count[next]--; if (in_count[next] == 0) { q.push(next); } } } return result; } #line 8 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/graph/all.hpp" #line 8 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/all.hpp" #line 1 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/math/all.hpp" // #include "combination.hpp" // #include "factorial.hpp" #line 1 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/math/modint.hpp" namespace modint_utils { constexpr inline int32_t normalize(int val, int32_t mod) { return (val % mod + mod) % mod; } constexpr inline int32_t inv(int32_t a, int32_t mod) { int32_t b = mod, u = 1, v = 0; while (b) { int32_t t = a / b; a -= t * b; swap(a, b); u -= t * v; swap(u, v); } u %= mod; if (u < 0) u += mod; return u; // return mod_pow(val, mod - 2, mod); } } // namespace modint_utils template struct dynamic_modint { private: int _val; public: dynamic_modint() : dynamic_modint(0) {} dynamic_modint(int val) : _val(modint_utils::normalize(val, MOD)) {} // logic int val() const { return _val; } inline dynamic_modint inv() const { return dynamic_modint(modint_utils::inv(_val, MOD)); } inline dynamic_modint pow(const int n) const { return dynamic_modint(powm(_val, n, MOD)); } inline static constexpr dynamic_modint pow(const dynamic_modint &a, const int n) { return dynamic_modint(mod_pow(a._val, n, a.MOD)); } // op inline dynamic_modint &operator++() { return *this += 1; } inline dynamic_modint &operator--() { return *this -= 1; } inline dynamic_modint operator++(int32_t) const { dynamic_modint tmp = *this; ++*this; return tmp; } inline dynamic_modint operator--(int32_t) { dynamic_modint tmp = *this; --*this; return tmp; } inline dynamic_modint operator+(const dynamic_modint &a) const { return dynamic_modint(_val) += a; } inline dynamic_modint operator-(const dynamic_modint &a) const { return dynamic_modint(_val) -= a; } inline dynamic_modint operator*(const dynamic_modint &a) const { return dynamic_modint(_val) *= a; } inline dynamic_modint operator/(const dynamic_modint &a) const { return dynamic_modint(_val) /= a; } inline bool operator==(const dynamic_modint &a) { return _val == a._val; } inline bool operator!=(const dynamic_modint &a) { return _val != a._val; } inline dynamic_modint &operator+=(const dynamic_modint &a) { _val += a.val(); if (_val >= MOD) _val -= MOD; return *this; } inline dynamic_modint &operator-=(const dynamic_modint &a) { _val -= a.val(); if (_val < 0) _val += MOD; return *this; } inline dynamic_modint &operator*=(const dynamic_modint &a) { _val = _val * a.val() % MOD; return *this; } inline dynamic_modint &operator/=(const dynamic_modint &a) { *this *= modint_utils::inv(a.val(), MOD); return *this; } explicit operator int() const { return _val; } // io friend ostream &operator<<(ostream &os, const dynamic_modint &a) { return os << a._val; } friend istream &operator>>(istream &os, dynamic_modint &a) { os >> a._val; a._val = modint_utils::normalize(a._val, MOD); return os; } }; // using modint998 = modint<998244353>; template ostream &operator<<(ostream &os, const dynamic_modint &i) { os << i.val(); return os; } template ostream &operator<<(ostream &os, const vector> &v) { for (int i = 0; i < (int)v.size(); i++) { os << v[i].val() << (i + 1 != (int)v.size() ? " " : ""); } return os; } template struct modint { private: using i32 = int32_t; i32 _val; public: consteval inline modint() noexcept : _val(0) {} constexpr inline modint(int val) noexcept : _val(modint_utils::normalize(val, MOD)) {} constexpr inline modint(modint const &val) noexcept : _val(val._val) {} // logic constexpr i32 val() const noexcept { return _val; } constexpr modint pow(const int n) const { return modint(powm(_val, n, MOD)); } constexpr inline static modint pow(const modint &a, const int n) noexcept { return modint(mod_pow(a._val, n, a.MOD)); } constexpr inline modint inv() const noexcept { return modint(modint_utils::inv(_val, MOD)); } // op constexpr inline modint &operator++() noexcept { return *this += 1; } constexpr inline modint &operator--() noexcept { return *this -= 1; } constexpr inline modint operator++(int32_t) noexcept { modint tmp = *this; ++*this; return tmp; } constexpr inline modint operator--(int32_t) noexcept { modint tmp = *this; --*this; return tmp; } constexpr inline modint operator+(const modint &a) const noexcept { return modint(*this) += a; } constexpr inline modint operator-(const modint &a) const noexcept { return modint(*this) -= a; } constexpr inline modint operator*(const modint &a) const noexcept { return modint(*this) *= a; } constexpr inline modint operator/(const modint &a) const noexcept { return modint(*this) /= a; } constexpr inline bool operator==(const modint &a) const noexcept { return _val == a.val(); } constexpr inline bool operator!=(const modint &a) const noexcept { return _val != a.val(); } constexpr inline modint &operator+=(const modint &a) noexcept { _val += a._val; if (_val >= MOD) _val -= MOD; return *this; } constexpr inline modint &operator-=(const modint &a) noexcept { _val -= a._val; if (_val < 0) _val += MOD; return *this; } constexpr inline modint &operator*=(const modint &a) noexcept { _val = (ll)_val * a._val % MOD; return *this; } constexpr inline modint &operator/=(const modint &a) noexcept { *this *= modint_utils::inv(a.val(), MOD); return *this; } explicit operator int() const noexcept { return _val; } // io friend ostream &operator<<(ostream &os, const modint &a) noexcept { return os << a._val; } friend istream &operator>>(istream &os, modint &a) noexcept { os >> a._val; a._val = modint_utils::normalize(a._val, MOD); return os; } }; using mint998 = modint<998244353>; #line 6 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/math/all.hpp" #line 1 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/math/prime.hpp" // ミラーラビン素数判定法 // O(k log^3 n) // https://drken1215.hatenablog.com/entry/2023/05/23/233000 bool MillerRabin(long long N, vector A) { long long s = 0, d = N - 1; while (d % 2 == 0) { ++s; d >>= 1; } for (auto a : A) { if (N <= a) return true; long long t, x = powm(a, d, N); if (x != 1) { for (t = 0; t < s; ++t) { if (x == N - 1) break; x = __int128_t(x) * x % N; } if (t == s) return false; } } return true; } bool is_prime(long long N) { if (N <= 1) return false; if (N == 2) return true; if (N % 2 == 0) return false; if (N < 4759123141LL) return MillerRabin(N, {2, 7, 61}); else return MillerRabin(N, {2, 325, 9375, 28178, 450775, 9780504, 1795265022}); } // ポラード・ロー素因数分解法 // 値が大きい場合に有効、ちゃんと調べる! // O(n^(1/4)) // https://lpha-z.hatenablog.com/entry/2023/01/15/231500 // https://algo-method.com/tasks/553/editorial uint64_t pollard_rho(uint64_t N) { if (N % 2 == 0) return 2; if (is_prime(N)) return N; uint64_t step = 0; auto f = [&](uint64_t x) -> uint64_t { return (__int128_t(x) * x + step) % N; }; while (true) { ++step; uint64_t x = step, y = f(x); while (true) { uint64_t p = gcd(y - x + N, N); if (p == 0 || p == N) break; if (p != 1) return p; x = f(x); y = f(f(y)); } } } // 素因数分解 // https://algo-method.com/tasks/553/editorial struct PrimeFactor { uint64_t prime; uint64_t exp; }; vec prime_factorize(uint64_t N) { if (N == 1) return {}; uint64_t p = pollard_rho(N); if (p == N) return {{p, 1}}; auto left = prime_factorize(p); auto right = prime_factorize(N / p); left.insert(left.end(), all(right)); sort(all(left), [](const PrimeFactor &a, const PrimeFactor &b) { return a.prime < b.prime; }); vec ans; rep(i, left.size()) { if (i == 0 || left[i].prime != left[i - 1].prime) ans.emplace_back(left[i]); else ans.back().exp += left[i].exp; } return ans; } #line 8 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/math/all.hpp" #line 1 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/math/rational.hpp" template struct Rational { T num, den; Rational(T num) : num(num), den(1) {} Rational(T num, T den) : num(num), den(den) { T g = gcd(num, den); this->num /= g; this->den /= g; } Rational operator+(const Rational &rhs) const { return Rational(num * rhs.den + rhs.num * den, den * rhs.den); } Rational operator-(const Rational &rhs) const { return Rational(num * rhs.den - rhs.num * den, den * rhs.den); } Rational operator*(const Rational &rhs) const { return Rational(num * rhs.num, den * rhs.den); } Rational operator/(const Rational &rhs) const { return Rational(num * rhs.den, den * rhs.num); } bool operator<(const Rational &rhs) const { return num * rhs.den < rhs.num * den; } bool operator>(const Rational &rhs) const { return num * rhs.den > rhs.num * den; } bool operator==(const Rational &rhs) const { return num * rhs.den == rhs.num * den; } bool operator!=(const Rational &rhs) const { return !(*this == rhs); } bool operator<=(const Rational &rhs) const { return (*this < rhs) || (*this == rhs); } bool operator>=(const Rational &rhs) const { return (*this > rhs) || (*this == rhs); } friend ostream &operator<<(ostream &os, const Rational &r) { return os << r.num << "/" << r.den; } void operator+=(const Rational &rhs) { *this = *this + rhs; } void operator-=(const Rational &rhs) { *this = *this - rhs; } void operator*=(const Rational &rhs) { *this = *this * rhs; } void operator/=(const Rational &rhs) { *this = *this / rhs; } double val() const { return (double)num / den; } // operator double() const { return val(); } // operator string() const { return to_string(num) + "/" + to_string(den); } Rational pow(ll n) const { if (n == 0) { return Rational(1); } else if (n < 0) { return Rational(den, num).pow(-n); } else { Rational res = pow(n / 2); res *= res; if (n % 2 == 1) { res *= *this; } return res; } } }; #line 9 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/math/all.hpp" #line 9 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/all.hpp" // #include "string/all.hpp" #line 1 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/util/all.hpp" #line 1 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/util/inversion-num.hpp" int inversion_num(const vec &a) { comp c(a); int n = a.size(); FenwickTree bit(n); int ans = 0; rep(i, n) { ans += i - bit.sum(c[i]); bit.add(c[i], 1); } return ans; } #line 4 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/util/all.hpp" #line 11 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/all.hpp" #line 3 "/home/zoi/document/kyopro/under_greeen_3/main.cpp" using mint = modint<998'244'353>; void solve() { string s; cin >> s; deque starts; int current_removes = 0; int removes = 0; rep(i, s.size()) { if(s[i] == '<') { starts.push_back(i); } else if(s[i] == '>') { bool ok = false; if(!starts.empty()){ int from = starts.back(); if(from + 1 < i) { removes += i - from + 1 - current_removes; current_removes += i - from + 1; // dump("remove", from, i); ok = true; } } if(!starts.empty()) { starts.pop_back(); } if(!ok) { starts.clear(); current_removes = 0; } } } // dump(s.size(), removes); cout << s.size() - removes << endl; } void test() { } signed main() { io_setup(); init_cpp_dump(); // input solve(); // test(); }