#line 2 "/home/yuruhiya/programming/library/Utility/get_MOD.cpp" constexpr long long get_MOD() { #ifdef SET_MOD return SET_MOD; #else return 1000000007; #endif } #line 3 "/home/yuruhiya/programming/library/Utility/constants.cpp" #include #include #include #include #define rep(i, n) for (int i = 0; i < (n); ++i) #define FOR(i, m, n) for (int i = (m); i < (n); ++i) #define rrep(i, n) for (int i = (n)-1; i >= 0; --i) #define rfor(i, m, n) for (int i = (m); i >= (n); --i) #define loop(n) rep(i##__COUNTER__, n) #define unless(c) if (!(c)) #define ALL(x) (x).begin(), (x).end() #define RALL(x) (x).rbegin(), (x).rend() #define range_it(a, l, r) (a).begin() + (l), (a).begin() + (r) using ll = long long; using LD = long double; using VB = std::vector; using VVB = std::vector; using VI = std::vector; using VVI = std::vector; using VL = std::vector; using VVL = std::vector; using VS = std::vector; using VD = std::vector; using PII = std::pair; using VP = std::vector; using PLL = std::pair; using VPL = std::vector; template using PQ = std::priority_queue; template using PQS = std::priority_queue, std::greater>; constexpr int inf = 1000000000; constexpr long long inf_ll = 1000000000000000000ll, MOD = get_MOD(); constexpr long double PI = 3.14159265358979323846, tau = PI * 2, EPS = 1e-12; #line 2 "/home/yuruhiya/programming/library/Utility/Scanner.cpp" #include #line 6 "/home/yuruhiya/programming/library/Utility/Scanner.cpp" #include #include #ifdef _WIN32 #define getchar_unlocked _getchar_nolock #define putchar_unlocked _putchar_nolock #define fwrite_unlocked fwrite #define fflush_unlocked fflush #endif class Scanner { template struct has_scan : std::false_type {}; template struct has_scan().template scan())>> : std::true_type {}; public: static int gc() { return getchar_unlocked(); } static char next_char() { char c; scan(c); return c; } template static void scan(T& v) { if (has_scan::value) { v.template scan(); } else { std::cin >> v; } } static void scan(char& v) { while (std::isspace(v = gc())) ; } static void scan(bool& v) { v = next_char() != '0'; } static void scan(std::vector::reference v) { bool b; scan(b); v = b; } static void scan(std::string& v) { v.clear(); for (char c = next_char(); !std::isspace(c); c = gc()) v += c; } static void scan(int& v) { v = 0; bool neg = false; char c = next_char(); if (c == '-') { neg = true; c = gc(); } for (; std::isdigit(c); c = gc()) v = v * 10 + (c - '0'); if (neg) v = -v; } static void scan(long long& v) { v = 0; bool neg = false; char c = next_char(); if (c == '-') { neg = true; c = gc(); } for (; std::isdigit(c); c = gc()) v = v * 10 + (c - '0'); if (neg) v = -v; } static void scan(double& v) { v = 0; double dp = 1; bool neg = false, after_dp = false; char c = next_char(); if (c == '-') { neg = true; c = gc(); } for (; std::isdigit(c) || c == '.'; c = gc()) { if (c == '.') { after_dp = true; } else if (after_dp) { v += (c - '0') * (dp *= 0.1); } else { v = v * 10 + (c - '0'); } } if (neg) v = -v; } static void scan(long double& v) { v = 0; long double dp = 1; bool neg = false, after_dp = false; char c = next_char(); if (c == '-') { neg = true; c = gc(); } for (; std::isdigit(c) || c == '.'; c = gc()) { if (c == '.') { after_dp = true; } else if (after_dp) { v += (c - '0') * (dp *= 0.1); } else { v = v * 10 + (c - '0'); } } if (neg) v = -v; } template static void scan(std::pair& v) { scan(v.first); scan(v.second); } template , std::nullptr_t> = nullptr> static void scan(std::vector& v) { for (auto& e : v) scan(e); } template , std::nullptr_t> = nullptr> static void scan(std::vector& v) { for (auto e : v) scan(e); } private: template static void scan_tuple_impl(T& v) { if constexpr (N < std::tuple_size_v) { scan(std::get(v)); scan_tuple_impl(v); } } public: template static void scan(std::tuple& v) { scan_tuple_impl(v); } private: struct Read2DVectorHelper { std::size_t h, w; Read2DVectorHelper(std::size_t _h, std::size_t _w) : h(_h), w(_w) {} template operator std::vector>() { std::vector vector(h, std::vector(w)); scan(vector); return vector; } }; struct ReadVectorHelper { std::size_t n; ReadVectorHelper(std::size_t _n) : n(_n) {} template operator std::vector() { std::vector vector(n); scan(vector); return vector; } auto operator[](std::size_t m) { return Read2DVectorHelper(n, m); } }; public: template T read() const { T result; scan(result); return result; } template auto read(std::size_t n) const { std::vector result(n); scan(result); return result; } template auto read(std::size_t h, std::size_t w) const { std::vector result(h, std::vector(w)); scan(result); return result; } std::string read_line() const { std::string v; for (char c = gc(); c != '\n' && c != '\0'; c = gc()) v += c; return v; } template operator T() const { return read(); } int operator--(int) const { return read() - 1; } auto operator[](std::size_t n) const { return ReadVectorHelper(n); } auto operator[](const std::pair& nm) const { return Read2DVectorHelper(nm.first, nm.second); } void operator()() const {} template void operator()(H&& h, T&&... t) const { scan(h); operator()(std::forward(t)...); } private: template