#1191816 (C++23) No.879 Range Mod 2 Query

提出ソース
結果

問題	No.879 Range Mod 2 Query
コンテスト
ユーザー	Today03
提出日時	2026-10-07 03:32:25
言語	C++23 (gcc 15.3.0 + boost 1.92.0 + ACL) コンパイル: `g++-15 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_` 実行: `./a.out`
結果	AC
実行時間	109 ms / 3,000 ms
	+ 439µs
コード長	47,179 bytes
記録記録タグの例: 初AC ショートコード純ショートコード純主流ショートコード最速実行時間
コンパイル時間	2,178 ms
コンパイル使用メモリ	286,596 KB
実行使用メモリ	15,616 KB
最終ジャッジ日時	2026-10-07 03:32:32
合計ジャッジ時間	5,819 ms
ジャッジサーバーID （参考情報）	judge2_0 / judge4_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン	結果
sample	AC * 1
other	AC * 21
権限があれば一括ダウンロードができます
ソースコード

raw source code
#ifdef TODAY_KYOPRO

/*
 */

//------>8 begin kyopro_library/data_structure/segtree_lazy.hpp >8------

/// @brief 遅延評価セグメント木
/// @tparam Monoid モノイド
/// @tparam Operator 作用素
/// @tparam mapping （モノイドの元，作用素の元）→モノイドの元を返す関数
/// @ref verify: https://judge.yosupo.jp/problem/range_affine_range_sum
/// @ref verify: https://judge.yosupo.jp/problem/range_add_range_min
/// @ref verify: https://judge.yosupo.jp/problem/range_affine_range_sum_large_array
/// @ref verify: https://judge.yosupo.jp/problem/range_set_range_composite
template <typename Monoid, typename Operator, auto mapping>
struct SegTreeLazy {
    using MonoidType = typename Monoid::Type;
    using OperatorType = typename Operator::Type;
    SegTreeLazy() = default;

    /// @brief 要素数 n の遅延セグ木を構築する
    SegTreeLazy(int n) {
        this->n = n;
        dat = vector<MonoidType>(n << 1, Monoid::id());
        lazy = vector<OperatorType>(n << 1, Operator::id());
        indices.reserve(100);
        cand.reserve(100);
        cand_l.reserve(100);
        cand_r.reserve(100);
    }

    /// @brief 配列 v から遅延セグ木を構築する
    SegTreeLazy(const vector<MonoidType>& v) {
        this->n = v.size();
        dat = vector<MonoidType>(n << 1, Monoid::id());
        lazy = vector<OperatorType>(n << 1, Operator::id());
        rep(i, n) dat[i + n] = v[i];
        for(int i = n - 1; i > 0; i--) dat[i] = Monoid::op(dat[i << 1], dat[i << 1 | 1]);
        indices.reserve(100);
        cand.reserve(100);
        cand_l.reserve(100);
        cand_r.reserve(100);
    }

    /// @brief i 番目の要素を x に更新する
    void set(int i, MonoidType x) {
        generate_indices(i, i + 1);
        pushdown();
        i += n;
        dat[i] = x;
        while(i >>= 1) dat[i] = Monoid::op(dat[i << 1], dat[i << 1 | 1]);
    }

    /// @brief 区間 [l, r) に x を作用させる
    void apply(int l, int r, OperatorType x) {
        if(l == r) return;
        generate_indices(l, r);
        pushdown();
        l += n;
        r += n;
        while(l < r) {
            if(l & 1) {
                lazy[l] = Operator::op(lazy[l], x);
                dat[l] = mapping(dat[l], x);
                l++;
            }
            if(r & 1) {
                r--;
                lazy[r] = Operator::op(lazy[r], x);
                dat[r] = mapping(dat[r], x);
            }
            l >>= 1;
            r >>= 1;
        }
        pushup();
    }

    /// @brief 区間 [l, r) のモノイド積を返す
    MonoidType fold(int l, int r) {
        if(l == r) return Monoid::id();
        generate_indices(l, r);
        pushdown();
        MonoidType retl = Monoid::id(), retr = Monoid::id();
        l += n;
        r += n;
        while(l < r) {
            if(l & 1) retl = Monoid::op(retl, dat[l++]);
            if(r & 1) retr = Monoid::op(dat[--r], retr);
            l >>= 1;
            r >>= 1;
        }
        return Monoid::op(retl, retr);
    }

    /// @brief 区間 [l, x) のモノイド積が f を満たすような最大の x >= l を返す
    /// @attention `f(Monoid::id())=true` が成り立つ必要がある
    /// @note O(log(N))
    template <typename F>
    int find_right(int l, F f) {
        assert(f(Monoid::id()));
        if(l == n) return n;
        generate_indices(l, n);
        pushdown();
        l += n;
        int r = n + n;
        cand_l.clear();
        cand_r.clear();
        while(l < r) {
            if(l & 1) cand_l.push_back(l++);
            if(r & 1) cand_r.push_back(--r);
            l >>= 1;
            r >>= 1;
        }
        cand = cand_l;
        reverse(all(cand_r));
        cand.insert(cand.end(), all(cand_r));
        MonoidType val = Monoid::id();
        for(int i : cand) {
            if(f(Monoid::op(val, dat[i]))) {
                val = Monoid::op(val, dat[i]);
            } else {
                while(i < n) {
                    propagate(i);
                    i <<= 1;
                    if(f(Monoid::op(val, dat[i]))) {
                        val = Monoid::op(val, dat[i]);
                        i |= 1;
                    }
                }
                return i - n;
            }
        }
        return n;
    }

    /// @brief 区間 [x, r) のモノイド積が f を満たすような最小の x<=r を返す
    /// @attention `f(Monoid::id())=true` が成り立つ必要がある
    /// @note O(log(N))
    template <typename F>
    int find_left(int r, F f) {
        assert(f(Monoid::id()));
        if(r == 0) return 0;
        generate_indices(0, r);
        pushdown();
        r += n;
        int l = n;
        cand_l.clear();
        cand_r.clear();
        while(l < r) {
            if(l & 1) cand_l.push_back(l++);
            if(r & 1) cand_r.push_back(--r);
            l >>= 1;
            r >>= 1;
        }
        cand = cand_r;
        reverse(all(cand_l));
        cand.insert(cand.end(), all(cand_l));
        MonoidType val = Monoid::id();
        for(int i : cand) {
            if(f(Monoid::op(dat[i], val))) {
                val = Monoid::op(dat[i], val);
            } else {
                while(i < n) {
                    propagate(i);
                    i = (i << 1) | 1;
                    if(f(Monoid::op(dat[i], val))) {
                        val = Monoid::op(dat[i], val);
                        i ^= 1;
                    }
                }
                return i - n + 1;
            }
        }
        return 0;
    }

