提出 #71511516

---

ソースコード 拡げる

#include <bits/stdc++.h>
using namespace std;

// #include <boost/multiprecision/cpp_int.hpp>
// using namespace boost::multiprecision;



// #pragma GCC optimize("O3")
// #pragma GCC target("avx2")
// #pragma GCC optimize("unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

using ll = long long;
using ull = unsigned long long;
using ld = long double;
using sb = set<bool>;
using si = set<int>;
using sl = set<ll>;
using sd = set<double>;
using sc = set<char>;
using ss = set<string>;
using msb = multiset<bool>;
using msi = multiset<int>;
using msl = multiset<ll>;
using msd = multiset<double>;
using msc = multiset<char>;
using mss = multiset<string>;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
using vb = vector<bool>;
using vi = vector<int>;
using vl = vector<ll>;
using vd = vector<double>;
using vc = vector<char>;
using vs = vector<string>;
using vsb = vector<sb>;
using vsi = vector<si>;
using vsl = vector<sl>;
using vsd = vector<sd>;
using vsc = vector<sc>;
using vss = vector<ss>;
using vmsb = vector<msb>;
using vmsi = vector<msi>;
using vmsl = vector<msl>;
using vmsd = vector<msd>;
using vmsc = vector<msc>;
using vmss = vector<mss>;
using vpii = vector<pii>;
using vpil = vector<pil>;
using vpli = vector<pli>;
using vpll = vector<pll>;
using vvb = vector<vb>;
using vvi = vector<vi>;
using vvl = vector<vl>;
using vvd = vector<vd>;
using vvc = vector<vc>;
using vvs = vector<vs>;
using vvsb = vector<vsb>;
using vvsi = vector<vsi>;
using vvsl = vector<vsl>;
using vvsd = vector<vsd>;
using vvsc = vector<vsc>;
using vvss = vector<vss>;
using vvmsb = vector<vmsb>;
using vvmsi = vector<vmsi>;
using vvmsl = vector<vmsl>;
using vvmsd = vector<vmsd>;
using vvmsc = vector<vmsc>;
using vvmss = vector<vmss>;
using vvpii = vector<vpii>;
using vvpil = vector<vpil>;
using vvpli = vector<vpli>;
using vvpll = vector<vpll>;
using vvvb = vector<vvb>;
using vvvi = vector<vvi>;
using vvvl = vector<vvl>;
using vvvd = vector<vvd>;
using vvvc = vector<vvc>;
using vvvs = vector<vvs>;
template <typename T>
using v = vector<T>;
template <typename T>
using vv = vector<v<T>>;
template <typename T>
using vvv = vector<vv<T>>;
template <typename T>
using vvvv = vector<vvv<T>>;

using line = tuple<ll, ll, ll>;


#define ca const auto&
#define en "\n"
// #define en endl
#define yes cout << "Yes" << en;
#define no cout << "No" << en;
#define Yes     \
    {           \
        yes;    \
        return; \
    }
#define No      \
    {           \
        no;     \
        return; \
    }
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define repb(i, n) for (ll i = (ll)(n) - 1; i >= 0; i--)
#define repr(i, min, max) for (ll i = (ll)(min); i <= (ll)(max); i++)
#define reprb(i, min, max) for (ll i = (ll)(max); i >= (ll)(min); i--)
#define repc2(i0, i1, n) repr(i0, 0, n - 2) repr(i1, i0 + 1, n - 1)
#define repc3(i0, i1, i2, n) repr(i0, 0, n - 3) repr(i1, i0 + 1, n - 2) repr(i2, i1 + 1, n - 1)
#define repc4(i0, i1, i2, i3, n) \
    repr(i0, 0, n - 4) repr(i1, i0 + 1, n - 3) repr(i2, i1 + 1, n - 2) repr(i3, i2 + 1, n - 1)
#define repx(i0, i1, n0, n1) rep(i0, n0) rep(i1, n1)
#define reprx(i0, i1, n0_min, n0_max, n1_min, n1_max) repr(i0, n0_min, n0_max) repr(i1, n1_min, n1_max)
#define repx3(i0, i1, i2, n0, n1, n2) rep(i0, n0) rep(i1, n1) rep(i2, n2)
#define reprx3(i0, i1, i2, n0_min, n0_max, n1_min, n1_max, n2_min, n2_max) \
    repr(i0, n0_min, n0_max) repr(i1, n1_min, n1_max) repr(i2, n2_min, n2_max)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define bit(x) (1ll << (x))
