#847803 (C++17) No.2242 Cities and Teleporters

提出ソース
結果

問題	No.2242 Cities and Teleporters
コンテスト
ユーザー	first_vil
提出日時	2023-03-10 22:13:43
言語	C++17 (gcc 13.3.0 + boost 1.87.0)
結果	AC
実行時間	332 ms / 3,000 ms
コード長	45,545 bytes
コンパイル時間	2,662 ms
コンパイル使用メモリ	234,384 KB
最終ジャッジ日時	2025-02-11 08:29:21
ジャッジサーバーID （参考情報）	judge3 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン	結果
other	AC * 26
権限があれば一括ダウンロードができます
ソースコード

raw source code
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using namespace chrono;
template<class T> using V = vector<T>;
using VI = V<int>;
using VL = V<ll>;
using VS = V<string>;
template<class T> using PQ = priority_queue<T, V<T>, greater<T>>;
using G = V<VI>;
template<class T> using WG = V<V<pair<int, T>>>;
#define inside(h, w, y, x) (unsigned(y) < h && unsigned(x) < w)
constexpr ll INF = 1000000000;
constexpr ll LLINF = 1001001001001001001;
constexpr ll mod = 1000000007;
constexpr ll MOD = 998244353;
template<class T> inline istream &operator>>(istream &is, V<T> &v) {
    for (auto &a : v) is >> a;
    return is;
}
template<class T, class U>
inline istream &operator>>(istream &is, pair<T, U> &p) {
    is >> p.first >> p.second;
    return is;
}
template<class T> inline V<T> vec(size_t a) { return V<T>(a); }
template<class T> inline V<T> defvec(T def, size_t a) { return V<T>(a, def); }
template<class T, class... Ts> inline auto vec(size_t a, Ts... ts) {
    return V<decltype(vec<T>(ts...))>(a, vec<T>(ts...));
}
template<class T, class... Ts> inline auto defvec(T def, size_t a, Ts... ts) {
    return V<decltype(defvec<T>(def, ts...))>(a, defvec<T>(def, ts...));
}
template<class T> inline void print(const T &a) { cout << a << "\n"; }
template<class T, class... Ts> inline void print(const T &a, const Ts &...ts) {
    cout << a << " ";
    print(ts...);
}
template<class T> inline void print(const V<T> &v) {
    for (int i = 0; i < v.size(); ++i)
        cout << v[i] << (i == v.size() - 1 ? "\n" : " ");
}
template<class T> inline void print(const V<V<T>> &v) {
    for (auto &a : v) print(a);
}
template<class T> inline constexpr const T cum(const V<T> &a, int l, int r) {
    return 0 <= l && l <= r && r < a.size() ? a[r] - (l == 0 ? 0 : a[l - 1])
                                            : 0;
}  //[l,r]
template<class T> inline constexpr const auto min(const T &v) {
    return *min_element(all(v));
}
template<class T> inline constexpr const auto max(const T &v) {
    return *max_element(all(v));
}
template<class T> inline V<T> &operator++(V<T> &v) {
    for (T &a : v) ++a;
    return v;
}
template<class T> inline V<T> &operator--(V<T> &v) {
    for (T &a : v) --a;
    return v;
}

struct Fast {
    Fast() {
        cin.tie(0);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(numeric_limits<double>::max_digits10);
    }
} fast;

#define overload3(_1, _2, _3, name, ...) name
#define overload4(_1, _2, _3, _4, name, ...) name
#define overload5(_1, _2, _3, _4, _5, name, ...) name
#define rep1(n) for (ll _ = 0; _ < (n); ++_)
#define rep2(i, n) for (ll i = 0; i < (n); ++i)
#define rep3(i, a, b) for (ll i = (a); i < (b); ++i)
#define rep4(i, a, b, c) for (ll i = (a); i < (b); i += (c))
#define rep(...) overload4(__VA_ARGS__, rep4, rep3, rep2, rep1)(__VA_ARGS__)
#define rrep1(n) for (ll i = n - 1; i >= 0; --i)
#define rrep2(i, n) for (ll i = n - 1; i >= 0; --i)
#define rrep3(i, a, b) for (ll i = b - 1; i >= a; --i)
#define rrep(...) overload3(__VA_ARGS__, rrep3, rrep2, rrep1)(__VA_ARGS__)
#define each2(e, v) for (auto &&e : v)
#define each3(a, b, v) for (auto &&[a, b] : v)
#define each4(a, b, c, v) for (auto &&[a, b, c] : v)
#define each5(a, b, c, d, v) for (auto &&[a, b, c, d] : v)
#define each(...) \
    overload5(__VA_ARGS__, each5, each4, each3, each2, _)(__VA_ARGS__)