    int size() { return n; }
    MonoidType operator[](int i) { return fold(i, i + 1); }
    MonoidType get(int i) { return fold(i, i + 1); }

private:
    int n;
    vector<MonoidType> dat;
    vector<OperatorType> lazy;
    vi indices, cand, cand_l, cand_r;
    void generate_indices(int l, int r) {
        indices.clear();
        l += n;
        r += n;
        int lm = (l / (l & -l)) >> 1, rm = (r / (r & -r)) >> 1;
        while(l < r) {
            if(l <= lm) indices.push_back(l);
            if(r <= rm) indices.push_back(r);
            l >>= 1;
            r >>= 1;
        }
        while(l) {
            indices.push_back(l);
            l >>= 1;
        }
    }
    void propagate(int i) {
        if(i < n) {
            lazy[i << 1] = Operator::op(lazy[i << 1], lazy[i]);
            lazy[i << 1 | 1] = Operator::op(lazy[i << 1 | 1], lazy[i]);
            dat[i << 1] = mapping(dat[i << 1], lazy[i]);
            dat[i << 1 | 1] = mapping(dat[i << 1 | 1], lazy[i]);
        }
        lazy[i] = Operator::id();
    }
    void pushdown() {
        for(int j = (int)indices.size() - 1; j >= 0; j--) {
            int i = indices[j];
            propagate(i);
        }
    }
    void pushup() {
        rep(j, (int)indices.size()) {
            int i = indices[j];
            dat[i] = Monoid::op(dat[i << 1], dat[i << 1 | 1]);
        }
    }
};

//------>8------ begin kyopro_library/others/monoid.hpp ------>8------

/// @brief モノイド
/// @ref verify: https://judge.yosupo.jp/problem/staticrmq
namespace Monoid {
    /// @brief Minモノイド
    /// @tparam max_value 単位元
    template <typename T, T max_value = inf<T>>
    struct Min {
        using Type = T;
        static Type id() { return max_value; }
        static Type op(const Type& a, const Type& b) { return min(a, b); }
    };

    /// @brief Maxモノイド
    /// @tparam min_value 単位元
    template <typename T, T min_value = -inf<T>>
    struct Max {
        using Type = T;
        static Type id() { return min_value; }
        static Type op(const Type& a, const Type& b) { return max(a, b); }
    };

    /// @brief 和
    template <typename T>
    struct Sum {
        using Type = T;
        static Type id() { return 0; }
        static Type op(const Type& a, const Type& b) { return a + b; }
    };

    /// @brief （和，区間の長さ）
    template <typename T>
    struct SumPair {
        using Type = pair<T, int>;
        static Type id() { return make_pair(T(0), 0); }
        static Type op(const Type& a, const Type& b) { return {a.first + b.first, a.second + b.second}; }
    };

    template <typename T, T not_exist>
    struct Update {
        using Type = T;
        static Type id() { return not_exist; }
        static Type op(const Type& a, const Type& b) { return b == id() ? a : b; }
    };

    /// @brief 一次関数 f(x) = a x + b の合成モノイド
    /// @details Type は pair<T, T> = (a, b)。op(f, g) は「f を適用してから g を適用する」合成 g∘f を返す。
    /// セグ木の fold(l, r) はそのまま f_{r-1}(...f_l(x)) の合成になる。
    /// @tparam T 係数の型（modint など、+ と * を持つ体）
    template <typename T>
    struct Affine {
        using Type = pair<T, T>;
        static Type id() { return {T(1), T(0)}; }
        static Type op(const Type& f, const Type& g) {
            /* g(f(x)) = g.a (f.a x + f.b) + g.b = (g.a f.a) x + (g.a f.b + g.b) */
            return {g.first * f.first, g.first * f.second + g.second};
        }
        /// @brief f(x) を評価する
        static T eval(const Type& f, const T& x) { return f.first * x + f.second; }
    };

    /// @brief 多数決（Boyer–Moore）モノイド。Type = (候補, 票差)。区間に過半数の要素があれば候補はそれに一致する
    /// @details 候補が本当に過半数かは別途出現回数を数えて確認する必要がある
    template <typename T>
    struct BoyerMoore {
        using Type = pair<T, ll>;
        static Type id() { return {T(), 0}; }
        static Type op(const Type& a, const Type& b) {
            /* 同じ候補なら票を足す。違えば票の多い方が残り、票差は減る（過半数の要素は決して打ち消し切られない） */
            if(a.first == b.first) return {a.first, a.second + b.second};
            if(a.second >= b.second) return {a.first, a.second - b.second};
            return {b.first, b.second - a.second};
        }
    };
}  // namespace Monoid
//------>8------- end kyopro_library/others/monoid.hpp ------->8------

namespace RangeQuery {
    /// @brief 区間更新 / 区間min
    /// @tparam max_value 最大値
    /// @tparam not_exist 存在しない値
    template <typename T, T max_value, T not_exist>
    struct ApplyUpdate_GetMin {
        static T mapping(const T& a, const T& b) { return b == not_exist ? a : b; }
        using Type = struct SegTreeLazy<Monoid::Min<T, max_value>, Monoid::Update<T, not_exist>, mapping>;
    };

    /// @brief 区間更新 / 区間max
    /// @tparam min_value 最小値
    /// @tparam not_exist 存在しない値
    template <typename T, T min_value, T not_exist>
    struct ApplyUpdate_GetMax {
        static T mapping(const T& a, const T& b) { return b == not_exist ? a : b; }
        using Type = struct SegTreeLazy<Monoid::Max<T, min_value>, Monoid::Update<T, not_exist>, mapping>;
    };

    /// @brief 区間更新 / 区間和
    /// @tparam not_exist 存在しない値
    template <typename T, T not_exist>
    struct ApplyUpdate_GetSum {
        using S = typename Monoid::SumPair<T>::Type;
        static S mapping(const S& a, const T& b) { return b == not_exist ? a : S{b * a.second, a.second}; }
        using Type = struct SegTreeLazy<Monoid::SumPair<T>, Monoid::Update<T, not_exist>, mapping>;
    };

    /// @brief 区間加算 / 区間min
    template <typename T, T max_value>
    struct ApplyAdd_GetMin {
        static T mapping(const T& a, const T& b) { return a + b; }
        using Type = struct SegTreeLazy<Monoid::Min<T, max_value>, Monoid::Sum<T>, mapping>;
    };

    /// @brief 区間加算 / 区間max
    template <typename T, T min_value>
    struct ApplyAdd_GetMax {
        static T mapping(const T& a, const T& b) { return a + b; }
        using Type = struct SegTreeLazy<Monoid::Max<T, min_value>, Monoid::Sum<T>, mapping>;
    };