#define fill_(x) setfill(' ') << setw(x)
#define fill0(x) setfill('0') << setw(x)
#define prec(x) fixed << setprecision(x)
#define fi first
#define se second
#define Out(x) out(x, string(#x))

constexpr short INF16 = 32767;
constexpr int INF32 = 2147483647;
constexpr ll INF64 = 9223372036854775807;
constexpr int MOD9 = 998244353;
constexpr int MOD10 = 1000000007;


template <typename T>
string type_name() {
#ifdef __clang__
    string s = __PRETTY_FUNCTION__;
    auto start = s.find("T = ") + 4;
    auto end = s.find(']', start);
    return s.substr(start, end - start);
#elif defined(__GNUC__)
    string s = __PRETTY_FUNCTION__;
    auto start = s.find("with T = ") + 9;
    auto end = s.find(';', start);
    return s.substr(start, end - start);
#else
    return "unknown";
#endif
}



template <class T>
concept NotContainer = !requires(T x) { std::begin(x); };



template <typename T = ll>
inline T in() {
    T x;
    cin >> x;
    return x;
}
template <typename T>
inline void in(T& x) {
    cin >> x;
}
template <typename... Ts>
inline void in(Ts&... xs) {
    (in(xs), ...);
}
template <typename T>
inline void in(vector<T>& v) {
    for (auto& e : v) in(e);
}
template <typename T, typename U>
inline void in(pair<T, U>& p) {
    in(p.fi, p.se);
}
template <typename... Ts>
inline void in(tuple<Ts...>& t) {
    auto read = [&]<size_t... Is>(index_sequence<Is...>) { ((cin >> get<Is>(t)), ...); };
    read(index_sequence_for<Ts...>{});
}
template <typename T>
inline void in(set<T>& st, ll n) {
    rep(_, n) st.insert(in<T>());
}
template <typename T>
inline void in(multiset<T>& st, ll n) {
    rep(_, n) st.insert(in<T>());
}
template <typename V>
using is_vector = conjunction<is_same<V, vector<typename V::value_type, typename V::allocator_type>>>;
template <typename... Vs>
using enable_if_all_vectors = enable_if_t<(is_vector<decay_t<Vs>>::value && ...), int>;
template <typename... Args>
using enable_if_two_or_more = enable_if_t<(sizeof...(Args) >= 1), int>;
template <typename T, typename... Args, enable_if_all_vectors<Args...> = 0, enable_if_two_or_more<Args...> = 0>
inline void in(vector<T>& v0, Args&... vecs) {
    const size_t n = v0.size();
    rep(i, n) {
        cin >> v0[i];
        ((cin >> vecs[i]), ...);
    }
}