#define ALL1(v) (v).begin(), (v).end()
#define ALL2(v, E) (v).begin(), (v).begin() + ((E) + 1)
#define ALL3(v, S, E) (v).begin() + (S), (v).begin() + ((E) + 1)
#define ALL(...) overload3(__VA_ARGS__, ALL3, ALL2, ALL1)(__VA_ARGS__)
#define all ALL
#define RALL1(v) (v).rbegin(), (v).rend()
#define RALL2(v, E) (v).rbegin(), (v).rbegin() + ((E) + 1)
#define RALL3(v, S, E) (v).rbegin() + (S), (v).rbegin() + ((E) + 1)
#define RALL(...) overload3(__VA_ARGS__, RALL3, RALL2, RALL1)(__VA_ARGS__)
#define rall RALL
template<class T> inline bool chmax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmin(T &a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline T MaxE(vector<T> &v, ll S, ll E) {
    T m = v[S];
    rep(i, S, E) chmax(m, v[i]);
    return m;
}
template<class T> inline T MinE(vector<T> &v, ll S, ll E) {
    T m = v[S];
    rep(i, S, E) chmin(m, v[i]);
    return m;
}
template<class T> inline T MaxE(vector<T> &v) {
    return MaxE(v, 0, (ll)v.size() - 1);
}
template<class T> inline T MinE(vector<T> &v) {
    return MinE(v, 0, (ll)v.size() - 1);
}
template<class T> inline auto maxe(T &&v, ll S, ll E) {
    return *max_element(ALL(v, S, E));
}
template<class T> inline auto maxe(T &&v) { return *max_element(ALL(v)); }
template<class T> inline auto mine(T &&v, ll S, ll E) {
    return *min_element(ALL(v, S, E));
}
template<class T> inline auto mine(T &&v) { return *min_element(ALL(v)); }
template<class T> inline T Sum(vector<T> &v, ll S, ll E) {
    T s = T();
    rep(i, S, E) s += v[i];
    return s;
}
template<class T> inline T Sum(vector<T> &v) { return Sum(v, 0, v.size() - 1); }
template<class T, class U = typename remove_reference<T>::type::value_type>
inline U sum(T &&v, ll S, ll E) {
    return accumulate(all(v, S, E), U());
}
template<class T> inline auto sum(T &&v) {
    return sum(v, 0, v.end() - v.begin() - 1);
}
template<class T> inline ll sz(T &&v) { return (ll)v.size(); }
inline ll CEIL(ll a, ll b) {
    return (a < 0) ? -(-a / b) : (a + b - 1) / b;
}  // 負もOK
inline ll FLOOR(ll a, ll b) { return -CEIL(-a, b); }  // 負もOK

// pair用テンプレート
template<class T, class S>
inline pair<T, S> &operator+=(pair<T, S> &a, const pair<T, S> &b) {
    a.first += b.first;
    a.second += b.second;
    return a;
}
template<class T, class S>
inline pair<T, S> &operator-=(pair<T, S> &a, const pair<T, S> &b) {
    a.first -= b.first;
    a.second -= b.second;
    return a;
}
template<class T, class S>
inline pair<T, S> &operator*=(pair<T, S> &a, const pair<T, S> &b) {
    a.first *= b.first;
    a.second *= b.second;
    return a;
}
template<class T, class S>
inline pair<T, S> &operator/=(pair<T, S> &a, const pair<T, S> &b) {
    a.first /= b.first;
    a.second /= b.second;
    return a;
}
template<class T, class S>
inline pair<T, S> &operator%=(pair<T, S> &a, const pair<T, S> &b) {
    a.first %= b.first;
    a.second %= b.second;
    return a;
}
template<class T, class S, class R>
inline pair<T, S> &operator+=(pair<T, S> &a, R b) {
    a.first += b;
    a.second += b;
    return a;
}
template<class T, class S, class R>
inline pair<T, S> &operator-=(pair<T, S> &a, R b) {
    a.first -= b;
    a.second -= b;
    return a;
}
template<class T, class S, class R>
inline pair<T, S> &operator*=(pair<T, S> &a, R b) {
    a.first *= b;
    a.second *= b;
    return a;
}
template<class T, class S, class R>
inline pair<T, S> &operator/=(pair<T, S> &a, R b) {
    a.first /= b;
    a.second /= b;
    return a;
}
template<class T, class S, class R>
inline pair<T, S> &operator%=(pair<T, S> &a, R b) {
    a.first %= b;
    a.second %= b;
    return a;
}
template<class T, class S, class R>
inline pair<T, S> operator+(const pair<T, S> &a, R b) {
    pair<T, S> c = a;
    return c += b;
}
template<class T, class S, class R>
inline pair<T, S> operator-(const pair<T, S> &a, R b) {
    pair<T, S> c = a;
    return c -= b;
}
template<class T, class S, class R>
inline pair<T, S> operator*(const pair<T, S> &a, R b) {
    pair<T, S> c = a;
    return c *= b;
}
template<class T, class S, class R>
inline pair<T, S> operator/(const pair<T, S> &a, R b) {
    pair<T, S> c = a;
    return c /= b;
}
template<class T, class S, class R>
inline pair<T, S> operator%(const pair<T, S> &a, R b) {
    pair<T, S> c = a;
    return c %= b;
}
template<class T, class S, class R>
inline pair<T, S> operator-(R b, const pair<T, S> &a) {
    pair<T, S> c = -a;
    return c += b;
}
template<class T, class S>
inline pair<T, S> operator-(const pair<T, S> &a, const pair<T, S> &b) {
    pair<T, S> c = a;
    return c -= b;
}
template<class T, class S> inline pair<T, S> operator-(const pair<T, S> &a) {
    pair<T, S> c = a;
    return c *= (-1);
}
template<class T, class S>
inline ostream &operator<<(ostream &os, const pair<T, S> &a) {
    return os << a.first << ' ' << a.second;
}

// tuple用テンプレート 出力用のみ
template<class T, class S, class R>
inline ostream &operator<<(ostream &os, const tuple<T, S, R> &a) {
    return os << get<0>(a) << ' ' << get<1>(a) << ' ' << get<2>(a);
}
template<class T, class S, class R, class Q>
inline ostream &operator<<(ostream &os, const tuple<T, S, R, Q> &a) {
    return os << get<0>(a) << ' ' << get<1>(a) << ' ' << get<2>(a) << ' '
              << get<3>(a);
}

// vector用テンプレート
template<class T>
inline vector<T> &operator+=(vector<T> &a, const vector<T> &b) {
    for (ll i = 0; i < (ll)a.size(); i++) a[i] += b[i];
    return a;
}
template<class T>
inline vector<T> &operator-=(vector<T> &a, const vector<T> &b) {
    for (ll i = 0; i < (ll)a.size(); i++) a[i] -= b[i];
    return a;
}
template<class T>
inline vector<T> &operator*=(vector<T> &a, const vector<T> &b) {
    for (ll i = 0; i < (ll)a.size(); i++) a[i] *= b[i];
    return a;
}
template<class T>
inline vector<T> &operator/=(vector<T> &a, const vector<T> &b) {
    for (ll i = 0; i < (ll)a.size(); i++) a[i] /= b[i];
    return a;
}
template<class T>
inline vector<T> &operator%=(vector<T> &a, const vector<T> &b) {
    for (ll i = 0; i < (ll)a.size(); i++) a[i] %= b[i];
    return a;
}
template<class T, class S> inline vector<T> &operator+=(vector<T> &a, S b) {
    for (T &e : a) e += b;
    return a;
}
template<class T, class S> inline vector<T> &operator-=(vector<T> &a, S b) {
    for (T &e : a) e -= b;
    return a;
}
template<class T, class S> inline vector<T> &operator*=(vector<T> &a, S b) {
    for (T &e : a) e *= b;
    return a;
}
template<class T, class S> inline vector<T> &operator/=(vector<T> &a, S b) {
    for (T &e : a) e /= b;
    return a;
}
template<class T, class S> inline vector<T> &operator%=(vector<T> &a, S b) {
    for (T &e : a) e %= b;
    return a;
}
template<class T, class S> inline vector<T> operator+(const vector<T> &a, S b) {
    vector<T> c = a;
    return c += b;
}
template<class T, class S> inline vector<T> operator-(const vector<T> &a, S b) {
    vector<T> c = a;
    return c -= b;
}
template<class T, class S> inline vector<T> operator*(const vector<T> &a, S b) {
    vector<T> c = a;
    return c *= b;
}
template<class T, class S> inline vector<T> operator/(const vector<T> &a, S b) {
    vector<T> c = a;
    return c /= b;
}
template<class T, class S> inline vector<T> operator%(const vector<T> &a, S b) {
    vector<T> c = a;
    return c %= b;
}
template<class T, class S> inline vector<T> operator-(S b, const vector<T> &a) {
    vector<T> c = -a;
    return c += b;
}
template<class T>
inline vector<T> operator-(const vector<T> &a, const vector<T> &b) {
    vector<T> c = a;
    return c -= b;
}
template<class T> inline vector<T> operator-(const vector<T> &a) {
    vector<T> c = a;
    return c *= (-1);
}
template<class T> inline ostream &operator<<(ostream &os, const vector<T> &a) {
    for (ll i = 0; i < (ll)a.size(); i++) os << (i > 0 ? " " : "") << a[i];
    return os;
}

// array用テンプレート
template<class T, size_t S>
inline array<T, S> &operator+=(array<T, S> &a, const array<T, S> &b) {
    for (ll i = 0; i < (ll)S; i++) a[i] += b[i];
    return a;
}
template<class T, size_t S>
inline array<T, S> &operator-=(array<T, S> &a, const array<T, S> &b) {
    for (ll i = 0; i < (ll)S; i++) a[i] -= b[i];
    return a;
}
template<class T, size_t S>
inline array<T, S> &operator*=(array<T, S> &a, const array<T, S> &b) {
    for (ll i = 0; i < (ll)S; i++) a[i] *= b[i];
    return a;
}
template<class T, size_t S>
inline array<T, S> &operator/=(array<T, S> &a, const array<T, S> &b) {
    for (ll i = 0; i < (ll)S; i++) a[i] /= b[i];
    return a;
}
template<class T, size_t S>
inline array<T, S> &operator%=(array<T, S> &a, const array<T, S> &b) {
    for (ll i = 0; i < (ll)S; i++) a[i] %= b[i];
    return a;
}
template<class T, size_t S, class R>
inline array<T, S> &operator+=(array<T, S> &a, R b) {
    for (T &e : a) e += b;
    return a;
}
template<class T, size_t S, class R>
inline array<T, S> &operator-=(array<T, S> &a, R b) {
    for (T &e : a) e -= b;
    return a;
}
template<class T, size_t S, class R>
inline array<T, S> &operator*=(array<T, S> &a, R b) {
    for (T &e : a) e *= b;
    return a;
}
template<class T, size_t S, class R>
inline array<T, S> &operator/=(array<T, S> &a, R b) {
    for (T &e : a) e /= b;
    return a;
}
template<class T, size_t S, class R>
inline array<T, S> &operator%=(array<T, S> &a, R b) {
    for (T &e : a) e %= b;
    return a;
}
template<class T, size_t S, class R>
inline array<T, S> operator+(const array<T, S> &a, R b) {
    array<T, S> c = a;
    return c += b;
}
template<class T, size_t S, class R>
inline array<T, S> operator-(const array<T, S> &a, R b) {
    array<T, S> c = a;
    return c -= b;
}
template<class T, size_t S, class R>
inline array<T, S> operator*(const array<T, S> &a, R b) {
    array<T, S> c = a;
    return c *= b;
}
template<class T, size_t S, class R>
inline array<T, S> operator/(const array<T, S> &a, R b) {
    array<T, S> c = a;
    return c /= b;
}
template<class T, size_t S, class R>
inline array<T, S> operator%(const array<T, S> &a, R b) {
    array<T, S> c = a;
    return c %= b;
}
template<class T, size_t S, class R>
inline array<T, S> operator-(R b, const array<T, S> &a) {
    array<T, S> c = -a;
    return c += b;
}
template<class T, size_t S>
inline array<T, S> operator-(const array<T, S> &a, const array<T, S> &b) {
    array<T, S> c = a;
    return c -= b;
}
template<class T, size_t S> inline array<T, S> operator-(const array<T, S> &a) {
    array<T, S> c = a;
    return c *= (-1);
}
template<class T, size_t S>
inline ostream &operator<<(ostream &os, const array<T, S> &a) {
    for (ll i = 0; i < (ll)S; i++) os << (i > 0 ? " " : "") << a[i];
    return os;
}

template<class T, size_t S, class R> struct view1d;
template<class T, size_t S, class R> struct view1dIter {
    view1d<T, S, R> *vw = nullptr;
    ll idx = LLINF;
    view1dIter() {}
    view1dIter(view1d<T, S, R> *vw_, ll idx_) : vw(vw_), idx(idx_) {}
    view1dIter(const view1dIter<T, S, R> &it) : vw(it.vw), idx(it.idx) {}
    R &operator*() { return (*vw)[idx]; }
    R &operator*() const { return (*vw)[idx]; }
    R &operator[](ll i) { return (*vw)[idx + i]; }
    R &operator[](ll i) const { return (*vw)[idx + i]; }
    auto &operator++() {
        idx++;
        return *this;
    }
    auto &operator--() {
        idx--;
        return *this;
    }
    auto operator++(int) {
        auto it = *this;
        idx++;
        return it;
    }
    auto operator--(int) {
        auto it = *this;
        idx--;
        return it;
    }
    auto &operator+=(ll n) {
        idx += n;
        return *this;
    }
    auto &operator-=(ll n) {
        idx -= n;
        return *this;
    }
    auto operator+(ll n) {
        auto it = *this;
        return it += n;
    }
    auto operator-(ll n) {
        auto it = *this;
        return it -= n;
    }
    ll operator-(const view1dIter<T, S, R> &it) const { return idx - it.idx; }
    bool operator<(const view1dIter<T, S, R> &it) const { return idx < it.idx; }
    bool operator>(const view1dIter<T, S, R> &it) const { return idx > it.idx; }
    bool operator<=(const view1dIter<T, S, R> &it) const {
        return idx <= it.idx;
    }
    bool operator>=(const view1dIter<T, S, R> &it) const {
        return idx >= it.idx;
    }
    bool operator!=(const view1dIter<T, S, R> &it) const {
        return idx != it.idx;
    }
    bool operator==(const view1dIter<T, S, R> &it) const {
        return idx == it.idx;
    }
    using iterator_category = random_access_iterator_tag;
    using value_type = R;
    using difference_type = ll;
    using pointer = R *;
    using reference = R &;
};
template<class T, size_t S, class R> struct view1d {
    using Sll = array<ll, S>;
    T &data;         // 参照先データ
    Sll dsize;       // 参照先データ各軸のサイズ
    Sll s = Sll();   // view先頭
    Sll d = Sll();   // view方向
    ll len;          // view長さ
    R &dummy;        // 範囲外の値参照
    R dummyj = R();  // 範囲外の値実体
    /*---- コンストラクタ ----*/
    view1d(T &v) : data(v), dummy(dummyj) {
        SetDsize(v, dsize);
        d[S - 1] = 1;
        len = dsize[S - 1];
    }
    // このコンストラクタは、マイナス座標指定を末尾にしない(暫定)
    // 代入時Array<ll,2>{...}等と書くため、使い勝手悪い。将来廃止するかも。
    view1d(T &v, Sll s, Sll e, Sll d)
        : data(v), s(s), d(d), len(Len(s, e, d)), dummy(dummyj) {
        SetDsize(v, dsize);
    }
    view1d(T &v, Sll s, Sll d, ll len, R &dmy_)
        : data(v), s(s), d(d), len(len), dummy(dmy_) {
        SetDsize(v, dsize);
    }

    /*---- 演算 ----*/
    template<class Q> auto &operator=(const Q &b) {
        rep(i, len)(*this)[i] = b;
        return *this;
    }
    template<class Q> auto &operator+=(const Q &b) {
        rep(i, len)(*this)[i] += b;
        return *this;
    }
    template<class Q> auto &operator-=(const Q &b) {
        rep(i, len)(*this)[i] -= b;
        return *this;
    }
    template<class Q> auto &operator*=(const Q &b) {
        rep(i, len)(*this)[i] *= b;
        return *this;
    }
    template<class Q> auto &operator/=(const Q &b) {
        rep(i, len)(*this)[i] /= b;
        return *this;
    }
    template<class Q> auto &operator%=(const Q &b) {
        rep(i, len)(*this)[i] %= b;
        return *this;
    }
    auto &operator=(const string &b) { return CpSeq(b); }
    template<size_t Q> auto &operator=(const char (&b)[Q]) {
        return *this = string(b);
    }
    template<class Q> auto &operator=(const vector<Q> &b) { return CpSeq(b); }
    template<class Q> auto &operator+=(const vector<Q> &b) { return PlSeq(b); }
    template<class Q> auto &operator-=(const vector<Q> &b) { return MnSeq(b); }
    template<class Q> auto &operator*=(const vector<Q> &b) { return PrSeq(b); }
    template<class Q> auto &operator/=(const vector<Q> &b) { return DvSeq(b); }
    template<class Q> auto &operator%=(const vector<Q> &b) { return RmSeq(b); }
    template<class Q, size_t P, class O>
    auto &operator=(const view1d<Q, P, O> &b) {
        return CpSeq(b);
    }
    template<class Q, size_t P, class O>
    auto &operator+=(const view1d<Q, P, O> &b) {
        return PlSeq(b);
    }
    template<class Q, size_t P, class O>
    auto &operator-=(const view1d<Q, P, O> &b) {
        return MnSeq(b);
    }
    template<class Q, size_t P, class O>
    auto &operator*=(const view1d<Q, P, O> &b) {
        return PrSeq(b);
    }
    template<class Q, size_t P, class O>
    auto &operator/=(const view1d<Q, P, O> &b) {
        return DvSeq(b);
    }
    template<class Q, size_t P, class O>
    auto &operator%=(const view1d<Q, P, O> &b) {
        return RmSeq(b);
    }
    template<class Q> auto &CpSeq(const Q &b) {
        rep(i, min(sz(b), len))(*this)[i] = b[i];
        return *this;
    }
    template<class Q> auto &PlSeq(const Q &b) {
        rep(i, min(sz(b), len))(*this)[i] += b[i];
        return *this;
    }
    template<class Q> auto &MnSeq(const Q &b) {
        rep(i, min(sz(b), len))(*this)[i] -= b[i];
        return *this;
    }
    template<class Q> auto &PrSeq(const Q &b) {
        rep(i, min(sz(b), len))(*this)[i] *= b[i];
        return *this;
    }
    template<class Q> auto &DvSeq(const Q &b) {
        rep(i, min(sz(b), len))(*this)[i] /= b[i];
        return *this;
    }
    template<class Q> auto &RmSeq(const Q &b) {
        rep(i, min(sz(b), len))(*this)[i] %= b[i];
        return *this;
    }
    // template<class Q,class P> static bool eq(const Q &a,const P &b){
    //	return equals(ALL(a),ALL(b));
    // }
    template<class Q, class P> static bool eq(const Q &a, const P &b) {
        if ((ll)a.size() != (ll)b.size()) return false;
        rep(i, (ll)a.size()) {
            if (a[i] != b[i]) return false;
        }
        return true;
    }
    template<class Q, class P> static bool lt(const Q &a, const P &b) {
        ll n = min((ll)a.size(), (ll)b.size());
        rep(i, n) {
            if (a[i] < b[i]) return true;
            if (a[i] > b[i]) return false;
        }
        return (ll)a.size() < (ll)b.size();
    }
    template<class Q, size_t P, class O>
    bool operator==(const view1d<Q, P, O> &b) {
        return eq(*this, b);
    }
    template<class Q> bool operator==(const Q &b) { return eq(*this, b); }
    template<class Q>
    friend bool operator==(const Q &a, const view1d<T, S, R> &b) {
        return eq(a, b);
    }
    template<size_t Q> bool operator==(const char (&b)[Q]) {
        return eq(*this, string(b));
    }
    template<class Q, size_t P, class O>
    bool operator!=(const view1d<Q, P, O> &b) {
        return !(*this == b);
    }
    template<class Q> bool operator!=(const Q &b) { return !(*this == b); }
    template<class Q>
    friend bool operator!=(const Q &a, const view1d<T, S, R> &b) {
        return !(a == b);
    }
    template<class Q, size_t P, class O>
    bool operator<(const view1d<Q, P, O> &b) {
        return lt(*this, b);
    }
    template<class Q> bool operator<(const Q &b) { return lt(*this, b); }
    template<class Q>
    friend bool operator<(const Q &a, const view1d<T, S, R> &b) {
        return lt(a, b);
    }
    template<class Q, size_t P, class O>
    bool operator>(const view1d<Q, P, O> &b) {
        return lt(b, *this);
    }
    template<class Q> bool operator>(const Q &b) { return lt(b, *this); }
    template<class Q>
    friend bool operator>(const Q &a, const view1d<T, S, R> &b) {
        return lt(b, a);
    }
    template<class Q, size_t P, class O>
    bool operator<=(const view1d<Q, P, O> &b) {
        return !(*this > b);
    }
    template<class Q> bool operator<=(const Q &b) { return !(*this > b); }
    template<class Q>
    friend bool operator<=(const Q &a, const view1d<T, S, R> &b) {
        return !(a > b);
    }
    template<class Q, size_t P, class O>
    bool operator>=(const view1d<Q, P, O> &b) {
        return !(*this < b);
    }
    template<class Q> bool operator>=(const Q &b) { return !(*this < b); }
    template<class Q>
    friend bool operator>=(const Q &a, const view1d<T, S, R> &b) {
        return !(a < b);
    }

    /*---- getter ----*/
    ll size() const { return len; }
    R &operator[](ll i) { return const_cast<R &>(OrgAt(s + d * i)); }
    const R &operator[](ll i) const { return OrgAt(s + d * i); }
    R &at(ll i) {
        if (i < 0) i += len;
        return (*this)[i];
    }
    // vector<R> tov(){ vector<R> vvv(len);  rep(i,0,len) vvv[i]=(*this)[i];
    // return vvv; }
    operator vector<R>() {
        vector<R> v(len);
        rep(i, len - 1) v[i] = (*this)[i];
        return v;
    }
    bool contains(R a) {
        rep(i, len) if ((*this)[i] == a) return true;
        return false;
    }
    auto begin() { return view1dIter<T, S, R>(this, 0); }
    auto end() { return view1dIter<T, S, R>(this, len); }
    /*---- view設定 ----*/
    view1d<T, S, R> &dmy(R dmy_) {
        dummy = dmy_;
        return *this;
    }  // ダミー値セット
    template<class... Q>
    view1d<T, S, R> &st(Q... s_) {  // 始点set 負は末尾からの位置
        this->s = RevIfNeg(SllD(s_...));
        this->len = AutoLen(this->s, this->d, this->dsize);
        return *this;
    }
    template<class... Q>
    view1d<T, S, R> &en(Q... e_) {  // 終了条件再設定 負は末尾から
        this->len = Len(s, RevIfNeg(SllD(e_...)), d);
        return *this;
    }
    template<class... Q>
    view1d<T, S, R> &dir(Q... d_) {  // 方向set、長さはdata端まで
        this->d = SllD(d_...);
        this->len = AutoLen(this->s, this->d, this->dsize);
        return *this;
    }
    template<class... Q> view1d<T, S, R> &mv(Q... s_) {
        this->s += SllD(s_...);
        return *this;
    }  // 平行移動
    view1d<T, S, R> &size(ll len_) {
        len = len_;
        return *this;
    }  // 長さset
    template<class Q> view1d<T, S, R> &size(Q &v) {
        len = (ll)v.size();
        return *this;
    }  // 長さset
    view1d<T, S, R> &rev() {
        s += d * (len - 1);
        d *= -1;
        return *this;
    }  // 反転

    /*---- utility ----*/
    template<class Q> inline static ll sz(Q &v) { return (ll)v.size(); }
    Sll RevIfNeg(Sll pos) {  //!< 負なら末尾からの位置に変換
        rep(i, S) if (pos[i] < 0) pos[i] += dsize[i];
        return pos;
    }
    static ll AutoLen(Sll s_, Sll d_,
                      Sll dsz) {  // 位置s_から方向d_ではみ出すまでの長さ
        Sll e = dsz - 1;
        rep(i, S) e[i] *= (d_[i] >= 0);  // 方向が負の軸を0にする
        return Len(s_, e, d_);
    }
    /*---- 先頭位置s、方向d、終了条件eから長さlen計算 ----*/
    // template<size_t Q> static ll Len(array<ll,Q> s,array<ll,Q> e,array<ll,Q>
    // d){ 	ll ret=LLINF; 	rep(i,0,Q) chmin(ret, Len1(s[i],e[i],d[i]));
    // return
    // ret;
    // }
    static ll Len(Sll s, Sll e, Sll d) {
        ll ret = LLINF;
        rep(i, S) chmin(ret, Len1(s[i], e[i], d[i]));
        return ret;
    }
    static ll Len1(ll s, ll e, ll d) {
        if (d == 0) return LLINF;
        if (d < 0) {
            s = -s;
            e = -e;
            d = -d;
        }
        if (s > e) return 0;
        return (e - s) / d + 1;
    }
    /*---- 可変長引数をSllに変換 ----*/
    template<class... Q> static Sll SllD(Q... args) {
        return SllRec(0, args...);
    }
    template<class... Q> static Sll SllRec(ll i, ll first, Q... rest) {
        Sll sll = (i == S - 1) ? Sll() : SllRec(i + 1, rest...);
        sll[i] = first;
        return sll;
    }
    static Sll SllRec(ll i) { return Sll(); }
    /*---- dataの位置posの値取得 ----*/
    const R &OrgAt(Sll pos) const {
        rep(i, S) {
            if (pos[i] < 0 || dsize[i] <= pos[i]) return dummy;
        }
        return OrgAt_(data, pos);
    }
    template<class Q> using V = vector<Q>;
    template<class Q> using VV = V<V<Q>>;
    template<class Q> using VVV = V<V<V<Q>>>;
    using Vs = V<string>;
    using VVs = VV<string>;
    using ll1 = array<ll, 1>;
    using ll2 = array<ll, 2>;
    using ll3 = array<ll, 3>;
    auto &OrgAt_(V<R> &dat, ll1 pos) const {
        auto [i] = pos;
        return dat[i];
    }
    auto &OrgAt_(string &dat, ll1 pos) const {
        auto [i] = pos;
        return dat[i];
    }
    auto &OrgAt_(VV<R> &dat, ll2 pos) const {
        auto [i, j] = pos;
        return dat[i][j];
    }
    auto &OrgAt_(Vs &dat, ll2 pos) const {
        auto [i, j] = pos;
        return dat[i][j];
    }
    auto &OrgAt_(VVV<R> &dat, ll3 pos) const {
        auto [i, j, k] = pos;
        return dat[i][j][k];
    }
    auto &OrgAt_(VVs &dat, ll3 pos) const {
        auto [i, j, k] = pos;
        return dat[i][j][k];
    }
    /*---- dataの各軸size取得 ----*/
    static void SetDsize(V<R> &dat, ll1 &dsz) { dsz = {sz(dat)}; }
    static void SetDsize(string &dat, ll1 &dsz) { dsz = {sz(dat)}; }
    static void SetDsize(VV<R> &dat, ll2 &dsz) { dsz = {sz(dat), sz(dat[0])}; }
    static void SetDsize(Vs &dat, ll2 &dsz) { dsz = {sz(dat), sz(dat[0])}; }
    static void SetDsize(VVV<R> &dat, ll3 &dsz) {
        dsz = {sz(dat), sz(dat[0]), sz(dat[0][0])};
    }
    static void SetDsize(VVs &dat, ll3 &dsz) {
        dsz = {sz(dat), sz(dat[0]), sz(dat[0][0])};
    }
    typedef view1dIter<T, S, R> iterator;
    using value_type = R;
};
template<class Q> using V = vector<Q>;
template<class Q> using VV = V<V<Q>>;
template<class Q> using VVV = V<V<V<Q>>>;
template<class T> view1d(VVV<T>) -> view1d<VVV<T>, 3, T>;
template<class T> view1d(VV<T>) -> view1d<VV<T>, 2, T>;
template<class T> view1d(V<T>) -> view1d<V<T>, 1, T>;
;
view1d(VV<string>)->view1d<VV<string>, 3, char>;
;
view1d(V<string>)->view1d<V<string>, 2, char>;
;
view1d(string)->view1d<string, 1, char>;
template<class T, class S> view1d(VVV<T>, S, S, S) -> view1d<VVV<T>, 3, T>;
template<class T, class S> view1d(VV<T>, S, S, S) -> view1d<VV<T>, 2, T>;
template<class T, class S> view1d(V<T>, S, S, S) -> view1d<V<T>, 1, T>;
template<class S> view1d(VV<string>, S, S, S) -> view1d<VV<string>, 3, char>;
template<class S> view1d(V<string>, S, S, S) -> view1d<V<string>, 2, char>;
template<class S> view1d(string, S, S, S) -> view1d<string, 1, char>;

template<class VIEW2D> struct view2dIter {
    VIEW2D *vw = nullptr;
    ll idx = LLINF;
    view2dIter() {}
    view2dIter(VIEW2D *vw_, ll idx_) : vw(vw_), idx(idx_) {}
    view2dIter(const view2dIter &it) : vw(it.vw), idx(it.idx) {}
    auto &operator*() { return (*vw)[x(idx)][y(idx)]; }
    auto &operator*() const { return (*vw)[x(idx)][y(idx)]; }
    auto &operator[](ll i) { return (*vw)[x(idx + i)][y(idx + i)]; }
    auto &operator[](ll i) const { return (*vw)[x(idx + i)][y(idx + i)]; }
    auto &operator++() {
        idx++;
        return *this;
    }
    auto &operator--() {
        idx--;
        return *this;
    }
    auto operator++(int) {
        auto it = *this;
        idx++;
        return it;
    }
    auto operator--(int) {
        auto it = *this;
        idx--;
        return it;
    }
    auto &operator+=(ll n) {
        idx += n;
        return *this;
    }
    auto &operator-=(ll n) {
        idx -= n;
        return *this;
    }
    auto operator+(ll n) {
        auto it = *this;
        return it += n;
    }
    auto operator-(ll n) {
        auto it = *this;
        return it -= n;
    }
    ll operator-(const view2dIter &it) const { return idx - it.idx; }
    bool operator<(const view2dIter &it) const { return idx < it.idx; }
    bool operator>(const view2dIter &it) const { return idx > it.idx; }
    bool operator<=(const view2dIter &it) const { return idx <= it.idx; }
    bool operator>=(const view2dIter &it) const { return idx >= it.idx; }
    bool operator!=(const view2dIter &it) const { return idx != it.idx; }
    bool operator==(const view2dIter &it) const { return idx == it.idx; }
    ll x(ll i) const { return i / vw->leny(); }
    ll y(ll i) const { return i % vw->leny(); }
    using iterator_category = random_access_iterator_tag;
    using value_type = typename VIEW2D::value_type;
    using difference_type = ll;
    using pointer = value_type *;
    using reference = value_type &;
};

template<class T, size_t S, class R> struct view2d {
    using Sll = array<ll, S>;
    T &data;         // 参照先データ
    Sll dsize;       // 参照先データ各軸のサイズ
    Sll s = Sll();   // view始点
    Sll dx = Sll();  // view x軸方向
    Sll dy = Sll();  // view y軸方向
    ll xl;           // view x軸長さ
    ll yl;           // view y軸長さ
    R dummy = R();   // 範囲外の値
    /*---- コンストラクタ ----*/
    view2d(T &v) : data(v) {
        view1d<T, S, R>::SetDsize(v, dsize);
        dx[S - 2] = 1;
        dy[S - 1] = 1;
        xl = dsize[S - 2];
        yl = dsize[S - 1];
    }
    /*---- 演算 ----*/
    // template<class Q> auto &operator =(const Q &b){ rep(i,0,xl) (*this)[i]
    // =b; return *this; } template<class Q,size_t P,class O> auto
    // &operator+=(const view2d<Q,P,O> &b){ 	rep(i,0,xl) (*this)[i]
    // return
    // PlSeq(b); }
    /*---- getter ----*/
    ll size() const { return xl; }
    array<ll, 2> shape() const { return {xl, yl}; }
    ll lenx() const { return xl; }
    ll leny() const { return yl; }
    /// pll shape() const { return {xl,yl}; }
    view1d<T, S, R> operator[](ll i) {
        return view1d(data, s + dx * i, dy, yl, dummy);
    }
    const view1d<T, S, R> operator[](ll i) const {
        return view1d(data, s + dx * i, dy, yl, dummy);
    }
    R &at(ll i, ll j) {
        if (i < 0) i += xl;
        if (j < 0) j += yl;
        return (*this)[i][j];
    }
    vector<vector<R>> tovv() {
        vector<vector<R>> vvv(xl);
        /// rep(i,0,xl) vvv[i]=(*this)[i].tov();  return vvv;
        rep(i, xl) vvv[i] = (*this)[i];
        return vvv;
    }
    operator vector<vector<R>>() {
        vector<vector<R>> v(xl);
        rep(i, xl) v[i] = (*this)[i];
        return v;
    }
    auto begin() { return view2dIter(this, 0); }
    auto end() { return view2dIter(this, xl * yl); }
    /* よくわからない
    #if defined(_DEBUG)
        void dump() { ::dump(tovv()); }
    #endif
    */
    /*---- view設定 ----*/
    view2d<T, S, R> &dmy(R dmy_) {
        dummy = dmy_;
        return *this;
    }  // ダミー値セット
    template<class... Q>
    view2d<T, S, R> &st(Q... s_) {  // 始点set 負は末尾からの位置
        this->s = RevIfNeg(view1d<T, S, R>::SllD(s_...));
        this->xl = view1d<T, S, R>::AutoLen(this->s, this->dx, this->dsize);
        this->yl = view1d<T, S, R>::AutoLen(this->s, this->dy, this->dsize);
        return *this;
    }
    template<class... Q>
    view2d<T, S, R> &dirx(Q... d_) {  // x軸set、長さはdata端まで
        this->dx = view1d<T, S, R>::SllD(d_...);
        this->xl = view1d<T, S, R>::AutoLen(this->s, this->dx, this->dsize);
        return *this;
    }
    template<class... Q>
    view2d<T, S, R> &diry(Q... d_) {  // y軸set、長さはdata端まで
        this->dy = view1d<T, S, R>::SllD(d_...);
        this->yl = view1d<T, S, R>::AutoLen(this->s, this->dy, this->dsize);
        return *this;
    }
    template<class... Q> view2d<T, S, R> &mv(Q... s_) {  // 平行移動
        this->s += view1d<T, S, R>::SllD(s_...);
        return *this;
    }
    view2d<T, S, R> &lenx(ll xl_) {
        xl = xl_;
        return *this;
    }
    view2d<T, S, R> &leny(ll yl_) {
        yl = yl_;
        return *this;
    }
    view2d<T, S, R> &shape(ll xl_, ll yl_) {
        xl = xl_;
        yl = yl_;
        return *this;
    }
    template<class Q> view2d<T, S, R> &shape(Q &v) {
        xl = v.lenx();
        yl = v.leny();
        return *this;
    }
    view2d<T, S, R> &rot90() {
        s += dx * (xl - 1);
        swap(xl, yl);
        swap(dx, dy);
        dy *= -1;
        return *this;
    }
    view2d<T, S, R> &rot270() {
        s += dy * (yl - 1);
        swap(xl, yl);
        swap(dx, dy);
        dx *= -1;
        return *this;
    }
    view2d<T, S, R> &rot180() {
        s += dx * (xl - 1) + dy * (yl - 1);
        dx *= -1;
        dy *= -1;
        return *this;
    }
    view2d<T, S, R> &revx() {
        s += dx * (xl - 1);
        dx *= -1;
        return *this;
    }
    view2d<T, S, R> &revy() {
        s += dy * (yl - 1);
        dy *= -1;
        return *this;
    }
    view2d<T, S, R> &swapxy() {
        swap(xl, yl);
        swap(dx, dy);
        return *this;
    }  // xy軸入替

    /*---- utility ----*/
    Sll RevIfNeg(Sll pos) {  //!< 負なら末尾からの位置に変換
        rep(i, S) if (pos[i] < 0) pos[i] += dsize[i];
        return pos;
    }
    using value_type = R;
};
template<class T> view2d(VVV<T>) -> view2d<VVV<T>, 3, T>;
template<class T> view2d(VV<T>) -> view2d<VV<T>, 2, T>;
;
view2d(VV<string>)->view2d<VV<string>, 3, char>;
;
view2d(V<string>)->view2d<V<string>, 2, char>;

/*
zipは参照のpairを返す。それをさらに参照するのはまずいので、コピーする。
*/
template<class ZIP> struct zipIter {
    ZIP *z = nullptr;
    ll idx = LLINF;
    zipIter() {}
    zipIter(ZIP *z_, ll idx_) : z(z_), idx(idx_) {}
    zipIter(const zipIter<ZIP> &it) : z(it.z), idx(it.idx) {}
    auto operator*() { return (*z)[idx]; }        // 参照ではなく値戻し
    auto operator*() const { return (*z)[idx]; }  // 同上
    auto operator[](ll i) { return (*z)[idx + i]; }        // 同上
    auto operator[](ll i) const { return (*z)[idx + i]; }  // 同上
    auto &operator++() {
        idx++;
        return *this;
    }
    auto &operator--() {
        idx--;
        return *this;
    }
    auto operator++(int) {
        auto it = *this;
        idx++;
        return it;
    }
    auto operator--(int) {
        auto it = *this;
        idx--;
        return it;
    }
    auto &operator+=(ll n) {
        idx += n;
        return *this;
    }
    auto &operator-=(ll n) {
        idx -= n;
        return *this;
    }
    auto operator+(ll n) {
        auto it = *this;
        return it += n;
    }
    auto operator-(ll n) {
        auto it = *this;
        return it -= n;
    }
    ll operator-(const zipIter<ZIP> &it) const { return idx - it.idx; }
    bool operator<(const zipIter<ZIP> &it) const { return idx < it.idx; }
    bool operator>(const zipIter<ZIP> &it) const { return idx > it.idx; }
    bool operator<=(const zipIter<ZIP> &it) const { return idx <= it.idx; }
    bool operator>=(const zipIter<ZIP> &it) const { return idx >= it.idx; }
    bool operator!=(const zipIter<ZIP> &it) const { return idx != it.idx; }
    bool operator==(const zipIter<ZIP> &it) const { return idx == it.idx; }
    using iterator_category = random_access_iterator_tag;
    using value_type = typename ZIP::value_type;
    using difference_type = ll;
    using pointer = value_type *;
    using reference = value_type &;
};

template<class T, class S> struct zip2 {
    T &t;
    S &s;
    zip2(T &t_, S &s_) : t(t_), s(s_) {}
    ll size() const { return t.end() - t.begin(); }
    auto operator[](ll i) {
        return make_pair(ref(t.begin()[i]), ref(s.begin()[i]));
    }
    auto operator[](ll i) const {
        return make_pair(ref(t.begin()[i]), ref(s.begin()[i]));
    }
    auto begin() { return zipIter(this, 0); }
    auto end() { return zipIter(this, size()); }
    using value_type = pair<typename T::value_type, typename S::value_type>;
};
template<class T, class S, class R> struct zip3 {
    T &t;
    S &s;
    R &r;
    zip3(T &t_, S &s_, R &r_) : t(t_), s(s_), r(r_) {}
    ll size() const { return t.end() - t.begin(); }
    auto operator[](ll i) {
        return make_tuple(ref(t.begin()[i]), ref(s.begin()[i]),
                          ref(r.begin()[i]));
    }
    auto operator[](ll i) const {
        return make_tuple(ref(t.begin()[i]), ref(s.begin()[i]),
                          ref(r.begin()[i]));
    }
    auto begin() { return zipIter(this, 0); }
    auto end() { return zipIter(this, size()); }
    using value_type = tuple<typename T::value_type, typename S::value_type,
                             typename R::value_type>;
};

struct {
    system_clock::time_point st = system_clock::now();
    ll operator()() const {
        return duration_cast<microseconds>(system_clock::now() - st).count() /
               1000;
    }
} timeget;

template<ll MOD> struct mll_ {
    ll val;
    mll_(ll v = 0) : val(v % MOD) {
        if (val < 0) val += MOD;
    }
    bool isnone() const { return val == -1; }  // true:値なし
    mll_ &none() {
        val = -1;
        return *this;
    }  // 値なしにする
    mll_ operator-() const { return -val; }
    mll_ operator+(const mll_ &b) const { return val + b.val; }
    mll_ operator-(const mll_ &b) const { return val - b.val; }
    mll_ operator*(const mll_ &b) const { return val * b.val; }
    mll_ operator/(const mll_ &b) const { return mll_(*this) /= b; }
    mll_ operator+(ll b) const { return *this + mll_(b); }
    mll_ operator-(ll b) const { return *this - mll_(b); }
    mll_ operator*(ll b) const { return *this * mll_(b); }
    friend mll_ operator+(ll a, const mll_ &b) { return b + a; }
    friend mll_ operator-(ll a, const mll_ &b) { return -b + a; }
    friend mll_ operator*(ll a, const mll_ &b) { return b * a; }
    friend mll_ operator/(ll a, const mll_ &b) { return mll_(a) / b; }
    mll_ &operator+=(const mll_ &b) {
        val = (val + b.val) % MOD;
        return *this;
    }
    mll_ &operator-=(const mll_ &b) {
        val = (val + MOD - b.val) % MOD;
        return *this;
    }
    mll_ &operator*=(const mll_ &b) {
        val = (val * b.val) % MOD;
        return *this;
    }
    mll_ &operator/=(const mll_ &b) {
        ll c = b.val, d = MOD, u = 1, v = 0;
        while (d) {
            ll t = c / d;
            c -= t * d;
            swap(c, d);
            u -= t * v;
            swap(u, v);
        }
        val = val * u % MOD;
        if (val < 0) val += MOD;
        return *this;
    }
    mll_ &operator+=(ll b) { return *this += mll_(b); }
    mll_ &operator-=(ll b) { return *this -= mll_(b); }
    mll_ &operator*=(ll b) { return *this *= mll_(b); }
    mll_ &operator/=(ll b) { return *this /= mll_(b); }
    bool operator==(const mll_ &b) const { return val == b.val; }
    bool operator!=(const mll_ &b) const { return val != b.val; }
    bool operator==(ll b) const { return *this == mll_(b); }
    bool operator!=(ll b) const { return *this != mll_(b); }
    friend bool operator==(ll a, const mll_ &b) { return mll_(a) == b.val; }
    friend bool operator!=(ll a, const mll_ &b) { return mll_(a) != b.val; }
    friend ostream &operator<<(ostream &os, const mll_ &a) {
        return os << a.val;
    }
    friend istream &operator>>(istream &is, mll_ &a) { return is >> a.val; }
    static mll_ Combination(ll a, ll b) {
        chmin(b, a - b);
        if (b < 0) return mll_(0);
        mll_ c = 1, d = 1;
        rep(i, b) c *= a - i;
        rep(i, b) d *= i + 1;
        return c / d;
    }
    enum { modll = MOD };
};

#if 1
#define MODLL (1000000007LL)
#else
#define MODLL (998244353LL)
#endif
using mint = mll_<MODLL>;

//////////////////////////////////////////

template<class T> struct SET : set<T> {
    using P = set<T>;
    typename P::iterator it = P::end();
    template<class... Args> SET(Args... args) : P(args...) {}
    SET(initializer_list<T> a) : P(a.begin(), a.end()) {}
    ll size() const { return (ll)P::size(); }
    bool insert(const T &x) {
        bool r;
        tie(it, r) = P::insert(x);
        return r;
    }
    template<class It> void insert(It st, It en) { P::insert(st, en); }
    void insert(initializer_list<T> a) { P::insert(a.begin(), a.end()); }
    template<class... A> bool emplace(A &&...a) {
        bool r;
        tie(it, r) = P::emplace(a...);
        return r;
    }
    void eraseit() { it = P::erase(it); }
    void find(const T &x) { it = P::find(x); }
    bool contains(const T &x) { return P::count(x) == 1; }
    void lower_bound(const T &x) { it = P::lower_bound(x); }
    void upper_bound(const T &x) { it = P::upper_bound(x); }
    bool isend() { return it == P::end(); }
    T getit() { return *it; }
    T next() { return *(++it); }
    T prev() { return *(--it); }
    bool nextok() { return !isend() && it != --P::end(); }
    bool prevok() { return it != P::begin(); }
    T front() { return *(it = P::begin()); }
    T back() { return *(it = --P::end()); }
    void pop_front() {
        front();
        eraseit();
    }
    void pop_back() {
        back();
        eraseit();
    }
    void push_front(const T &x) { it = P::insert(P::begin(), x); }
    void push_back(const T &x) { it = P::insert(P::end(), x); }
    void push_out(SET &b) {
        b.push_front(back());
        pop_back();
    }
    void pull_in(SET &b) {
        push_back(b.front());
        b.pop_front();
    }
};
/*
front(), back(), pop_front(), pop_back(), contains(x), push_front(x),
push_back(x) ある要素の次、前を連続して得る機能 find(x), next(), prev(),
nextok(), prevok()
*/

//////////////////////////////////////////

void cin2solve() {
    int n;
    cin >> n;
    V<tuple<int, int, int>> hti(n);
    rep(i, n) cin >> get<0>(hti[i]);
    rep(i, n) {
        cin >> get<1>(hti[i]);
        get<1>(hti[i]) *= -1;
        get<2>(hti[i]) = i;
    }
    sort(all(hti));
    VI h(n), t(n), p(n), q(n);
    rep(i, n) {
        tie(h[i], t[i], p[i]) = hti[i];
        t[i] *= -1;
        q[p[i]] = i;
    }
    const int logn = 18;
    auto nxt = defvec<int>(-1, logn + 1, n);  // [)
    VI m = t;
    rep(i, n - 1) chmax(m[i + 1], m[i]);
    rep(i, n) nxt[0][i] = int(upper_bound(all(h), m[i]) - h.begin()) - 1;
    rep(j, logn) rep(i, n) {
        if (nxt[j][i] != -1) nxt[j + 1][i] = nxt[j][nxt[j][i]];
    }
    int _q;
    cin >> _q;
    while (_q--) {
        int a, b;
        cin >> a >> b;
        --a, --b;
        a = q[a], b = q[b];
        if (h[b] <= t[a]) print(1);
        else {
            int i = int(upper_bound(all(h), t[a]) - h.begin()) - 1;
            if (i == -1) print(-1);
            else if (nxt[0][i] >= nxt[1][i]) {
                // 以降も減るだけなのでここで試す
                if (nxt[0][i] >= b) print(2);
                else {
                    print(-1);
                }
            }
            else {
                // だんだん増えるはず
                int ans = 1;
                rrep(j, logn + 1) {
                    if (nxt[j][i] < b) {
                        ans += (1 << j);
                        i = nxt[j][i];
                    }
                }
                if (ans == (1 << logn + 1)) print(-1);
                else print(ans + 1);
            }
        }
    }
    return;
}

//////////////////////////////////////////

int main() {
#if 1
    cin2solve();
    // generand();
#else
    ll t;
    cin >> t;
    rep(i, t) {
        cin2solve();
        // generand();
    }
#endif
    // cerr << timeget() <<"ms"<< endl;
    return 0;
}
yukicoder

結果

ソースコード