    /// @brief 区間加算 / 区間和
    template <typename T>
    struct ApplyAdd_GetSum {
        using S = typename Monoid::SumPair<T>::Type;
        static S mapping(const S& a, const T& b) { return {a.first + b * a.second, a.second}; }
        using Type = struct SegTreeLazy<Monoid::SumPair<T>, Monoid::Sum<T>, mapping>;
    };
}  // namespace RangeQuery
//------>8 end kyopro_library/data_structure/segtree_lazy.hpp >8------

struct Mono {
    using Type = ii3;  // val, len, even
    static Type op(Type l, Type r) {
        auto [lval, llen, leven] = l;
        auto [rval, rlen, reven] = r;
        return {lval + rval, llen + rlen, leven + reven};
    }
    static Type id() {
        return {0, 0, 0};
    }
};

struct Ope {
    using Type = ii3;  // fi,fl,se
    static Type op(Type l, Type r) {
        if(l[1]) {
            if(!r[1]) {
                assert(r[2] == 0);
                l[2] += r[0];
            } else {
                l[0] = l[0] + l[2] + r[0];
                l[2] = r[2];
            }
        } else {
            if(!r[1]) {
                assert(r[2] == 0);
                l[0] += r[0];
            } else {
                l[0] += r[0];
                l[2] = r[2];
                l[1] = 1;
            }
        }
        return l;
    }
    static Type id() { return {0, 0, 0}; }
};

typename Mono::Type mapping(typename Mono::Type x, typename Ope::Type f) {
    auto& [val, len, even] = x;
    ii odd = len - even;
    auto& [fi, fl, se] = f;
    val += len * fi;
    if(fi % 2) swap(even, odd);
    if(fl) val = odd;
    val += se * len;
    if(se % 2) swap(even, odd);
    return x;
}

void run() {
    II(N, Q);
    VI(A, N);

    V<ii3> init(N);
    rep(i, N) init[i] = {A[i], 1, 1 - A[i] % 2};

    SegTreeLazy<Mono, Ope, mapping> range(init);

    rep(Q) {
        II(T);
        IDX(L, R);
        R++;

        if(T == 1) {
            range.apply(L, R, {0, 1, 0});
        } else if(T == 2) {
            II(X);
            range.apply(L, R, {X, 0, 0});
        } else {
            say(range.fold(L, R)[0]);
        }
    }
}

#else

// Created: 2026-10-07 03:09:13
// Copied:  2026-10-07 03:32:18
// #define MULTI
//------>8-------- begin kyopro_library/template.hpp --------->8------
//---------------->8----------------------------------------------------->8----------------
//
//
//
//
//
//
//
//
//
//
//
//
//
//
//---------------->8----------------------------------------------------->8----------------

//------>8------ begin kyopro_library/base/include.hpp ------->8------

#include <iostream>
#include <algorithm>
#include <type_traits>
#include <vector>
#include <array>
#include <bitset>
#include <cmath>
#include <complex>
#include <deque>
#include <functional>
#include <iomanip>
#include <map>
#include <set>
#include <queue>
#include <random>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <climits>
#include <utility>
#include <chrono>
#include <cstring>
#include <cstdlib>
#include <cerrno>
#include <cassert>
#include <unistd.h>

using namespace std;
//------>8------- end kyopro_library/base/include.hpp -------->8------

//------>8-------- begin kyopro_library/base/type.hpp -------->8------

using i8 = int8_t;
using i16 = int16_t;
using i32 = int32_t;
using i64 = int64_t;
using i128 = __int128_t;
using u8 = uint8_t;
using u16 = uint16_t;
using u32 = uint32_t;
using u64 = unsigned long long;
using u128 = __uint128_t;
using f64 = double;
using f80 = long double;

using ii = i64;
template <typename T>
struct myvec : vector<T> {
    using vector<T>::vector;
    T operator[](ii n) const {
        return this->at(n);
    }
    T& operator[](ii n) {
        return this->at(n);
    }
};

using ll = i64;
using ull = u64;
using vi = myvec<ii>;
using vvi = myvec<myvec<ii>>;
using vvvi = myvec<myvec<myvec<ii>>>;
using vl = myvec<ll>;
using vvl = myvec<myvec<ll>>;
using vvvl = myvec<myvec<myvec<ll>>>;
using ii3 = array<ii, 3>;
using ii4 = array<ii, 4>;
using ii5 = array<ii, 5>;
using lll = i128;
using vlll = myvec<lll>;
using vvlll = myvec<myvec<lll>>;
using ulll = u128;
using ld = f80;
using str = string;
using vstr = myvec<str>;
constexpr ii operator""_ii(ull x) { return static_cast<ii>(x); }
constexpr lll operator""_lll(ull x) { return static_cast<lll>(x); }

template <typename T>
using V = myvec<T>;
template <typename T>
using VV = myvec<myvec<T>>;
template <typename T>
using VVV = myvec<myvec<myvec<T>>>;
template <typename T>
using VVVV = myvec<myvec<myvec<myvec<T>>>>;
template <typename T>
using VVVVV = myvec<myvec<myvec<myvec<myvec<T>>>>>;
template <typename T>
using VVVVVV = myvec<myvec<myvec<myvec<myvec<myvec<T>>>>>>;

template <typename T>
using max_pq = priority_queue<T>;
template <typename T>
using min_pq = priority_queue<T, myvec<T>, greater<T>>;
template <typename T>
using unset = unordered_set<T>;
template <typename T, typename T2>
using unmap = unordered_map<T, T2>;

template <typename T, typename U>
struct PR : pair<T, U> {
    template <typename... Args>
    PR(Args... args) : pair<T, U>(args...) {}
    PR() = default;
    using pair<T, U>::first;
    using pair<T, U>::second;
    PR& operator+=(const PR& r) {
        first += r.first;
        second += r.second;
        return *this;
    }
    PR& operator-=(const PR& r) {
        first -= r.first;
        second -= r.second;
        return *this;
    }
    PR& operator*=(const PR& r) {
        first *= r.first;
        second *= r.second;
        return *this;
    }
    template <typename S>
    PR& operator+=(const S& r) {
        first += r;
        second += r;
        return *this;
    }
    template <typename S>
    PR& operator-=(const S& r) {
        first -= r;
        second -= r;
        return *this;
    }
    template <typename S>
    PR& operator*=(const S& r) {
        first *= r;
        second *= r;
        return *this;
    }
    PR operator+(const PR& r) const { return PR(*this) += r; }
    PR operator-(const PR& r) const { return PR(*this) -= r; }
    PR operator*(const PR& r) const { return PR(*this) *= r; }
    template <typename S>
    PR operator+(const S& r) const { return PR(*this) += r; }
    template <typename S>
    PR operator-(const S& r) const { return PR(*this) -= r; }
    template <typename S>
    PR operator*(const S& r) const { return PR(*this) *= r; }
    PR operator-() const { return PR{-first, -second}; }
};
using pi = PR<ii, ii>;
using vpi = myvec<pi>;
using vvpi = myvec<myvec<pi>>;
using pl = PR<ll, ll>;
using vpl = myvec<pl>;
using vvpl = myvec<myvec<pl>>;