inline void out() {
    cout << en;
}
template <typename T>
inline void out(const T& x, string name = "") {
    if (name == "") {
        cout << x << en;
    } else {
        cout << name << ": " << x << "   <" << type_name<T>() << ">" << en;
    }
}
template <typename... Ts>
inline void out(const Ts&... xs) {
    ((cout << xs << " "), ...);
    cout << en;
}
template <typename T>
inline void out(const vector<T>& v, string name = "") {
    if (name == "") {
        rep(i, v.size()) cout << v[i] << " ";
        cout << en;
    } else {
        cout << name << ": {";
        rep(i, v.size()) {
            if (i != 0) cout << " ";
            cout << v[i];
        }
        cout << "}   <std::vector<" << type_name<T>() << ">>" << en;
    }
}
template <typename T>
inline void out(const vector<vector<T>>& v, string name = "") {
    if (name == "") {
        rep(i, v.size()) {
            rep(j, v[i].size()) {
                if (j != 0) cout << " ";
                cout << v[i][j];
            }
            cout << en;
        }
    } else {
        cout << name << ": {";
        rep(i, v.size()) {
            if (i != 0) {
                cout << en;
                rep(_, name.size() + 3) cout << " ";
            }
            cout << "{";
            rep(j, v[i].size()) {
                if (j != 0) cout << " ";
                cout << v[i][j];
            }
            cout << "}";
        }
        cout << "}   <std::vector<std::vector<" << type_name<T>() << ">>>" << en;
    }
}
template <typename T>
inline void out(const vector<vector<vector<T>>>& v, string name = "") {
    if (name == "") {
        rep(i, v.size()) {
            if (i != 0) cout << en;
            rep(j, v[i].size()) {
                rep(k, v[i][j].size()) {
                    if (k != 0) cout << " ";
                    cout << v[i][j][k];
                }
                cout << en;
            }
        }
    } else {
        cout << name << ": {";
        rep(i, v.size()) {
            if (i != 0) {
                cout << en;
            }
            rep(j, v[i].size()) {
                if (j != 0) {
                    cout << en << " ";
                }
                if (i != 0 || j != 0) {
                    rep(_, name.size() + 3) cout << " ";
                }
                if (j == 0) {
                    cout << "{";
                }


                cout << "{";
                rep(k, v[i][j].size()) {
                    if (k != 0) cout << " ";
                    cout << v[i][j][k];
                }
                cout << "}";
            }
            cout << "}" << en;
        }
        cout << "}   <std::vector<std::vector<std::vector<" << type_name<T>() << ">>>>" << en;
    }
}
template <typename T, typename U>
inline void out(const pair<T, U>& p, string name = "") {
    if (name == "") {
        cout << p.fi << " " << p.se << en;
    } else {
        cout << name << ": {";
        cout << p.fi << " " << p.se;
        cout << "}   <std::pair<" << type_name<T>() << ", " << type_name<U>() << ">>" << en;
    }
}
template <typename T, typename U>
inline void out(const vector<pair<T, U>>& v, string name = "") {
    if (name == "") {
        rep(i, v.size()) cout << v[i].fi << " " << v[i].se << en;
    } else {
        cout << name << ": {";
        rep(i, v.size()) {
            if (i != 0) {
                cout << en;
                rep(_, name.size() + 3) cout << " ";
            }
            cout << "{" << v[i].fi << " " << v[i].se << "}";
        }
        cout << "}   <std::vector<std::pair<" << type_name<T>() << ", " << type_name<U>() << ">>>" << en;
    }
}
template <typename T>
inline void out_set_like(const T& s, string name = "") {
    if (name == "") {
        for (auto it = s.begin(); it != s.end(); ++it) {
            if (it != s.begin()) cout << " ";
            cout << *it;
        }
        cout << en;
    } else {
        cout << name << ": {";
        for (auto it = s.begin(); it != s.end(); ++it) {
            if (it != s.begin()) cout << " ";
            cout << *it;
        }
        cout << "}   <" << type_name<T>() << ">" << en;
    }
}
template <typename T>
inline void out(const set<T>& s, string name = "") {
    out_set_like(s, name);
}
template <typename T>
inline void out(const multiset<T>& s, string name = "") {
    out_set_like(s, name);
}
template <typename T>
inline void out_vector_set_like(const vector<T>& v, string name = "") {
    if (name == "") {
        rep(i, v.size()) {
            for (auto it = v[i].begin(); it != v[i].end(); ++it) {
                if (it != v[i].begin()) cout << " ";
                cout << *it;
            }
            cout << en;
        }
    } else {
        cout << name << ": {";
        rep(i, v.size()) {
            if (i != 0) {
                cout << en;
                rep(_, name.size() + 3) cout << " ";
            }
            cout << "{";
            for (auto it = v[i].begin(); it != v[i].end(); ++it) {
                if (it != v[i].begin()) cout << " ";
                cout << *it;
            }
            cout << "}";
        }
        cout << "}   <std::vector<" << type_name<T>() << ">>" << en;
    }
}
template <typename T>
inline void out(const vector<set<T>>& v, string name = "") {
    out_vector_set_like(v, name);
}
template <typename T>
inline void out(const vector<multiset<T>>& v, string name = "") {
    out_vector_set_like(v, name);
}
template <typename T, typename U>
inline void out(const map<T, U>& m, string name = "") {
    if (name == "") {
        for (auto it = m.begin(); it != m.end(); ++it) {
            cout << (*it).fi << " " << (*it).se << en;
        }
    } else {
        cout << name << ": {";
        for (auto it = m.begin(); it != m.end(); ++it) {
            if (it != m.begin()) {
                cout << en;
                rep(_, name.size() + 3) cout << " ";
            }
            cout << "{" << (*it).fi << " " << (*it).se << "}";
        }
        cout << "}   <std::map<" << type_name<T>() << ", " << type_name<U>() << ">>" << en;
    }
}
template <typename T, typename U>
inline void out(const vector<map<T, U>>& m, string name = "") {
    if (name == "") {
        rep(i, m.size()) {
            if (i != 0) cout << en;
            for (auto it = m[i].begin(); it != m[i].end(); ++it) {
                cout << (*it).fi << " " << (*it).se << en;
            }
        }
    } else {
        cout << name << ": {";
        rep(i, m.size()) {
            if (i != 0) {
                cout << en;
            }
            for (auto it = m[i].begin(); it != m[i].end(); ++it) {
                if (it != m[i].begin()) {
                    cout << en << " ";
                }
                if (i != 0 || it != m[i].begin()) {
                    rep(_, name.size() + 3) cout << " ";
                }
                if (it == m[i].begin()) {
                    cout << "{";
                }

                cout << "{" << (*it).fi << " " << (*it).se << "}";
            }
            cout << "}" << en;
        }
        cout << "}   <std::vector<std::map<" << type_name<T>() << ", " << type_name<U>() << ">>>" << en;
    }
}
template <typename T>
inline void out(queue<T> q, string name = "") {
    if (name == "") {
        for (;;) {
            cout << q.front();
            q.pop();
            if (!q.empty()) {
                cout << " ";
            } else {
                break;
            }
        }
        cout << en;
    } else {
        cout << name << ": {";
        for (;;) {
            cout << q.front();
            q.pop();
            if (!q.empty()) {
                cout << " ";
            } else {
                break;
            }
        }
        cout << "}   <std::queue<" << type_name<T>() << ">>" << en;
    }
}
template <typename T>
inline void out(priority_queue<T> pq, string name = "") {
    if (name == "") {
        for (;;) {
            cout << pq.front();
            pq.pop();
            if (!pq.empty()) {
                cout << " ";
            } else {
                break;
            }
        }
        cout << en;
    } else {
        cout << name << ": {";
        for (;;) {
            cout << pq.front();
            pq.pop();
            if (!pq.empty()) {
                cout << " ";
            } else {
                break;
            }
        }
        cout << "}   <std::priority_queue<" << type_name<T>() << ">>" << en;
    }
}
template <typename T>
inline void out(stack<T> s, string name = "") {
    if (name == "") {
        for (;;) {
            cout << s.top();
            s.pop();
            if (!s.empty()) {
                cout << " ";
            } else {
                break;
            }
        }
        cout << en;
    } else {
        cout << name << ": {";
        for (;;) {
            cout << s.top();
            s.pop();
            if (!s.empty()) {
                cout << " ";
            } else {
                break;
            }
        }
        cout << "}   <std::stack<" << type_name<T>() << ">>" << en;
    }
}
template <typename T>
inline void out(deque<T> d, string name = "") {
    if (name == "") {
        rep(i, d.size()) cout << d[i] << " ";
        cout << en;
    } else {
        cout << name << ": {";
        rep(i, d.size()) {
            if (i != 0) cout << " ";
            cout << d[i];
        }
        cout << "}   <std::deque<" << type_name<T>() << ">>" << en;
    }
}

