#ifdef ONLINE_JUDGE #include #include #else #include #endif inline std::ostream& operator<<(std::ostream& os, __int128_t val) noexcept { std::string s; bool neg = val < 0; if (val < 0) { val *= -1; } if (val == 0) { s += '0'; } else { while (val > 0) { s += '0' + val % 10; val /= 10; } } reverse(s.begin(), s.end()); if (neg) s = "-" + s; return os << s; } inline std::istream& operator>>(std::istream& is, __int128_t& val) noexcept { std::string s; is >> s; bool neg = false; if (s[0] == '-') { neg = true; s = s.substr(1); } val = 0; for (auto c : s) { val *= 10; val += c - '0'; } if (neg) val *= -1; return is; } __int128_t stolll(std::string s) { __int128_t res = 0; bool neg = false; if (s[0] == '-') { neg = true; s = s.substr(1); } for (auto c : s) { res *= 10; res += c - '0'; } if (neg) res *= -1; return res; } std::string to_string(__int128_t x) { std::string s; bool neg = x < 0; if (x < 0) { x *= -1; } if (x == 0) { s += '0'; } else { while (x > 0) { s += '0' + x % 10; x /= 10; } } reverse(s.begin(), s.end()); if (neg) s = "-" + s; return s; } using ll = long long; using lll = __int128_t; #define rep(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i) #define reps(i, n) for (int i = 1, i##_len = (n); i <= i##_len; ++i) #define rrep(i, n) for (int i = ((int)(n)-1); i >= 0; --i) #define rreps(i, n) for (int i = ((int)(n)); i > 0; --i) #define rep2(i, s, n) for (int i = (s); i < (int)(n); i++) #define repc2(i, s, n) for (int i = (s); i <= (int)(n); i++) #define length(v) ((int)(v).size()) constexpr int inf = 2'000'000'000; constexpr ll linf = 4'000'000'000'000'000'000, M7 = 1'000'000'007, M9 = 998'244'353; #define all(v) begin(v), end(v) #define rall(v) rbegin(v), rend(v) using namespace std; using namespace atcoder; // clang-format off using vint = vector;using vvint = vector>;using vvvint = vector>>; using vll = vector;using vvll = vector>;using vvvll = vector>>; using vlll = vector;using vvlll = vector>;using vvvlll = vector>>; using vchar = vector;using vvchar = vector>;using vvvchar = vector>>; using vstr = vector;using vvstr = vector>;using vvvstr = vector>>; using vpi = vector>;using vvpi = vector>>;using vvpint = vector>>; using vpl = vector>;using vvpl = vector>>;using vvplint = vector>>; using vbool = vector;using vvbool = vector>;using vvvbool = vector>>; #define Vec(type, ...) __make_vec(__VA_ARGS__) template vector __make_vec(size_t a) {return vector(a);}template auto __make_vec(size_t a, Ts... ts) {return vector(ts...))>(a, __make_vec(ts...));} #define VecI(init, type, ...) __make_vecI(__VA_ARGS__) template vector __make_vecI(size_t a) {return vector(a, init);} template auto __make_vecI(size_t a, Ts... ts) {return vector(ts...))>(a, __make_vecI(ts...));} template inline ostream& operator<<(ostream& os, const pair& p) noexcept {return os << p.first << " " << p.second;} inline ostream& operator<<(ostream& os, const modint& m) noexcept { return os << m.val(); } template inline ostream& operator<<(ostream& os, const static_modint& m) noexcept { return os << m.val(); } template struct is_static_modint : std::false_type {}; template struct is_static_modint> : std::true_type {}; template