template <typename T, typename U, typename V>
struct TR : tuple<T, U, V> {
    using tuple<T, U, V>::tuple;
    T& x = get<0>(*this);
    U& y = get<1>(*this);
    V& z = get<2>(*this);
    TR() : tuple<T, U, V>() {}
    TR(const T& a, const U& b, const V& c) : tuple<T, U, V>(a, b, c) {}
    TR(const TR& other) : tuple<T, U, V>(other), x(get<0>(*this)), y(get<1>(*this)), z(get<2>(*this)) {}
    TR(TR&& other) noexcept : tuple<T, U, V>(move(other)), x(get<0>(*this)), y(get<1>(*this)), z(get<2>(*this)) {}
    TR& operator=(const TR& other) {
        tuple<T, U, V>::operator=(other);
        return *this;
    }
    TR& operator=(TR&& other) noexcept {
        tuple<T, U, V>::operator=(move(other));
        return *this;
    }
};
using ti = TR<ii, ii, ii>;
using vti = myvec<ti>;
using vvti = myvec<myvec<ti>>;
using tl = TR<ll, ll, ll>;
using vtl = myvec<ti>;
using vvtl = myvec<myvec<tl>>;

const i32 INFI = 1e9 + 10;
const i64 INFL = 4e18;
const i128 INFLL = 1_lll << 120;

template <typename T>
constexpr T inf = 0;
template <>
constexpr i32 inf<i32> = INFI;
template <>
constexpr i64 inf<i64> = INFL;
template <>
constexpr i128 inf<i128> = INFLL;
template <>
constexpr u32 inf<u32> = INFI;
template <>
constexpr u64 inf<u64> = INFL;
template <>
constexpr u128 inf<u128> = INFLL;
template <>
constexpr f64 inf<f64> = numeric_limits<f64>::infinity();
template <>
constexpr f80 inf<f80> = numeric_limits<f80>::infinity();

istream& operator>>(istream& is, lll& x) {
    int c = is.peek();
    while(c == ' ' || c == '\n') is.get(), c = is.peek();
    bool neg = false;
    if(c == '-') neg = true, is.get();
    x = 0;
    while(isdigit(is.peek())) x = x * 10 + is.get() - '0';
    if(neg) x = -x;
    return is;
}

ostream& operator<<(ostream& os, lll x) {
    if(x < 0) os << '-', x = -x;
    if(x == 0) return os << '0';
    string s;
    while(x > 0) s += char('0' + x % 10), x /= 10;
    reverse(s.begin(), s.end());
    return os << s;
}

#ifdef TDY
lll abs(lll x) {
    if(x < 0) return -x;
    return x;
}
lll gcd(lll a, lll b) {
    while(b) a %= b, swap(a, b);
    return a;
}
#endif
//------>8--------- end kyopro_library/base/type.hpp --------->8------

// #include "kyopro_library/base/fastio.hpp"
// #include "kyopro_library/base/fastio_impl.hpp"
//------>8------- begin kyopro_library/base/macro.hpp -------->8------

#define rep1(n) for(ii i = 0; i < (n); i++)
#define rep2(i, n) for(ii i = 0; i < (n); i++)
#define rep3(i, a, b) for(ii i = (a); i < (b); i++)
#define rep4(i, a, b, c) for(ii i = (a); i < (b); i += (c))
#define rep_overload(a, b, c, d, e, ...) e
#define rep(...) rep_overload(__VA_ARGS__, rep4, rep3, rep2, rep1)(__VA_ARGS__)

#define per1(n) for(ii i = (n) - 1; i >= 0; i--)
#define per2(i, n) for(ii i = (n) - 1; i >= 0; i--)
#define per3(i, a, b) for(ii i = (b) - 1; i >= (a); i--)
#define per4(i, a, b, c) for(ii i = (b) - 1; i >= (a); i -= (c))
#define per_overload(a, b, c, d, e, ...) e
#define per(...) per_overload(__VA_ARGS__, per4, per3, per2, per1)(__VA_ARGS__)

#define fore(x, a) for(auto& x : a)

#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()

#define QYN(q, a, b) ((q) ? (a) : (b))

#define pb push_back
#define eb emplace_back
#define mkp make_pair
#define mkt make_tuple
#define fi first
#define se second

// vの各要素にfを作用させる
#define dov(v, f)         \
    [&]() {               \
        auto&& _v = (v);  \
        for(auto& x : _v) \
            f(x);         \
    }()
// vの各要素xに対してf(x)からなる配列を返す
#define mkv(v, f)                                            \
    [&]() {                                                  \
        auto&& _v = (v);                                     \
        using Type = std::decay_t<decltype(f(*_v.begin()))>; \
        V<Type> ret;                                         \
        ret.reserve(_v.size());                              \
        for(const auto& x : _v)                              \
            ret.push_back(f(x));                             \
        return ret;                                          \
    }()

// 宣言&入力
#define II(...)     \
    ii __VA_ARGS__; \
    input(__VA_ARGS__)
#define LL(...)     \
    ll __VA_ARGS__; \
    input(__VA_ARGS__)
#define LLL(...)     \
    lll __VA_ARGS__; \
    input(__VA_ARGS__)
#define IDX(...)        \
    ii __VA_ARGS__;     \
    input(__VA_ARGS__); \
    input_index(__VA_ARGS__)
#define STR(...)        \
    string __VA_ARGS__; \
    input(__VA_ARGS__);
#define CHR(...)      \
    char __VA_ARGS__; \
    input(__VA_ARGS__);
#define LD(...)     \
    ld __VA_ARGS__; \
    input(__VA_ARGS__);
#define VI(A, N)     \
    vector<ii> A(N); \
    input(A);
#define VVI(A, N, M)                        \
    vector<vector<ii>> A(N, vector<ii>(M)); \
    input(A);
#define VL(A, N)     \
    vector<ll> A(N); \
    input(A);
#define VVL(A, N, M)                        \
    vector<vector<ll>> A(N, vector<ll>(M)); \
    input(A);
#define VPI(A, N) \
    vpi A(N);     \
    input(A);
#define VTI(A, N) \
    vti A(N);     \
    input(A);
#define VI2(A, B, N)       \
    vector<ii> A(N), B(N); \
    rep(i, N) cin >> A[i] >> B[i];
#define VL2(A, B, N)       \
    vector<ll> A(N), B(N); \
    rep(i, N) cin >> A[i] >> B[i];
