#ifndef HIDDEN_IN_VS // 折りたたみ用 // 警告の抑制 #define _CRT_SECURE_NO_WARNINGS #include using namespace std; #include using namespace atcoder; // 型名の短縮 using ll = long long; using ull = unsigned long long; // -2^63 ~ 2^63 = 9e18(int は -2^31 ~ 2^31 = 2e9) using u8 = uint8_t; using u16 = uint16_t; using u32 = uint32_t; using u64 = uint64_t; using i128 = __int128; using u128 = unsigned __int128; using pii = pair; using pll = pair; using pil = pair; using pli = pair; using vi = vector; using vvi = vector; using vvvi = vector; using vvvvi = vector; using vl = vector; using vvl = vector; using vvvl = vector; using vvvvl = vector; using vb = vector; using vvb = vector; using vvvb = vector; using vc = vector; using vvc = vector; using vvvc = vector; using vd = vector; using vvd = vector; using vvvd = vector; using vs = vector; using vvs = vector; using vvvs = vector; using mint = modint998244353; // using mint = modint1000000007; // using mint = static_modint<(int)1e9+7>; // using mint = modint; // mint::set_mod(m); using vm = vector; using vvm = vector; using vvvm = vector; using vvvvm = vector; using pim = pair; // 大きい順 template using pq = priority_queue, less>; // 小さい順 template using pq_rev = priority_queue, greater>; using Graph = vvi; // 定数の定義 const double PI = acos(-1); // 4 近傍(右、下、左、上) int DX[4] = {1, 0, -1, 0}; // int DX[] = {1, 1, 0, -1, -1, -1, 0, 1}; int DY[4] = {0, 1, 0, -1}; // int DY[] = {0, 1, 1, 1, 0, -1, -1, -1}; const int INF = 1001001001; const ll INFL = 4004004003094073385LL; // (int)INFL = INF, (int)(-INFL) = -INF; // 汎用マクロの定義 #define all(a) (a).begin(), (a).end() #define rall(a) (a).rbegin(), (a).rend() #define sz(x) ((int)(x).size()) #define lb(a, x) std::lower_bound(all(a), (x)) #define ub(a, x) std::upper_bound(all(a), (x)) #define lbpos(a, x) (int)distance((a).begin(), lb(a, x)) #define ubpos(a, x) (int)distance((a).begin(), ub(a, x)) #define rep(i, n) for (ll i = 0, i##_len = ll(n); i < i##_len; ++i) // 0 から n-1 まで昇順 #define repi(i, s, t) for (ll i = ll(s), i##_end = ll(t); i <= i##_end; ++i) // s から t まで昇順 #define repir(i, s, t) for (ll i = ll(s), i##_end = ll(t); i >= i##_end; --i) // s から t まで降順 #define repe(v, a) for (const auto& v : (a)) // a の全要素(変更不可能) #define repea(v, a) for (auto& v : (a)) // a の全要素(変更可能) #define repb(set, d) for (int set = 0, set##_ub = 1 << int(d); set < set##_ub; ++set) // d ビット全探索(昇順) #define repis(i, set) for (int i = lsb(set), bset##i = set; i < 32; bset##i -= 1 << i, i = lsb(bset##i)) // set の全要素(昇順) #define repp(a) \ sort(all(a)); \ for (bool a##_perm = true; a##_perm; a##_perm = next_permutation(all(a))) // a の順列全て(昇順) #define uniq(a) \ { \ sort(all(a)); \ (a).erase(unique(all(a)), (a).end()); \ } // 重複除去 // 左へ1つ回転 {1, 2, 3} → {2, 3, 1} #define rotl(a) rotate((a).begin(), (a).begin() + 1, (a).end()) // 右へ1つ回転 {1, 2, 3} → {3, 1, 2} #define rotr(a) rotate((a).rbegin(), (a).rbegin() + 1, (a).rend()) #define EXIT(a) \ { \ cout << (a) << endl; \ exit(0); \ } // 強制終了 #define inQ(x, y, u, l, d, r) ((u) <= (x) && (l) <= (y) && (x) < (d) && (y) < (r)) // 半開矩形内判定 #define MIN(v) *min_element(all(v)) #define MAX(v) *max_element(all(v)) #define YN { cout << "Yes" << '\n'; } else { cout << "No" << '\n'; } #define NONE (cout << -1 << '\n') // 汎用関数の定義 template inline ll powi(T n, int k) { ll v = 1; rep(i, k) v *= n; return v; } template inline bool chmax(T& M, const T& x) { if (M < x) { M = x; return true; } return false; } // 最大値を更新(更新されたら true を返す) template inline bool chmin(T& m, const T& x) { if (m > x) { m = x; return true; } return false; } // 最小値を更新(更新されたら true を返す) template inline T getb(T set, int i) { return (set >> i) & T(1); } template inline T smod(T n, T m) { n %= m; if (n < 0) n += m; return n; } // 非負mod // x / y の切り捨ての値を返す(負数にも対応した切り下げ除算) template T floor(T a, T b) { return a / b - (a % b && (a ^ b) < 0); } // x を y で割った時に余りを返す(負数にも対応) template T bmod(T x, T y) { return x - y * floor(x, y); } // floor と bmod の結果を pair で返す template pair divmod(T x, T y) { T q = floor(x, y); return {q, x - q * y}; } // 二次元配列を時計回りに回転. template void vv_rotn(vector> &v) { ll n = v.size(); vector> cv(n, vector(n)); rep(i, n) rep(j, n) cv[n - j - 1][i] = v[i][j]; swap(cv, v); } // 二次元配列を反時計回りに回転. template void vv_rotr(vector> &v) { ll n = v.size(); vector> cv(n, vector(n)); rep(i, n) rep(j, n) cv[j][n - i - 1] = v[i][j]; swap(cv, v); } // グリッド外かどうか(true ならグリッド外) bool out_grid(ll i, ll j, ll h, ll w) { return (!(0 <= i && i < h && 0 <= j && j < w)); } inline int popcount(int n) { return __builtin_popcount(n); } inline int popcount(ll n) { return __builtin_popcountll(n); } inline int lsb(int n) { return n != 0 ? __builtin_ctz(n) : 32; } inline int lsb(ll n) { return n != 0 ? __builtin_ctzll(n) : 64; } inline int msb(int n) { return n != 0 ? (31 - __builtin_clz(n)) : -1; } inline int msb(ll n) { return n != 0 ? (63 - __builtin_clzll(n)) : -1; } template T SUM(const U& A) { return std::accumulate(A.begin(), A.end(), T{}); } template T POP(queue& que) { T a = que.front(); que.pop(); return a; } template T POP(deque& que) { T a = que.front(); que.pop_front(); return a; } template T POP(priority_queue& que) { T a = que.top(); que.pop(); return a; } template T POP(vector& que) { T a = que.back(); que.pop_back(); return a; } template ll binary_search(F check, ll ok, ll ng) { while (llabs(ok - ng) > 1) { auto x = (ng + ok) / 2; (check(x) ? ok : ng) = x; } return ok; } // 演算子オーバーロード template inline istream& operator>>(istream& is, pair& p) { is >> p.first >> p.second; return is; } template inline istream& operator>>(istream& is, vector& v) { repea(x, v) is >> x; return is; } template inline vector& operator--(vector& v) { repea(x, v)-- x; return v; } template inline vector& operator++(vector& v) { repea(x, v)++ x; return v; } #endif // 折りたたみ用 #ifdef LOCAL #define debug(arg) print(#arg, arg) // std::cerr << arg が元々使えるやつはそれを使う template void out(Tp arg) { std::cerr << arg; } // std::pair の出力 template void out(std::pair arg) { std::cerr << '('; out(arg.first); std::cerr << ", "; out(arg.second); std::cerr << ')'; } // std::tuple の出力 template void print_tuple(T arg, std::index_sequence) { static_cast(((std::cerr << (Is == 0 ? "" : ", "), out(std::get(arg))), ...)); } template void out(std::tuple arg) { std::cerr << '('; print_tuple(arg, std::make_index_sequence()); std::cerr << ')'; } // std::{vector, deque, forward_list, list, initializer_list, set, multiset, unordered_set, unordered_multiset, map, multimap, // unordered_map, unordered_multimap, valarray} の出力 template