inline void yn_out(bool b) {
    cout << (b ? "Yes" : "No") << en;
}
inline void yn_out(vb v) {
    for (ca b : v) cout << (b ? "Yes" : "No") << en;
}

// 小さいなら更新 trueを返す
template <typename T, typename U>
bool chmin(T& a, U b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
// 大きいなら更新 trueを返す
template <typename T, typename U>
bool chmax(T& a, U b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

// 範囲内かどうか返す min <= x <= max
template <typename T, typename U = ll, typename V = ll>
bool inrange(T x, U min, V max) {
    return min <= x && x <= max;
}
// 範囲内かどうか返す min <= p <= max
template <typename T, typename U = ll, typename V = ll>
bool inrange(const pair<T, T>& p, const pair<U, U>& min, const pair<V, V>& max) {
    return inrange(p.fi, min.fi, max.fi) && inrange(p.se, min.se, max.se);
}

template <typename T>
pair<T, T> p_move(const pair<T, T>& x, ll d) {
    const vl di = {1, 0, -1, 0, 1, 1, -1, -1};
    const vl dj = {0, 1, 0, -1, 1, -1, 1, -1};
    return {x.fi + di[d], x.se + dj[d]};
}
template <typename T, typename U>
auto man_dist(const pair<T, T>& x, const pair<U, U>& y) {
    return abs(x.fi - y.fi) + abs(x.se - y.se);
}
template <typename T, typename U>
auto euc_dist_sq(const pair<T, T>& x, const pair<U, U>& y) {
    return (x.fi - y.fi) * (x.fi - y.fi) + (x.se - y.se) * (x.se - y.se);
}

// 10進数の10^iの位を出力
ll digit(ll n, ll p) {
    ll d = 1;
    rep(i, p) d *= 10;
    return n / d % 10;
}

ll modinv(ll x, ll m) {
    auto euclid = [](auto self, ll a, ll b) -> pll {
        if (b == 0) {
            return make_pair(1, 0);
        } else {
            auto [_x, _y] = self(self, b, a % b);
            return make_pair(_y, -(a / b) * _y + _x);
        }
    };
    auto [i, p] = euclid(euclid, x, m);
    return i < 0 ? i + m : i;
}

// コラボレーション(nCr)を計算
// 逆元を求めるmodinvが必要
ll ncr(ll n, ll r, ll mod = 0) {
    if (n < 1 || n < r) return 0;
    ll ans = 1;
    if (mod == 0) {
        rep(i, min(r, n - r)) {
            ans = ans * (n - i) / (i + 1);
        }
    } else {
        rep(i, min(r, n - r)) {
            ans *= n - i;
            ans %= mod;
            ans *= modinv(i + 1, mod);
            ans %= mod;
        }
    }
    return ans;
}

ll powz(ll x, ll y, ll mod = 0) {
    vl v(63, x);
    rep(i, 62) {
        if (mod == 0 && y < bit(i + 1)) break;
        v[i + 1] = v[i] * v[i];
        if (mod != 0) v[i + 1] %= mod;
    }
    ll ans = 1;
    rep(i, 63) {
        if ((y >> i) & 1) {
            ans *= v[i];
            if (mod != 0) ans %= mod;
        }
    }
    return ans;
}

ll sqrtz(ll x) {
    if (x < 0) {
        cerr << "error: x < 0 in sqrtz(x)." << endl;
        cerr << "x: " << x << endl;
        exit(1);
    }

    ll l = 0, r = 3037000500;
    while (l + 1 != r) {
        ll m = (l + r) / 2;
        if (m * m <= x) {
            l = m;
        } else {
            r = m;
        }
    }
    return l;
}

ll log10z(ll x) {
    if (x <= 0) {
        cerr << "error: x <= 0 in log10z(x)." << endl;
        cerr << "x: " << x << endl;
        exit(1);
    }
    ll ans = 0;
    while (x >= 10) {
        x /= 10;
        ans++;
    }
    return ans;
}

template <typename T, typename U>
T mod(T x, U y) {
    if (y <= 0) {
        cerr << "error: y <= 0 in mod(x, y)." << endl;
        cerr << "x: " << x << "   y: " << y << endl;
        exit(1);
    }
    if (x >= 0) {
        return x % y;
    } else {
        return x % y + y;
    }
}

// 2点を通るax+by+c=0の[a,b,c]を出力
line line_from_points(pll p0, pll p1) {
    ll a = p1.se - p0.se;
    ll b = p0.fi - p1.fi;
    ll c = -(a * p0.fi + b * p0.se);
    if (a < 0 || (a == 0 && b < 0) || (a == 0 && b == 0 && c < 0)) {
        a = -a;
        b = -b;
        c = -c;
    }
    ll d = gcd(a, gcd(b, c));
    a /= d;
    b /= d;
    c /= d;
    return {a, b, c};
}
// ax+by+c=0がp(x,y)を通るか判定
bool cross(line l, pll p) {
    auto [a, b, c] = l;
    auto [x, y] = p;
    return a * x + b * y + c == 0;
}

// next_permutation()のcollaboration版
template <class It, typename T>
bool next_collaboration(It first, It last, T n) {
    auto i = last;
    do {
        --i;
        ++(*i);

        auto j = i;
        ++j;
        for (; j != last; ++j) {
            *j = *(j - 1) + 1;
        }
        if (*(last - 1) < n) {
            return true;
        }
    } while (i != first);
    return false;
}

// n個の要素をr通りから選ぶ方法の列挙 (r^n通り)
template <class It, typename T>
bool next_repetition_oriented(It first, It last, T r) {
    if (first == last) return false;
    auto i = last;
    do {
        --i;

        if (*i < r - 1) {
            ++(*i);

            auto j = i;
            ++j;
            for (; j != last; ++j) {
                *j = 0;
            }
            return true;
        }

    } while (i != first);

    return false;
}

// x以下の素数リストを作成
inline vector<ll> make_prime_list(ll x) {
    if (x <= 0) return {};
    vector<ll> list(1, 2);
    ll n = 3;
    for (;;) {
        bool flag = true;
        for (ca e : list) {
            if (e * e > n) break;
            if (n % e == 0) {
                flag = false;
                break;
            }
        }
        if (flag) {
            if (n > x) break;
            list.emplace_back(n);
        }
        n += 2;
    }
    return list;
}

// 素因数を(因数, 指数)で出力
// 1.6e6 num/s (1 <= num < 1e5)
template <typename T = vpll>
T prime_factorization_list(ll n) {
    if (n == 1) return {};
    if (n < 1) {
        cerr << "error: n < 1 in prime_factorization_list(n)." << endl;
        cerr << "n: " << n << endl;
        exit(1);
    }

    T ans;
    auto add = [&](ll p, ll c) {
        if constexpr (requires { ans.emplace_back(p, c); }) {
            ans.emplace_back(p, c);
        } else {
            // map / unordered_map 対応
            ans[p] = c;
        }
    };

    ll i = 2;
    while (n != 1) {
        if (i * i > n) break;
        if (n % i == 0) {
            ll cnt = 0;
            while (n % i == 0) {
                cnt++;
                n /= i;
            }
            add(i, cnt);
        }
        i++;
    }
    if (n != 1) add(n, 1);
    return ans;
}

template <typename T>
vector<vector<T>> rotate(const vector<vector<T>>& a, ll d) {
    ll n = a.size();
    if (n == 0) return a;
    ll m = a[0].size();
    vector<vector<T>> res;

    switch (mod(d, 4)) {
        case 0:
            return a;
        case 1:
            res = vector<vector<T>>(m, vector<T>(n));
            repx(i, j, n, m) {
                res[j][n - 1 - i] = a[i][j];
            }
            break;
        case 2:
            res = vector<vector<T>>(n, vector<T>(m));
            repx(i, j, n, m) {
                res[n - 1 - i][m - 1 - j] = a[i][j];
            }
            break;
        case 3:
            res = vector<vector<T>>(m, vector<T>(n));
            repx(i, j, n, m) {
                res[m - 1 - j][i] = a[i][j];
            }
            break;
    }
    return res;
}

vs rotate(const vs& a, ll d) {
    ll n = a.size();
    if (n == 0) return a;
    ll m = a[0].size();

    vs res;

    switch (mod(d, 4)) {
        case 0:
            return a;

        case 1:
            res = vs(m, string(n, ' '));
            repx(i, j, n, m) {
                res[j][n - 1 - i] = a[i][j];
            }
            break;

        case 2:
            res = vs(n, string(m, ' '));
            repx(i, j, n, m) {
                res[n - 1 - i][m - 1 - j] = a[i][j];
            }
            break;

        case 3:
            res = vs(m, string(n, ' '));
            repx(i, j, n, m) {
                res[m - 1 - j][i] = a[i][j];
            }
            break;
    }
    return res;
}

static mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll rand(ll l, ll r) {
    uniform_int_distribution<ll> dist(l, r);
    return dist(rng);
}




// UnionFind
// pathへのアクセスはroot()で更新されるため無効
// valueに値を格納可能 標準型はll
template <class C, class T>
concept Combiner = requires(C c, T a, T b) {
    { c(a, b) };  // c(a,b) が有効な式であること
};
template <typename T = ll, class Combine = plus<T>>
struct UnionFind {
   private:
    vector<ll> parent;
    vector<ll> sz;    // 各根のサイズ
    vector<T> val;    // 各根に対応した値
    Combine combine;  // 値の結合方法

   public:
    ll group_count;  // 連結成分数

    // --- コンストラクタ ---
    UnionFind(ll n, T init_value = T(), Combine c = Combine())
        : parent(n), sz(n, 1), val(n, init_value), combine(c), group_count(n) {
        iota(parent.begin(), parent.end(), 0);
    }

    // --- root ---
    ll root(ll x) {
        if (parent[x] == x) return x;
        return parent[x] = root(parent[x]);
    }

    // --- same ---
    bool same(ll x, ll y) {
        return root(x) == root(y);
    }

    // --- unite ---
    bool unite(ll x, ll y) {
        x = root(x);
        y = root(y);
        if (x == y) return false;

        // y → x に接続
        parent[y] = x;
        sz[x] += sz[y];
        // 結合関数がある場合のみ実行
        if constexpr (Combiner<Combine, T>) {
            val[x] = combine(val[x], val[y]);
        }

        group_count--;
        return true;
    }

    // --- size ---
    ll size(ll x) {
        return sz[root(x)];
    }

    // --- 値への参照（結合後取得）---
    T& element(ll x) {
        return val[root(x)];
    }
};

// 区間内の和を求める
template <typename T = ll>
struct BinaryIndexedTree {
   private:
    vector<T> a;

   public:
    BinaryIndexedTree(ll n) {
        init(n);
    }
    void init(ll n) {
        a.resize(n + 1);
    }
    // p番目の要素にxだけ加算
    void add(ll p, T x) {
        p++;
        rep(i, 63) {
            if ((p >> i) & 1) {
                a[p] += x;
                p += bit(i);
                if (p >= static_cast<ll>(a.size())) break;
            }
        }
    }
    // [l,r]の要素の和を取得
    T get(ll l, ll r) {
        r++;
        T ans = 0;
        rep(i, 63) {
            if ((r >> i) & 1) {
                ans += a[r];
                r -= bit(i);
            }
            if ((l >> i) & 1) {
                ans -= a[l];
                l -= bit(i);
            }
        }
        return ans;
    }
    // p番目の要素にxを代入
    void set(ll p, T x) {
        add(p, x - get(p, p));
    }
};

// 区間内の最大最小を求める
// 標準の型はll
template <typename T = ll>
struct MinMaxSegmentTree {
   private:
    ll n;
    vector<T> min_tree;
    vector<T> max_tree;

    void build(const vector<T>& v, ll i, ll l, ll r) {
        if (l == r) {
            min_tree[i] = v[l];
            max_tree[i] = v[l];
            return;
        }
        ll m = (l + r) / 2;
        build(v, i * 2, l, m);
        build(v, i * 2 + 1, m + 1, r);

        min_tree[i] = std::min(min_tree[i * 2], min_tree[i * 2 + 1]);
        max_tree[i] = std::max(max_tree[i * 2], max_tree[i * 2 + 1]);
    }

    T query_min(ll i, ll l, ll r, ll ql, ll qr) const {
        if (qr < l || r < ql) return numeric_limits<T>::max();
        if (ql <= l && r <= qr) return min_tree[i];
        ll m = (l + r) / 2;
        return std::min(query_min(i * 2, l, m, ql, qr), query_min(i * 2 + 1, m + 1, r, ql, qr));
    }

    T query_max(ll i, ll l, ll r, ll ql, ll qr) const {
        if (qr < l || r < ql) return numeric_limits<T>::min();
        if (ql <= l && r <= qr) return max_tree[i];
        ll m = (l + r) / 2;
        return std::max(query_max(i * 2, l, m, ql, qr), query_max(i * 2 + 1, m + 1, r, ql, qr));
    }

   public:
    MinMaxSegmentTree(const vector<T>& v) {
        init(v);
    }

    void init(const vector<T>& v) {
        n = v.size();
        ll size = 1;
        while (size < n) size <<= 1;
        size <<= 1;

        min_tree.assign(size, numeric_limits<T>::max());
        max_tree.assign(size, numeric_limits<T>::min());

        build(v, 1, 0, n - 1);
    }

    T min(ll l, ll r) const {
        return query_min(1, 0, n - 1, l, r);
    }
    T max(ll l, ll r) const {
        return query_max(1, 0, n - 1, l, r);
    }
};

void solve();
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    solve();
    cout.flush();
    return 0;
}

//   _   _   __         __                           __
//  | | / | / /        /_/  __                 __   / /
//  | |/  |/ / __ ___ __ __/ /_  ___        __/ /_ / /_    ___
//  | / / / / / ／__// //_  __/／__ \      /_  __//  _ \ ／__ \
//  |  /|  / / ／   / /  / /_ / ____/       / /_ / / / // ____/
//  |_/ |_/ /_/    /_/   \__/ \___／        \__//_/ /_/ \___／
//       _____
//      / __  \                             ____
//     / /_ノ /__ ___  ___    ___   __ ___ /___ \ ________
//    / ____／/ ／__/／ _ \ ／ _ \ / ／__/／ _  //  _   _ \
//   / /     / ／   / /_/ // /_/ // ／   / /_/ // / / / / /
//  /_/     /_/     \___／ \__  //_/     \____//_/ /_/ /_/
//       __            __ ___/ /                 __   __
//      / /           / //___／                 / /  / /
//     / /_    ___   / / ___   __  __  __      / /__/ / ___   __ ___  ___
//    /  _ \ ／ _ \ / /／ _ \ / / / / / /     / ___  /／__ \ / ／__/／__ \
//   / /_/ // ____// // / / // /_/ /_/ /     / /  / // ____// ／   / ____/
//  /_|__／ \___／/_/ \___／ \________/     /_/  /_/ \___／/_/     \___／
//
//////////////////////////////////////////////////////////////////////////////
// 2025/11/30




void dfs(vvl& path, vector<deque<ll>>& loop, deque<ll>& his, vb& seen, sl dict, ll now) {
    if (dict.count(now)) {
        while (his.front() == now) his.pop_front();
        his.push_back(now);
        // Out(his);

        loop.emplace_back(his);


        return;
    }
    if (seen[now]) return;
    seen[now] = 1;
    his.push_back(now);
    dict.insert(now);

    for (ca to : path[now]) {
        dfs(path, loop, his, seen, dict, to);
    }
}

void f(vvl& path, vl& root, vb& can_visit, ll now) {
    if (can_visit[root[now]]) return;
    can_visit[root[now]] = 1;

    for (ca to : path[now]) {
        f(path, root, can_visit, to);
    }
}

void solve() {
    ll n, m;
    in(n, m);
    vvl path(n);
    rep(i, m) {
        ll x, y;
        in(x, y);
        x--;
        y--;
        path[y].emplace_back(x);
    }



    vl root(n);
    iota(all(root), 0);
    vb seen(n);
    vector<deque<ll>> loop;
    rep(i, n) {
        sl dict;
        deque<ll> his;
        dfs(path, loop, his, seen, dict, i);
    }

    for (auto& his : loop) {
        ll now = his.front();
        his.pop_front();
        for (ca e : his) {
            for (ca p : path[e]) path[now].emplace_back(p);
            root[e] = now;
        }
    }

    // Out(root);
    // Out(path);


    ll q;
    in(q);
    vb can_visit(n);
    rep(_, q) {
        ll mode, v;
        in(mode, v);
        v--;

        if (mode == 1) {
            f(path, root, can_visit, v);
        } else {
            yn_out(can_visit[root[v]]);
        }
        // Out(can_visit);
    }
}

提出情報

コンパイルエラー

./Main.cpp:1094:1: warning: multi-line comment [-Wcomment]
 1094 | //  | / / / / / ／__// //_  __/／__ \      /_  __//  _ \ ／__ \
      | ^
./Main.cpp:1100:1: warning: multi-line comment [-Wcomment]
 1100 | //    / ____／/ ／__/／ _ \ ／ _ \ / ／__/／ _  //  _   _ \
      | ^
./Main.cpp:1106:1: warning: multi-line comment [-Wcomment]
 1106 | //    /  _ \ ／ _ \ / /／ _ \ / / / / / /     / ___  /／__ \ / ／__/／__ \
      | ^

ジャッジ結果