#define VI3(A, B, C, N)          \
    vector<ii> A(N), B(N), C(N); \
    rep(i, N) cin >> A[i] >> B[i] >> C[i];
#define VL3(A, B, C, N)          \
    vector<ll> A(N), B(N), C(N); \
    rep(i, N) cin >> A[i] >> B[i] >> C[i];
#define VI4(A, B, C, D, N)             \
    vector<ii> A(N), B(N), C(N), D(N); \
    rep(i, N) cin >> A[i] >> B[i] >> C[i] >> D[i];
#define VST(A, N)        \
    vector<string> A(N); \
    input(A);
#define IN2(A, B) rep(i, siz(A)) cin >> A[i] >> B[i];
#define IN3(A, B, C) rep(i, siz(A)) cin >> A[i] >> B[i] >> C[i];
#define IN4(A, B, C, D) rep(i, siz(A)) cin >> A[i] >> B[i] >> C[i] >> D[i];
#define IN5(A, B, C, D, E) \
    rep(i, siz(A)) cin >> A[i] >> B[i] >> C[i] >> D[i] >> E[i];
//------>8-------- end kyopro_library/base/macro.hpp --------->8------

//------>8--------- begin kyopro_library/base/io.hpp --------->8------

const char NL = '\n';
void flush() { cout.flush(); }

const string Yes = "Yes";
const string No = "No";
const string YES = "YES";
const string NO = "NO";
const string ALICE = "Alice";
const string BOB = "Bob";
const string FIRST = "First";
const string SECOND = "Second";
inline string YesNo(bool f) { return f ? Yes : No; }
inline string YESNO(bool f) { return f ? YES : NO; }
inline string AliBo(bool f) { return f ? ALICE : BOB; }
inline string FiSe(bool f) { return f ? FIRST : SECOND; }

template <typename T>
istream& operator>>(istream& is, vector<vector<T>>& v) {
    for(auto& x : v)
        for(auto& y : x) is >> y;
    return is;
}
template <typename T>
istream& operator>>(istream& is, vector<T>& v) {
    for(auto& x : v) is >> x;
    return is;
}
template <typename T1, typename T2>
istream& operator>>(istream& is, pair<T1, T2>& p) {
    is >> p.first >> p.second;
    return is;
}

template <class... T>
void input(T&... a) { (cin >> ... >> a); }

template <class T>
void input_index(T& a) { a--; }
template <class T, class... Ts>
void input_index(T& a, Ts&... b) {
    a--;
    input_index(b...);
}

template <typename T1, typename T2>
ostream& operator<<(ostream& os, const pair<T1, T2>& p) {
    os << p.fi << ' ' << p.se;
    return os;
}
template <typename T1, typename T2>
ostream& operator<<(ostream& os, const PR<T1, T2>& p) {
    os << p.fi << ' ' << p.se;
    return os;
}
template <typename T1, typename T2, typename T3>
ostream& operator<<(ostream& os, const tuple<T1, T2, T3>& t) {
    os << ' ' << get<0>(t) << ' ' << get<1>(t) << ' ' << get<2>(t);
    return os;
}
template <typename T1, typename T2, typename T3>
ostream& operator<<(ostream& os, const TR<T1, T2, T3>& t) {
    os << ' ' << get<0>(t) << ' ' << get<1>(t) << ' ' << get<2>(t);
    return os;
}
template <typename T1, typename T2, typename T3, typename T4>
ostream& operator<<(ostream& os, const tuple<T1, T2, T3, T4>& t) {
    os << ' ' << get<0>(t) << ' ' << get<1>(t) << ' ' << get<2>(t) << ' ' << get<3>(t);
    return os;
}
template <typename T>
ostream& operator<<(ostream& os, const vector<vector<vector<T>>>& a) {
    int I = a.size();
    for(int i = 0; i < I; i++) {
        int J = a[i].size();
        for(int j = 0; j < J; j++) {
            int K = a[i][j].size();
            for(int k = 0; k < K; k++) {
                os << a[i][j][k];
                if(k != K - 1) os << ' ';
            }
            os << NL;
        }
        if(i != I - 1) os << NL;
    }
    return os;
}
template <typename T>
ostream& operator<<(ostream& os, const vector<vector<T>>& a) {
    int I = a.size();
    for(int i = 0; i < I; i++) {
        int J = a[i].size();
        for(int j = 0; j < J; j++) {
            os << a[i][j];
            if(j != J - 1) os << ' ';
        }
        if(i != I - 1) cout << NL;
    }
    return os;
}
template <typename T>
ostream& operator<<(ostream& os, const vector<T>& a) {
    int n = a.size();
    for(int i = 0; i < n; i++) {
        os << a[i];
        if(i != n - 1) os << ' ';
    }
    return os;
}

template <typename T>
ostream& operator<<(ostream& os, const set<T>& a) {
    for(auto itr = a.begin(); itr != a.end(); itr++) {
        os << *itr;
        if(next(itr) != a.end()) os << ' ';
    }
    return os;
}
template <typename T>
ostream& operator<<(ostream& os, const multiset<T>& a) {
    for(auto itr = a.begin(); itr != a.end(); itr++) {
        os << *itr;
        if(next(itr) != a.end()) os << ' ';
    }
    return os;
}
template <typename T>
ostream& operator<<(ostream& os, const deque<T>& a) {
    for(auto itr = a.begin(); itr != a.end(); itr++) {
        os << *itr;
        if(next(itr) != a.end()) os << ' ';
    }
    return os;
}
template <typename T>
ostream& operator<<(ostream& os, queue<T> a) {
    while(!a.empty()) {
        os << a.front();
        a.pop();
        if(a.size()) os << ' ';
    }
    return os;
}
template <typename T>
ostream& operator<<(ostream& os, priority_queue<T> a) {
    while(!a.empty()) {
        os << a.top();
        a.pop();
        if(a.size()) os << ' ';
    }
    return os;
}
template <typename T>
ostream& operator<<(ostream& os, priority_queue<T, vector<T>, greater<T>> a) {
    while(!a.empty()) {
        os << a.top();
        a.pop();
        if(a.size()) os << ' ';
    }
    return os;
}
template <typename T, auto N>
ostream& operator<<(ostream& os, array<T, N> a) {
    for(int i = 0; i < N; i++) {
        os << a[i];
        if(i != N - 1) os << ' ';
    }
    return os;
}

template <class T, class... Ts>
void put(const T& a, const Ts&... b) {
    cout << a;
    (void)(cout << ... << b);
}

template <class T, class... Ts>
void line(const T& a, const Ts&... b) {
    cout << a;
    (void)(cout << ... << (cout << ' ', b));
    cout << ' ';
}

void say() { cout << '\n'; }
template <class T, class... Ts>
void say(const T& a, const Ts&... b) {
    cout << a;
    (void)(cout << ... << (cout << ' ', b));
    cout << NL;
}

void esay() {
#ifdef TDY
    flush();
    cerr << NL;
#endif
}
template <class T, class... Ts>
void esay(const T& a, const Ts&... b) {
#ifdef TDY
    flush();
    cerr << a;
    (void)(cerr << ... << (cerr << ' ', b));
    cerr << NL;
#endif
}

#define O(...)            \
    {                     \
        say(__VA_ARGS__); \
        return;           \
    }
//------>8---------- end kyopro_library/base/io.hpp ---------->8------

//------>8-------- begin kyopro_library/base/util.hpp -------->8------

// 便利関数たち

// https://trap.jp/post/1224/
template <class... T>
constexpr auto min(T... a) {
    return min(initializer_list<common_type_t<T...>>{a...});
}

template <class... T>
constexpr auto max(T... a) {
    return max(initializer_list<common_type_t<T...>>{a...});
}

template <typename A, typename B>
bool chmin(A& a, B b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}

template <typename A, typename B>
bool chmax(A& a, B b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}

// A/B以下の最大の整数
template <typename A, typename B>
constexpr common_type_t<A, B> myfloor(A a, B b) {
    assert(b != 0);
    if(b < 0) a = -a, b = -b;
    return a / b - (a % b < 0);
}

// A/B以上の最小の整数
template <typename A, typename B>
constexpr common_type_t<A, B> myceil(A a, B b) {
    assert(b != 0);
    if(b < 0) a = -a, b = -b;
    return a / b + (a % b > 0);
}

// A%B(in [0,B))
template <typename A, typename B>
constexpr common_type_t<A, B> mymod(A a, B b) {
    assert(b != 0);
    if(b < 0) b = -b;
    if(a > 0) return a % b;
    return (a % b + b) % b;
}

// LCM
template <typename A, typename B>
constexpr common_type_t<A, B> mylcm(A a, B b) {
    using T = common_type_t<A, B>;
    T g = gcd<T>(a, b);
    return T(a) / g * b;
}

template <typename T>
inline ii siz(const T& v) { return v.size(); }

template <typename T>
T minv(const vector<T>& v) {
    if(v.empty()) return inf<T>;
    return *min_element(all(v));
}
template <typename T>
T maxv(const vector<T>& v) {
    if(v.empty()) return -inf<T>;
    return *max_element(all(v));
}
template <typename T>
ii minidx(const V<T>& v) { return min_element(all(v)) - v.begin(); }
template <typename T>
ii maxidx(const V<T>& v) { return max_element(all(v)) - v.begin(); }
template <typename T>
T sumv(const vector<T>& v) { return reduce(v.begin(), v.end()); }
template <typename T>
ii lob(const vector<T>& v, const T& x) { return lower_bound(all(v), x) - v.begin(); }
template <typename T>
ii upb(const V<T>& v, const T& x) { return upper_bound(all(v), x) - v.begin(); }
template <typename T>
ii findv(const V<T>& v, const T& x) {
    for(ii i = 0; i < siz(v); i++)
        if(v[i] == x) return i;
    return siz(v);
}
template <typename T>
ii find_lastv(const V<T>& v, const T& x) {
    for(ii i = siz(v) - 1; i >= 0; i--)
        if(v[i] == x) return i;
    return -1;
}

// do~~ 破壊的に変える
// mk~~ 新しく作る

// ソート
template <typename T>
void doso(T& v) {
    sort(v.begin(), v.end());
}

template <typename T>
T mkso(const T& v) {
    auto w = v;
    doso(w);
    return w;
}

// 逆順ソート
template <typename T>
void dosor(T& v) {
    sort(v.rbegin(), v.rend());
}

template <typename T>
T mksor(const T& v) {
    auto w = v;
    dorsort(w);
    return w;
}

// ソート→重複削除
template <typename T>
void douniq(V<T>& v) {
    sort(all(v));
    v.erase(unique(v.begin(), v.end()), v.end());
}

template <typename T>
V<T> mkuniq(const V<T>& v) {
    auto w = v;
    douniq(w);
    return w;
}

// 座標圧縮
template <typename T>
V<T> mkcomp(V<T> v) {
    auto w = v;
    douniq(w);
    for(T& x : v) x = lob(w, x);
    return v;
}

// aの中のvの個数を返す
ii countv(const auto& a, auto v) {
    return count(a.begin(), a.end(), v);
}

// aのidx番目にvを挿入する（..., a[idx-1], v, a[idx], ...）
void doinsert(auto& a, ii idx, auto v) {
    assert(idx <= siz(a));
    a.insert(a.begin() + idx, v);
}

auto mkinsert(const auto& a, ii idx, auto v) {
    auto b = a;
    doinsert(b, idx, v);
    return b;
}

// aのidx番目を削除する
void doerase(auto& a, ii idx) {
    assert(idx < siz(a));
    a.erase(a.begin() + idx);
}

auto mkerase(const auto& a, ii idx) {
    auto b = a;
    doerase(b, idx);
    return b;
}

// 先頭をoffset個分後ろに
void dorotateback(auto& a, ii offset) {
    offset %= siz(a);
    rotate(a.begin(), a.end() - offset, a.end());
}

// 末尾をoffset個分前の方に
void dorotatefront(auto& a, ii offset) {
    offset %= siz(a);
    rotate(a.begin(), a.begin() + offset, a.end());
}

auto mkpush(const auto& a, auto v) {
    auto b = a;
    b.push_back(v);
    return b;
}

// aの[l,r)を抜き出す
template <typename T>
V<T> mkslice(const V<T>& a, ii l, ii r) {
    assert(l <= r && l >= 0 && r <= siz(a));
    V<T> b(a.begin() + l, a.begin() + r);
    return b;
}

// aとbを連結した配列を返す
template <typename T>
V<T> mkconcat(const V<T>& a, const V<T>& b) {
    auto ret = a;
    ret.reserve(siz(a) + siz(b));
    for(auto x : b) ret.push_back(x);
    return ret;
}

// aの後ろにbをくっつける
// a <<= bと同じ
template <typename T>
void doconcat(V<T>& a, const V<T>& b) {
    for(auto x : b) a.push_back(x);
}

// a,bから{(a[0],b[0]), (a[1],b[1]), ...}を作る めっちゃ便利
template <typename A, typename B>
vector<PR<A, B>> zip(const vector<A>& a, const vector<B>& b) {
    ii n = siz(a);
    vector<PR<A, B>> ret(n);
    for(ii i = 0; i < n; i++) ret[i] = {a[i], b[i]};
    return ret;
}

template <typename A, typename B, typename C>
vector<tuple<A, B, C>> zip(const vector<A>& a, const vector<B>& b, const vector<C>& c) {
    ii n = siz(a);
    vector<tuple<A, B, C>> ret(n);
    for(ii i = 0; i < n; i++) ret[i] = {a[i], b[i], c[i]};
    return ret;
}

template <typename A, typename B>
PR<vector<A>, vector<B>> unzip(const vector<PR<A, B>>& p) {
    ii n = siz(p);
    vector<A> reta(n);
    vector<B> retb(n);
    for(ii i = 0; i < n; i++) {
        reta[i] = p[i].first;
        retb[i] = p[i].second;
    }
    return mkp(reta, retb);
}

template <typename A, typename B, typename C>
TR<vector<A>, vector<B>, vector<C>> unzip(const vector<TR<A, B, C>>& p) {
    ii n = siz(p);
    vector<A> reta(n);
    vector<B> retb(n);
    vector<C> retc(n);
    for(ii i = 0; i < n; i++) {
        auto [a, b, c] = p[i];
        reta[i] = a;
        retb[i] = b;
        retc[i] = c;
    }
    return mkt(reta, retb, retc);
}

template <typename T>
T pick(max_pq<T>& v) {
    T ret = v.top();
    v.pop();
    return ret;
}
template <typename T>
T pick(min_pq<T>& v) {
    T ret = v.top();
    v.pop();
    return ret;
}
template <typename T>
T pick(queue<T>& v) {
    T ret = v.front();
    v.pop();
    return ret;
}
template <typename T>
T pick(vector<T>& v) {
    T ret = v.back();
    v.pop_back();
    return ret;
}
template <typename T>
T pickf(deque<T>& v) {
    T ret = v.front();
    v.pop_front();
    return ret;
}
template <typename T>
T pickb(deque<T>& v) {
    T ret = v.back();
    v.pop_back();
    return ret;
}

template <typename T>
bool nxperm(T& v) { return next_permutation(v.begin(), v.end()); }

// 前置インクリメント (++v)
template <typename T>
vector<T>& operator++(vector<T>& a) {
    for(auto& x : a) ++x;
    return a;
}
// 後置インクリメント (v++)
template <typename T>
vector<T> operator++(vector<T>& a, int) {
    vector<T> res = a;
    ++a;
    return res;
}
// 前置デクリメント (--v)
template <typename T>
vector<T>& operator--(vector<T>& a) {
    for(auto& x : a) --x;
    return a;
}
// 後置デクリメント (v--)
template <typename T>
vector<T> operator--(vector<T>& a, int) {
    vector<T> res = a;
    --a;
    return res;
}

template <typename T, typename U>
vector<T> operator>>=(const U& b, vector<T>& a) {
    a.insert(a.begin(), b);
    return a;
}
template <typename T, typename U>
vector<T> operator>>(const U& b, vector<T> a) {
    b >>= a;
    return a;
}

template <typename T, typename U>
vector<T> operator<<=(vector<T>& a, const U& b) {
    a.push_back(b);
    return a;
}
template <typename T, typename U>
void operator<<=(vector<T>& a, const vector<U>& b) {
    vector<T> ret = a;
    for(const auto& x : b) ret.push_back(x);
    a = ret;
}
template <typename T, typename U>
vector<T> operator<<(vector<T> a, const U& b) {
    a <<= b;
    return a;
}
template <typename T, typename U>
vector<T> operator<<(vector<T> a, const vector<U>& b) {
    a <<= b;
    return a;
}

// 演算子オーバーロードを一括定義するマクロ
#define DEFINE_VECTOR_OP(OP)                                      \
    /* vector<T> OP= スカラー */                              \
    template <typename T, typename U>                             \
    vector<T>& operator OP##=(vector<T>& a, const U & b) {        \
        for(auto& x : a) x OP## = b;                              \
        return a;                                                 \
    }                                                             \
    /* vector<T> OP= vector<U> (ベクトル同士) */            \
    template <typename T, typename U>                             \
    vector<T>& operator OP##=(vector<T>& a, const vector<U>& b) { \
        assert(a.size() == b.size());                             \
        for(ii i = 0; i < a.size(); i++) a[i] OP## = b[i];        \
        return a;                                                 \
    }                                                             \
    /* vector<T> OP スカラー */                               \
    template <typename T, typename U>                             \
    vector<T> operator OP(vector<T> a, const U & b) {             \
        a OP## = b;                                               \
        return a;                                                 \
    }                                                             \
    /* スカラー OP vector<T> */                               \
    template <typename T, typename U>                             \
    vector<T> operator OP(const U & a, vector<T> b) {             \
        for(auto& x : b) x = a OP x;                              \
        return b;                                                 \
    }                                                             \
    /* vector<T> OP vector<U> (ベクトル同士) */             \
    template <typename T, typename U>                             \
    vector<T> operator OP(vector<T> a, const vector<U>& b) {      \
        a OP## = b;                                               \
        return a;                                                 \
    }

DEFINE_VECTOR_OP(+)
DEFINE_VECTOR_OP(-)
DEFINE_VECTOR_OP(*)
DEFINE_VECTOR_OP(/)
DEFINE_VECTOR_OP(%)
DEFINE_VECTOR_OP(&)
DEFINE_VECTOR_OP(|)
DEFINE_VECTOR_OP(^)

#undef DEFINE_VECTOR_OP

// 多次元のvectorを作る
// initで型が推論されるので注意
template <typename T>
V<T> mkvec(ii n, T init) {
    return V<T>(n, init);
}
template <typename... Ts>
auto mkvec(ii n, Ts... ts) {
    return V<decltype(mkvec(ts...))>(n, mkvec(ts...));
}

// 累積和
template <typename T = i64, typename U>
vector<T> mksum(const vector<U>& v) {
    ii n = siz(v);
    V<T> ret(n + 1);
    for(ii i = 0; i < n; i++) ret[i + 1] = ret[i] + v[i];
    return ret;
}

// 累積max
template <typename T>
V<T> mkprefmax(const V<T>& v) {
    ii n = siz(v);
    V<T> ret(n + 1, -inf<T>);
    for(ii i = 0; i < n; i++) ret[i + 1] = max(ret[i], v[i]);
    return ret;
}

// 累積min
template <typename T>
V<T> mkprefmin(const V<T>& v) {
    ii n = siz(v);
    V<T> ret(n + 1, inf<T>);
    for(ii i = 0; i < n; i++) ret[i + 1] = min(ret[i], v[i]);
    return ret;
}

template <typename T>
V<T> mksuffmax(const V<T>& v) {
    ii n = siz(v);
    V<T> ret(n + 1, -inf<T>);
    for(ii i = n - 1; i >= 0; i--) ret[i] = max(ret[i + 1], v[i]);
    return ret;
}

template <typename T>
V<T> mksuffmin(const V<T>& v) {
    ii n = siz(v);
    V<T> ret(n + 1, inf<T>);
    for(ii i = n - 1; i >= 0; i--) ret[i] = min(ret[i + 1], v[i]);
    return ret;
}

vi mkiota(ii n) {
    vi ret(n);
    iota(ret.begin(), ret.end(), 0);
    return ret;
}

template <typename T>
T mkrev(T A) {
    reverse(A.begin(), A.end());
    return A;
}

template <typename T>
void dorev(T& A) {
    reverse(A.begin(), A.end());
}

vi mkinv(const vector<ii>& A, ii mx = -1) {
    ii n = siz(A);
    if(mx == -1) mx = maxv(A) + 1;
    vi ret(mx);
    for(ii i = 0; i < n; i++) ret[A[i]] = i;
    return ret;
}

template <typename T>
vvi mkinvvec(const vi& A, ii mx = -1) {
    ii n = siz(A);
    if(mx == -1) mx = maxv(A) + 1;
    vvi ret(mx);
    for(ii i = 0; i < n; i++) ret[A[i]].push_back(i);
    return ret;
}

vi mkfreq(const vi& A, ii mx = -1) {
    ii n = siz(A);
    if(mx == -1) mx = maxv(A) + 1;
    vi ret(mx);
    for(ii i = 0; i < n; i++) ret[A[i]]++;
    return ret;
}

template <typename T>
vi mkarg(const vector<T>& A) {
    vi ret = mkiota(siz(A));
    sort(ret.begin(), ret.end(), [&](ii i, ii j) {
        return (A[i] == A[j] ? i < j : A[i] < A[j]);
    });
    return ret;
}

template <typename T>
constexpr ii digit_siz(T n) {
    ii ret = 0;
    while(n) {
        ret++;
        n /= 10;
    }
    return ret;
}

template <typename T>
constexpr vi digits(T n) {
    vi ret;
    while(n) {
        ret.push_back(n % 10);
        n /= 10;
    }
    reverse(ret.begin(), ret.end());
    return ret;
}

template <typename T = i64>
constexpr T intpow(T x, T r) {
    T ret = 1;
    while(r) {
        if(r & 1) ret *= x;
        x *= x;
        r >>= 1;
    }
    return ret;
}

constexpr i64 tenpow(ii r) {
    i64 ret = 1;
    while(r--) ret *= 10;
    return ret;
}

template <typename T>
constexpr T intsqrt(T x) {
    i64 sq = (T)sqrtl(ld(x));
    while(sq * sq > x) sq--;
    while((sq + 1) * (sq + 1) <= x) sq++;
    return sq;
}

template <typename T = i128>
constexpr T euc_dist(auto ax, auto ay, auto bx, auto by) {
    return T(ax - bx) * (ax - bx) + T(ay - by) * (ay - by);
}

template <typename T = i64>
constexpr T man_dist(auto ax, auto ay, auto bx, auto by) {
    return abs(T(ax) - bx) + abs(T(ay) - by);
}

constexpr ii lotoi(char c) {
    assert('a' <= c && c <= 'z');
    return c - 'a';
}

constexpr char itolo(ii i) {
    assert(0 <= i && i <= 25);
    return char('a' + i);
}

constexpr ii hitoi(char c) {
    assert('A' <= c && c <= 'Z');
    return c - 'A';
}

constexpr char itohi(ii i) {
    assert(0 <= i && i <= 25);
    return char('A' + i);
}

constexpr ii ctoi(char c) {
    assert('0' <= c && c <= '9');
    return c - '0';
}

constexpr char itoc(ii i) {
    assert(0 <= i && i <= 9);
    return char('0' + i);
}

vi stov(const str& s, char base = 'a') {
    vi ret(s.size());
    rep(i, s.size()) ret[i] = s[i] - base;
    return ret;
}

str vtos(const vi& a, char base = 'a') {
    str ret;
    rep(i, a.size()) ret.push_back(char(base + a[i]));
    return ret;
}

constexpr ii popcount(i32 n) { return __builtin_popcount(n); }
constexpr ii popcount(i64 n) { return __builtin_popcountll(n); }

constexpr ii parity(i32 n) { return __builtin_parity(n); }
constexpr ii parity(i64 n) { return __builtin_parityll(n); }

// 最上位ビットの位置
constexpr ii topbit(i32 n) { return n ? 31 - __builtin_clz(n) : -1; }
constexpr ii topbit(i64 n) { return n ? 63 - __builtin_clzll(n) : -1; }

// 2進表現の長さ
constexpr ii bitsiz(i32 n) { return n ? 32 - __builtin_clz(n) : 1; }
constexpr ii bitsiz(i64 n) { return n ? 64 - __builtin_clzll(n) : 1; }

// 最下位ビットの位置
constexpr ii bottombit(i32 n) { return n ? __builtin_ctz(n) : -1; }
constexpr ii bottombit(i64 n) { return n ? __builtin_ctzll(n) : -1; }

bool ispower2(i32 n) { return n && (n & -n) == n; }

constexpr i64 mkmask(ii n) { return (1LL << n) - 1; }

bool hasbit(i64 n, ii i) { return (n >> i & 1); }

vi mksubset(ii s) {
    vi ret;
    ii t = s;
    do {
        ret.push_back(t);
        --t &= s;
    } while(t != s);
    return ret;
}

// 2進数表記を返す
string tobinary(i64 n, ii len = 32, bool rev = false) {
    string ret;
    for(ii i = 0; i < len; i++) ret += (hasbit(n, rev ? len - 1 - i : i) ? '1' : '0');
    return ret;
}

// Mint有理数の復元用
template <ii iter = 1000, typename Mint>
str tofraction(const Mint& a) {
    for(ii deno = 1; deno <= iter; deno++) {
        Mint inv = ((Mint)deno).inv();
        for(ii nume = 0; nume <= iter; nume++) {
            Mint val = inv * nume;
            if(val == a) {
                if(deno == 1) return to_string(nume);
                return to_string(nume) + "/" + to_string(deno);
            } else if(-val == a) {
                if(deno == 1) return to_string(-nume);
                return to_string(-nume) + "/" + to_string(deno);
            }
        }
    }
    return "NF";
}
//------>8--------- end kyopro_library/base/util.hpp --------->8------

void run();
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(15);
    cerr << fixed << setprecision(7);
#ifdef MULTI
    II(T);
    rep(t, T) {
#ifdef TDY
        // esay("============ Case: #", t + 1, " ============");
#endif
        run();
    }
#else
    run();
#endif
}

#ifdef DEBUG
#include "./debug.hpp"
#else
#define debug(...)
#define print_line
#endif
//------>8--------- end kyopro_library/template.hpp ---------->8------

// #include <kyopro_library/utils.hpp>

#define TODAY_KYOPRO
#include __FILE__

#endif
// b.cpp
// 2026-10-07 03:32:18
yukicoder

結果

ソースコード
