tests/range_parallel_dsu.test.cpp

• View this file on GitHub
• Last update: 2025-08-10 01:57:18+09:00
• Problem: https://judge.yosupo.jp/problem/range_parallel_unionfind

Depends on

• std::abs(x) extended for my library (tools/abs.hpp)
• $\left\lceil \frac{x}{y} \right\rceil$ (tools/ceil.hpp)
• tools/detail/rolling_hash.hpp
• Extended Euclidean algorithm (tools/extgcd.hpp)
• Floyd's cycle-finding algorithm (tools/find_cycle.hpp)
• $\left\lfloor \frac{x}{y} \right\rfloor$ (tools/floor.hpp)
• std::gcd(m, n) extended for my library (tools/gcd.hpp)
• std::is_arithmetic extended for tools::int128_t and tools::uint128_t (tools/is_arithmetic.hpp)
• std::is_integral extended for tools::int128_t and tools::uint128_t (tools/is_integral.hpp)
• Check whether T is a monoid (tools/is_monoid.hpp)
• std::is_unsigned extended for tools::int128_t and tools::uint128_t (tools/is_unsigned.hpp)
• Minimum non-negative reminder (tools/mod.hpp)
• $\mathbb{Z} / (2^{61} - 1) \mathbb{Z}$ (tools/modint_for_rolling_hash.hpp)
• Typical monoids (tools/monoid.hpp)
• The number of nanoseconds that have elapsed since epoch (tools/now.hpp)
• $b^n$ under a given monoid, and std::pow(b, n) extended for my library (tools/pow.hpp)
• Cache for $b^n \pmod{M}$ (tools/pow_mod_cache.hpp)
• Disjoint set union, but allows range parallel union (tools/range_parallel_dsu.hpp)
• $x^2$ under a given monoid (tools/square.hpp)

Code

// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/range_parallel_unionfind

#include <iostream>
#include <utility>
#include <vector>
#include "atcoder/modint.hpp"
#include "tools/range_parallel_dsu.hpp"
#include "tools/square.hpp"

using mint = atcoder::modint998244353;

int main() {
  std::cin.tie(nullptr);
  std::ios_base::sync_with_stdio(false);

  int N, Q;
  std::cin >> N >> Q;
  std::vector<std::pair<mint, mint>> x(N);
  for (int i = 0; i < N; ++i) {
    int x_i;
    std::cin >> x_i;
    x[i] = {mint::raw(x_i), tools::square(mint::raw(x_i))};
  }

  const auto two_inv = mint::raw(2).inv();
  tools::range_parallel_dsu dsu(N);
  auto answer = mint::raw(0);
  for (int q = 0; q < Q; ++q) {
    int k, a, b;
    std::cin >> k >> a >> b;
    for (const auto& [r1, r2] : dsu.merge(a, b, k)) {
      answer -= (tools::square(x[r1].first) - x[r1].second) * two_inv;
      answer -= (tools::square(x[r2].first) - x[r2].second) * two_inv;
      x[r1].first += x[r2].first;
      x[r1].second += x[r2].second;
      x[r2] = {mint::raw(0), mint::raw(0)};
      answer += (tools::square(x[r1].first) - x[r1].second) * two_inv;
    }
    std::cout << answer.val() << '\n';
  }

  return 0;
}

#line 1 "tests/range_parallel_dsu.test.cpp"
// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/range_parallel_unionfind

#include <iostream>
#include <utility>
#include <vector>
#line 1 "lib/ac-library/atcoder/modint.hpp"



#include <cassert>
#include <numeric>
#include <type_traits>

#ifdef _MSC_VER
#include <intrin.h>
#endif

#line 1 "lib/ac-library/atcoder/internal_math.hpp"



#line 5 "lib/ac-library/atcoder/internal_math.hpp"

#ifdef _MSC_VER
#include <intrin.h>
#endif

namespace atcoder {

namespace internal {

// @param m `1 <= m`
// @return x mod m
constexpr long long safe_mod(long long x, long long m) {
    x %= m;
    if (x < 0) x += m;
    return x;
}

// Fast modular multiplication by barrett reduction
// Reference: https://en.wikipedia.org/wiki/Barrett_reduction
// NOTE: reconsider after Ice Lake
struct barrett {
    unsigned int _m;
    unsigned long long im;

    // @param m `1 <= m`
    explicit barrett(unsigned int m) : _m(m), im((unsigned long long)(-1) / m + 1) {}

    // @return m
    unsigned int umod() const { return _m; }

    // @param a `0 <= a < m`
    // @param b `0 <= b < m`
    // @return `a * b % m`
    unsigned int mul(unsigned int a, unsigned int b) const {
        // [1] m = 1
        // a = b = im = 0, so okay

        // [2] m >= 2
        // im = ceil(2^64 / m)
        // -> im * m = 2^64 + r (0 <= r < m)
        // let z = a*b = c*m + d (0 <= c, d < m)
        // a*b * im = (c*m + d) * im = c*(im*m) + d*im = c*2^64 + c*r + d*im
        // c*r + d*im < m * m + m * im < m * m + 2^64 + m <= 2^64 + m * (m + 1) < 2^64 * 2
        // ((ab * im) >> 64) == c or c + 1
        unsigned long long z = a;
        z *= b;
#ifdef _MSC_VER
        unsigned long long x;
        _umul128(z, im, &x);
#else
        unsigned long long x =
            (unsigned long long)(((unsigned __int128)(z)*im) >> 64);
#endif
        unsigned long long y = x * _m;
        return (unsigned int)(z - y + (z < y ? _m : 0));
    }
};

// @param n `0 <= n`
// @param m `1 <= m`
// @return `(x ** n) % m`
constexpr long long pow_mod_constexpr(long long x, long long n, int m) {
    if (m == 1) return 0;
    unsigned int _m = (unsigned int)(m);
    unsigned long long r = 1;
    unsigned long long y = safe_mod(x, m);
    while (n) {
        if (n & 1) r = (r * y) % _m;
        y = (y * y) % _m;
        n >>= 1;
    }
    return r;
}

// Reference:
// M. Forisek and J. Jancina,
// Fast Primality Testing for Integers That Fit into a Machine Word
// @param n `0 <= n`
constexpr bool is_prime_constexpr(int n) {
    if (n <= 1) return false;
    if (n == 2 || n == 7 || n == 61) return true;
    if (n % 2 == 0) return false;
    long long d = n - 1;
    while (d % 2 == 0) d /= 2;
    constexpr long long bases[3] = {2, 7, 61};
    for (long long a : bases) {
        long long t = d;
        long long y = pow_mod_constexpr(a, t, n);
        while (t != n - 1 && y != 1 && y != n - 1) {
            y = y * y % n;
            t <<= 1;
        }
        if (y != n - 1 && t % 2 == 0) {
            return false;
        }
    }
    return true;
}
template <int n> constexpr bool is_prime = is_prime_constexpr(n);

// @param b `1 <= b`
// @return pair(g, x) s.t. g = gcd(a, b), xa = g (mod b), 0 <= x < b/g
constexpr std::pair<long long, long long> inv_gcd(long long a, long long b) {
    a = safe_mod(a, b);
    if (a == 0) return {b, 0};

    // Contracts:
    // [1] s - m0 * a = 0 (mod b)
    // [2] t - m1 * a = 0 (mod b)
    // [3] s * |m1| + t * |m0| <= b
    long long s = b, t = a;
    long long m0 = 0, m1 = 1;

    while (t) {
        long long u = s / t;
        s -= t * u;
        m0 -= m1 * u;  // |m1 * u| <= |m1| * s <= b

        // [3]:
        // (s - t * u) * |m1| + t * |m0 - m1 * u|
        // <= s * |m1| - t * u * |m1| + t * (|m0| + |m1| * u)
        // = s * |m1| + t * |m0| <= b

        auto tmp = s;
        s = t;
        t = tmp;
        tmp = m0;
        m0 = m1;
        m1 = tmp;
    }
    // by [3]: |m0| <= b/g
    // by g != b: |m0| < b/g
    if (m0 < 0) m0 += b / s;
    return {s, m0};
}

// Compile time primitive root
// @param m must be prime
// @return primitive root (and minimum in now)
constexpr int primitive_root_constexpr(int m) {
    if (m == 2) return 1;
    if (m == 167772161) return 3;
    if (m == 469762049) return 3;
    if (m == 754974721) return 11;
    if (m == 998244353) return 3;
    int divs[20] = {};
    divs[0] = 2;
    int cnt = 1;
    int x = (m - 1) / 2;
    while (x % 2 == 0) x /= 2;
    for (int i = 3; (long long)(i)*i <= x; i += 2) {
        if (x % i == 0) {
            divs[cnt++] = i;
            while (x % i == 0) {
                x /= i;
            }
        }
    }
    if (x > 1) {
        divs[cnt++] = x;
    }
    for (int g = 2;; g++) {
        bool ok = true;
        for (int i = 0; i < cnt; i++) {
            if (pow_mod_constexpr(g, (m - 1) / divs[i], m) == 1) {
                ok = false;
                break;
            }
        }
        if (ok) return g;
    }
}
template <int m> constexpr int primitive_root = primitive_root_constexpr(m);

// @param n `n < 2^32`
// @param m `1 <= m < 2^32`
// @return sum_{i=0}^{n-1} floor((ai + b) / m) (mod 2^64)
unsigned long long floor_sum_unsigned(unsigned long long n,
                                      unsigned long long m,
                                      unsigned long long a,
                                      unsigned long long b) {
    unsigned long long ans = 0;
    while (true) {
        if (a >= m) {
            ans += n * (n - 1) / 2 * (a / m);
            a %= m;
        }
        if (b >= m) {
            ans += n * (b / m);
            b %= m;
        }

        unsigned long long y_max = a * n + b;
        if (y_max < m) break;
        // y_max < m * (n + 1)
        // floor(y_max / m) <= n
        n = (unsigned long long)(y_max / m);
        b = (unsigned long long)(y_max % m);
        std::swap(m, a);
    }
    return ans;
}

}  // namespace internal

}  // namespace atcoder


#line 1 "lib/ac-library/atcoder/internal_type_traits.hpp"



#line 7 "lib/ac-library/atcoder/internal_type_traits.hpp"

namespace atcoder {

namespace internal {

#ifndef _MSC_VER
template <class T>
using is_signed_int128 =
    typename std::conditional<std::is_same<T, __int128_t>::value ||
                                  std::is_same<T, __int128>::value,
                              std::true_type,
                              std::false_type>::type;

template <class T>
using is_unsigned_int128 =
    typename std::conditional<std::is_same<T, __uint128_t>::value ||
                                  std::is_same<T, unsigned __int128>::value,
                              std::true_type,
                              std::false_type>::type;

template <class T>
using make_unsigned_int128 =
    typename std::conditional<std::is_same<T, __int128_t>::value,
                              __uint128_t,
                              unsigned __int128>;

template <class T>
using is_integral = typename std::conditional<std::is_integral<T>::value ||
                                                  is_signed_int128<T>::value ||
                                                  is_unsigned_int128<T>::value,
                                              std::true_type,
                                              std::false_type>::type;

template <class T>
using is_signed_int = typename std::conditional<(is_integral<T>::value &&
                                                 std::is_signed<T>::value) ||
                                                    is_signed_int128<T>::value,
                                                std::true_type,
                                                std::false_type>::type;

template <class T>
using is_unsigned_int =
    typename std::conditional<(is_integral<T>::value &&
                               std::is_unsigned<T>::value) ||
                                  is_unsigned_int128<T>::value,
                              std::true_type,
                              std::false_type>::type;

template <class T>
using to_unsigned = typename std::conditional<
    is_signed_int128<T>::value,
    make_unsigned_int128<T>,
    typename std::conditional<std::is_signed<T>::value,
                              std::make_unsigned<T>,
                              std::common_type<T>>::type>::type;

#else

template <class T> using is_integral = typename std::is_integral<T>;

template <class T>
using is_signed_int =
    typename std::conditional<is_integral<T>::value && std::is_signed<T>::value,
                              std::true_type,
                              std::false_type>::type;

template <class T>
using is_unsigned_int =
    typename std::conditional<is_integral<T>::value &&
                                  std::is_unsigned<T>::value,
                              std::true_type,
                              std::false_type>::type;

template <class T>
using to_unsigned = typename std::conditional<is_signed_int<T>::value,
                                              std::make_unsigned<T>,
                                              std::common_type<T>>::type;

#endif

template <class T>
using is_signed_int_t = std::enable_if_t<is_signed_int<T>::value>;

template <class T>
using is_unsigned_int_t = std::enable_if_t<is_unsigned_int<T>::value>;

template <class T> using to_unsigned_t = typename to_unsigned<T>::type;

}  // namespace internal

}  // namespace atcoder


#line 14 "lib/ac-library/atcoder/modint.hpp"

namespace atcoder {

namespace internal {

struct modint_base {};
struct static_modint_base : modint_base {};

template <class T> using is_modint = std::is_base_of<modint_base, T>;
template <class T> using is_modint_t = std::enable_if_t<is_modint<T>::value>;

}  // namespace internal

template <int m, std::enable_if_t<(1 <= m)>* = nullptr>
struct static_modint : internal::static_modint_base {
    using mint = static_modint;

  public:
    static constexpr int mod() { return m; }
    static mint raw(int v) {
        mint x;
        x._v = v;
        return x;
    }

    static_modint() : _v(0) {}
    template <class T, internal::is_signed_int_t<T>* = nullptr>
    static_modint(T v) {
        long long x = (long long)(v % (long long)(umod()));
        if (x < 0) x += umod();
        _v = (unsigned int)(x);
    }
    template <class T, internal::is_unsigned_int_t<T>* = nullptr>
    static_modint(T v) {
        _v = (unsigned int)(v % umod());
    }

    int val() const { return _v; }

    mint& operator++() {
        _v++;
        if (_v == umod()) _v = 0;
        return *this;
    }
    mint& operator--() {
        if (_v == 0) _v = umod();
        _v--;
        return *this;
    }
    mint operator++(int) {
        mint result = *this;
        ++*this;
        return result;
    }
    mint operator--(int) {
        mint result = *this;
        --*this;
        return result;
    }

    mint& operator+=(const mint& rhs) {
        _v += rhs._v;
        if (_v >= umod()) _v -= umod();
        return *this;
    }
    mint& operator-=(const mint& rhs) {
        _v -= rhs._v;
        if (_v >= umod()) _v += umod();
        return *this;
    }
    mint& operator*=(const mint& rhs) {
        unsigned long long z = _v;
        z *= rhs._v;
        _v = (unsigned int)(z % umod());
        return *this;
    }
    mint& operator/=(const mint& rhs) { return *this = *this * rhs.inv(); }

    mint operator+() const { return *this; }
    mint operator-() const { return mint() - *this; }

    mint pow(long long n) const {
        assert(0 <= n);
        mint x = *this, r = 1;
        while (n) {
            if (n & 1) r *= x;
            x *= x;
            n >>= 1;
        }
        return r;
    }
    mint inv() const {
        if (prime) {
            assert(_v);
            return pow(umod() - 2);
        } else {
            auto eg = internal::inv_gcd(_v, m);
            assert(eg.first == 1);
            return eg.second;
        }
    }

    friend mint operator+(const mint& lhs, const mint& rhs) {
        return mint(lhs) += rhs;
    }
    friend mint operator-(const mint& lhs, const mint& rhs) {
        return mint(lhs) -= rhs;
    }
    friend mint operator*(const mint& lhs, const mint& rhs) {
        return mint(lhs) *= rhs;
    }
    friend mint operator/(const mint& lhs, const mint& rhs) {
        return mint(lhs) /= rhs;
    }
    friend bool operator==(const mint& lhs, const mint& rhs) {
        return lhs._v == rhs._v;
    }
    friend bool operator!=(const mint& lhs, const mint& rhs) {
        return lhs._v != rhs._v;
    }

  private:
    unsigned int _v;
    static constexpr unsigned int umod() { return m; }
    static constexpr bool prime = internal::is_prime<m>;
};

template <int id> struct dynamic_modint : internal::modint_base {
    using mint = dynamic_modint;

  public:
    static int mod() { return (int)(bt.umod()); }
    static void set_mod(int m) {
        assert(1 <= m);
        bt = internal::barrett(m);
    }
    static mint raw(int v) {
        mint x;
        x._v = v;
        return x;
    }

    dynamic_modint() : _v(0) {}
    template <class T, internal::is_signed_int_t<T>* = nullptr>
    dynamic_modint(T v) {
        long long x = (long long)(v % (long long)(mod()));
        if (x < 0) x += mod();
        _v = (unsigned int)(x);
    }
    template <class T, internal::is_unsigned_int_t<T>* = nullptr>
    dynamic_modint(T v) {
        _v = (unsigned int)(v % mod());
    }

    int val() const { return _v; }

    mint& operator++() {
        _v++;
        if (_v == umod()) _v = 0;
        return *this;
    }
    mint& operator--() {
        if (_v == 0) _v = umod();
        _v--;
        return *this;
    }
    mint operator++(int) {
        mint result = *this;
        ++*this;
        return result;
    }
    mint operator--(int) {
        mint result = *this;
        --*this;
        return result;
    }

    mint& operator+=(const mint& rhs) {
        _v += rhs._v;
        if (_v >= umod()) _v -= umod();
        return *this;
    }
    mint& operator-=(const mint& rhs) {
        _v += mod() - rhs._v;
        if (_v >= umod()) _v -= umod();
        return *this;
    }
    mint& operator*=(const mint& rhs) {
        _v = bt.mul(_v, rhs._v);
        return *this;
    }
    mint& operator/=(const mint& rhs) { return *this = *this * rhs.inv(); }

    mint operator+() const { return *this; }
    mint operator-() const { return mint() - *this; }

    mint pow(long long n) const {
        assert(0 <= n);
        mint x = *this, r = 1;
        while (n) {
            if (n & 1) r *= x;
            x *= x;
            n >>= 1;
        }
        return r;
    }
    mint inv() const {
        auto eg = internal::inv_gcd(_v, mod());
        assert(eg.first == 1);
        return eg.second;
    }

    friend mint operator+(const mint& lhs, const mint& rhs) {
        return mint(lhs) += rhs;
    }
    friend mint operator-(const mint& lhs, const mint& rhs) {
        return mint(lhs) -= rhs;
    }
    friend mint operator*(const mint& lhs, const mint& rhs) {
        return mint(lhs) *= rhs;
    }
    friend mint operator/(const mint& lhs, const mint& rhs) {
        return mint(lhs) /= rhs;
    }
    friend bool operator==(const mint& lhs, const mint& rhs) {
        return lhs._v == rhs._v;
    }
    friend bool operator!=(const mint& lhs, const mint& rhs) {
        return lhs._v != rhs._v;
    }

  private:
    unsigned int _v;
    static internal::barrett bt;
    static unsigned int umod() { return bt.umod(); }
};
template <int id> internal::barrett dynamic_modint<id>::bt(998244353);

using modint998244353 = static_modint<998244353>;
using modint1000000007 = static_modint<1000000007>;
using modint = dynamic_modint<-1>;

namespace internal {

template <class T>
using is_static_modint = std::is_base_of<internal::static_modint_base, T>;

template <class T>
using is_static_modint_t = std::enable_if_t<is_static_modint<T>::value>;

template <class> struct is_dynamic_modint : public std::false_type {};
template <int id>
struct is_dynamic_modint<dynamic_modint<id>> : public std::true_type {};

template <class T>
using is_dynamic_modint_t = std::enable_if_t<is_dynamic_modint<T>::value>;

}  // namespace internal

}  // namespace atcoder


#line 1 "tools/range_parallel_dsu.hpp"



#include <algorithm>
#line 6 "tools/range_parallel_dsu.hpp"
#include <iterator>
#line 1 "lib/ac-library/atcoder/segtree.hpp"



#line 6 "lib/ac-library/atcoder/segtree.hpp"
#include <functional>
#line 8 "lib/ac-library/atcoder/segtree.hpp"

#line 1 "lib/ac-library/atcoder/internal_bit.hpp"



#ifdef _MSC_VER
#include <intrin.h>
#endif

#if __cplusplus >= 202002L
#include <bit>
#endif

namespace atcoder {

namespace internal {

#if __cplusplus >= 202002L

using std::bit_ceil;

#else

// @return same with std::bit::bit_ceil
unsigned int bit_ceil(unsigned int n) {
    unsigned int x = 1;
    while (x < (unsigned int)(n)) x *= 2;
    return x;
}

#endif

// @param n `1 <= n`
// @return same with std::bit::countr_zero
int countr_zero(unsigned int n) {
#ifdef _MSC_VER
    unsigned long index;
    _BitScanForward(&index, n);
    return index;
#else
    return __builtin_ctz(n);
#endif
}

// @param n `1 <= n`
// @return same with std::bit::countr_zero
constexpr int countr_zero_constexpr(unsigned int n) {
    int x = 0;
    while (!(n & (1 << x))) x++;
    return x;
}

}  // namespace internal

}  // namespace atcoder


#line 10 "lib/ac-library/atcoder/segtree.hpp"

namespace atcoder {

#if __cplusplus >= 201703L

template <class S, auto op, auto e> struct segtree {
    static_assert(std::is_convertible_v<decltype(op), std::function<S(S, S)>>,
                  "op must work as S(S, S)");
    static_assert(std::is_convertible_v<decltype(e), std::function<S()>>,
                  "e must work as S()");

#else

template <class S, S (*op)(S, S), S (*e)()> struct segtree {

#endif

  public:
    segtree() : segtree(0) {}
    explicit segtree(int n) : segtree(std::vector<S>(n, e())) {}
    explicit segtree(const std::vector<S>& v) : _n(int(v.size())) {
        size = (int)internal::bit_ceil((unsigned int)(_n));
        log = internal::countr_zero((unsigned int)size);
        d = std::vector<S>(2 * size, e());
        for (int i = 0; i < _n; i++) d[size + i] = v[i];
        for (int i = size - 1; i >= 1; i--) {
            update(i);
        }
    }

    void set(int p, S x) {
        assert(0 <= p && p < _n);
        p += size;
        d[p] = x;
        for (int i = 1; i <= log; i++) update(p >> i);
    }

    S get(int p) const {
        assert(0 <= p && p < _n);
        return d[p + size];
    }

    S prod(int l, int r) const {
        assert(0 <= l && l <= r && r <= _n);
        S sml = e(), smr = e();
        l += size;
        r += size;

        while (l < r) {
            if (l & 1) sml = op(sml, d[l++]);
            if (r & 1) smr = op(d[--r], smr);
            l >>= 1;
            r >>= 1;
        }
        return op(sml, smr);
    }

    S all_prod() const { return d[1]; }

    template <bool (*f)(S)> int max_right(int l) const {
        return max_right(l, [](S x) { return f(x); });
    }
    template <class F> int max_right(int l, F f) const {
        assert(0 <= l && l <= _n);
        assert(f(e()));
        if (l == _n) return _n;
        l += size;
        S sm = e();
        do {
            while (l % 2 == 0) l >>= 1;
            if (!f(op(sm, d[l]))) {
                while (l < size) {
                    l = (2 * l);
                    if (f(op(sm, d[l]))) {
                        sm = op(sm, d[l]);
                        l++;
                    }
                }
                return l - size;
            }
            sm = op(sm, d[l]);
            l++;
        } while ((l & -l) != l);
        return _n;
    }

    template <bool (*f)(S)> int min_left(int r) const {
        return min_left(r, [](S x) { return f(x); });
    }
    template <class F> int min_left(int r, F f) const {
        assert(0 <= r && r <= _n);
        assert(f(e()));
        if (r == 0) return 0;
        r += size;
        S sm = e();
        do {
            r--;
            while (r > 1 && (r % 2)) r >>= 1;
            if (!f(op(d[r], sm))) {
                while (r < size) {
                    r = (2 * r + 1);
                    if (f(op(d[r], sm))) {
                        sm = op(d[r], sm);
                        r--;
                    }
                }
                return r + 1 - size;
            }
            sm = op(d[r], sm);
        } while ((r & -r) != r);
        return 0;
    }

  private:
    int _n, size, log;
    std::vector<S> d;

    void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
};

}  // namespace atcoder


#line 1 "tools/modint_for_rolling_hash.hpp"



#line 1 "tools/detail/rolling_hash.hpp"



#include <cstdint>
#line 6 "tools/detail/rolling_hash.hpp"
#include <tuple>
#line 1 "tools/pow.hpp"



#line 6 "tools/pow.hpp"
#include <cmath>
#line 1 "tools/monoid.hpp"



#line 6 "tools/monoid.hpp"
#include <cstddef>
#include <limits>
#line 1 "tools/gcd.hpp"



#line 6 "tools/gcd.hpp"

namespace tools {
  template <typename M, typename N> requires (
    ::std::is_integral_v<M> && !::std::is_same_v<::std::remove_cv_t<M>, bool>
    && ::std::is_integral_v<N> && !::std::is_same_v<::std::remove_cv_t<N>, bool>
  )
  constexpr ::std::common_type_t<M, N> gcd(const M m, const N n) {
    return ::std::gcd(m, n);
  }
}


#line 1 "tools/is_arithmetic.hpp"



#line 5 "tools/is_arithmetic.hpp"

namespace tools {
  template <typename T>
  struct is_arithmetic : ::std::is_arithmetic<T> {};

  template <typename T>
  inline constexpr bool is_arithmetic_v = ::tools::is_arithmetic<T>::value;
}


#line 1 "tools/is_integral.hpp"



#line 5 "tools/is_integral.hpp"

namespace tools {
  template <typename T>
  struct is_integral : ::std::is_integral<T> {};

  template <typename T>
  inline constexpr bool is_integral_v = ::tools::is_integral<T>::value;
}


#line 12 "tools/monoid.hpp"

namespace tools {
  namespace monoid {
    template <typename M>
    class bit_and {
      using VR = ::std::conditional_t<::tools::is_arithmetic_v<M> && sizeof(M) <= sizeof(::std::size_t), const M, const M&>;

    public:
      using T = M;
      static T op(VR x, VR y) {
        return x & y;
      }
      static T e() {
        return ::std::numeric_limits<T>::max();
      }
    };

    template <typename M>
    class bit_or {
      using VR = ::std::conditional_t<::tools::is_arithmetic_v<M> && sizeof(M) <= sizeof(::std::size_t), const M, const M&>;

    public:
      using T = M;
      static T op(VR x, VR y) {
        return x | y;
      }
      static T e() {
        return T(0);
      }
    };

    template <typename M> requires (!::tools::is_arithmetic_v<M> || (::tools::is_integral_v<M> && !::std::is_same_v<M, bool>))
    class gcd {
      using VR = ::std::conditional_t<::tools::is_arithmetic_v<M> && sizeof(M) <= sizeof(::std::size_t), const M, const M&>;

    public:
      using T = M;
      static T op(VR x, VR y) {
        return ::tools::gcd(x, y);
      }
      static T e() {
        return T(0);
      }
    };

    template <typename M, M ...dummy>
    class max;

    template <typename M> requires (::tools::is_arithmetic_v<M>)
    class max<M> {
      using VR = ::std::conditional_t<::tools::is_arithmetic_v<M> && sizeof(M) <= sizeof(::std::size_t), const M, const M&>;

    public:
      using T = M;
      static T op(VR x, VR y) {
        return ::std::max(x, y);
      }
      static T e() {
        if constexpr (::tools::is_integral_v<M>) {
          return ::std::numeric_limits<M>::min();
        } else {
          return -::std::numeric_limits<M>::infinity();
        }
      }
    };

    template <typename M, M E>
    class max<M, E> {
      using VR = ::std::conditional_t<::tools::is_arithmetic_v<M> && sizeof(M) <= sizeof(::std::size_t), const M, const M&>;

    public:
      using T = M;
      static T op(VR x, VR y) {
        assert(E <= x);
        assert(E <= y);
        return ::std::max(x, y);
      }
      static T e() {
        return E;
      }
    };

    template <typename M, M ...dummy>
    class min;

    template <typename M> requires (::tools::is_arithmetic_v<M>)
    class min<M> {
      using VR = ::std::conditional_t<::tools::is_arithmetic_v<M> && sizeof(M) <= sizeof(::std::size_t), const M, const M&>;

    public:
      using T = M;
      static T op(VR x, VR y) {
        return ::std::min(x, y);
      }
      static T e() {
        if constexpr (::tools::is_integral_v<M>) {
          return ::std::numeric_limits<M>::max();
        } else {
          return ::std::numeric_limits<M>::infinity();
        }
      }
    };

    template <typename M, M E>
    class min<M, E> {
      using VR = ::std::conditional_t<::tools::is_arithmetic_v<M> && sizeof(M) <= sizeof(::std::size_t), const M, const M&>;

    public:
      using T = M;
      static T op(VR x, VR y) {
        assert(x <= E);
        assert(y <= E);
        return ::std::min(x, y);
      }
      static T e() {
        return E;
      }
    };

    template <typename M>
    class multiplies {
      using VR = ::std::conditional_t<::tools::is_arithmetic_v<M> && sizeof(M) <= sizeof(::std::size_t), const M, const M&>;

    public:
      using T = M;
      static T op(VR x, VR y) {
        return x * y;
      }
      static T e() {
        return T(1);
      }
    };

    template <>
    struct multiplies<bool> {
      using T = bool;
      static T op(const bool x, const bool y) {
        return x && y;
      }
      static T e() {
        return true;
      }
    };

    template <typename M, M E>
    class update {
      using VR = ::std::conditional_t<::tools::is_arithmetic_v<M> && sizeof(M) <= sizeof(::std::size_t), const M, const M&>;

    public:
      using T = M;
      static T op(VR x, VR y) {
        return x == E ? y : x;
      }
      static T e() {
        return E;
      }
    };
  }
}


#line 1 "tools/square.hpp"



#line 1 "tools/is_monoid.hpp"



#line 6 "tools/is_monoid.hpp"

namespace tools {

  template <typename M, typename = void>
  struct is_monoid : ::std::false_type {};

  template <typename M>
  struct is_monoid<M, ::std::enable_if_t<
    ::std::is_same_v<typename M::T, decltype(M::op(::std::declval<typename M::T>(), ::std::declval<typename M::T>()))> &&
    ::std::is_same_v<typename M::T, decltype(M::e())>
  , void>> : ::std::true_type {};

  template <typename M>
  inline constexpr bool is_monoid_v = ::tools::is_monoid<M>::value;
}


#line 6 "tools/square.hpp"

namespace tools {

  template <typename M>
  ::std::enable_if_t<::tools::is_monoid_v<M>, typename M::T> square(const typename M::T& x) {
    return M::op(x, x);
  }

  template <typename T>
  ::std::enable_if_t<!::tools::is_monoid_v<T>, T> square(const T& x) {
    return x * x;
  }
}


#line 9 "tools/pow.hpp"

namespace tools {

  template <typename M, typename E>
  ::std::enable_if_t<::std::is_integral_v<E>, typename M::T> pow(const typename M::T& base, const E exponent) {
    assert(exponent >= 0);
    return exponent == 0
      ? M::e()
      : exponent % 2 == 0
        ? ::tools::square<M>(::tools::pow<M>(base, exponent / 2))
        : M::op(::tools::pow<M>(base, exponent - 1), base);
  }

  template <typename T, typename E>
  ::std::enable_if_t<::std::is_integral_v<E>, T> pow(const T& base, const E exponent) {
    assert(exponent >= 0);
    return ::tools::pow<::tools::monoid::multiplies<T>>(base, exponent);
  }

  template <typename T, typename E>
  auto pow(const T base, const E exponent) -> ::std::enable_if_t<!::std::is_integral_v<E>, decltype(::std::pow(base, exponent))> {
    return ::std::pow(base, exponent);
  }
}


#line 1 "tools/extgcd.hpp"



#line 1 "tools/abs.hpp"



namespace tools {
  constexpr float abs(const float x) {
    return x < 0 ? -x : x;
  }
  constexpr double abs(const double x) {
    return x < 0 ? -x : x;
  }
  constexpr long double abs(const long double x) {
    return x < 0 ? -x : x;
  }
  constexpr int abs(const int x) {
    return x < 0 ? -x : x;
  }
  constexpr long abs(const long x) {
    return x < 0 ? -x : x;
  }
  constexpr long long abs(const long long x) {
    return x < 0 ? -x : x;
  }
  constexpr unsigned int abs(const unsigned int x) noexcept {
    return x;
  }
  constexpr unsigned long abs(const unsigned long x) noexcept {
    return x;
  }
  constexpr unsigned long long abs(const unsigned long long x) noexcept {
    return x;
  }
}


#line 9 "tools/extgcd.hpp"

namespace tools {

  template <typename T>
  ::std::tuple<T, T, T> extgcd(T prev_r, T r) {
    const bool prev_r_is_neg = prev_r < T(0);
    const bool r_is_neg = r < T(0);

    if (prev_r_is_neg) prev_r = -prev_r;
    if (r_is_neg) r = -r;

    #ifndef NDEBUG
    const T a = prev_r;
    const T b = r;
    #endif

    T prev_s(1);
    T prev_t(0);
    T s(0);
    T t(1);
    while (r != T(0)) {
      const T q = prev_r / r;
      ::std::tie(prev_r, r) = ::std::make_pair(r, prev_r - q * r);
      ::std::tie(prev_s, s) = ::std::make_pair(s, prev_s - q * s);
      ::std::tie(prev_t, t) = ::std::make_pair(t, prev_t - q * t);
    }

    if (prev_r_is_neg) prev_s = -prev_s;
    if (r_is_neg) prev_t = -prev_t;

    assert(::tools::abs(prev_s) <= ::std::max(b / prev_r / T(2), T(1)));
    assert(::tools::abs(prev_t) <= ::std::max(a / prev_r / T(2), T(1)));
    return ::std::make_tuple(prev_s, prev_t, prev_r);
  }
}


#line 1 "tools/pow_mod_cache.hpp"



#line 5 "tools/pow_mod_cache.hpp"
#include <optional>
#line 1 "tools/find_cycle.hpp"



#line 5 "tools/find_cycle.hpp"

namespace tools {

  template <typename T, typename F>
  ::std::pair<long long, long long> find_cycle(const T& seed, const F& f) {
    auto i = 1LL;
    auto j = 2LL;
    T x = f(seed);
    T y = f(f(seed));
    for (; x != y; ++i, j += 2, x = f(x), y = f(f(y)));

    i = 0;
    x = seed;
    for (; x != y; ++i, ++j, x = f(x), y = f(y));

    const auto head = i;

    ++i;
    j = i + 1;
    x = f(x);
    y = f(f(y));
    for (; x != y; ++i, j += 2, x = f(x), y = f(f(y)));

    const auto cycle = j - i;

    return ::std::make_pair(head, cycle);
  }
}


#line 1 "tools/mod.hpp"



#line 7 "tools/mod.hpp"

namespace tools {

  template <typename M, typename N> requires (
    ::tools::is_integral_v<M> && !::std::is_same_v<::std::remove_cv_t<M>, bool> &&
    ::tools::is_integral_v<N> && !::std::is_same_v<::std::remove_cv_t<N>, bool>)
  constexpr ::std::common_type_t<M, N> mod(const M a, const N b) noexcept {
    assert(b != 0);

    using UM = ::std::make_unsigned_t<M>;
    using UN = ::std::make_unsigned_t<N>;
    const UM ua = a >= 0 ? a : static_cast<UM>(-(a + 1)) + 1;
    const UN ub = b >= 0 ? b : static_cast<UN>(-(b + 1)) + 1;
    auto r = ua % ub;
    if (a < 0 && r > 0) {
      r = ub - r;
    }
    return r;
  }
}


#line 1 "tools/floor.hpp"



#line 7 "tools/floor.hpp"

namespace tools {

  template <typename M, typename N> requires (
    ::tools::is_integral_v<M> && !::std::is_same_v<::std::remove_cv_t<M>, bool> &&
    ::tools::is_integral_v<N> && !::std::is_same_v<::std::remove_cv_t<N>, bool>)
  constexpr ::std::common_type_t<M, N> floor(const M x, const N y) noexcept {
    assert(y != 0);
    if (y >= 0) {
      if (x >= 0) {
        return x / y;
      } else {
        return (x + 1) / y - 1;
      }
    } else {
      if (x > 0) {
        return (x - 1) / y - 1;
      } else {
        return x / y;
      }
    }
  }
}


#line 1 "tools/ceil.hpp"



#line 1 "tools/is_unsigned.hpp"



#line 5 "tools/is_unsigned.hpp"

namespace tools {
  template <typename T>
  struct is_unsigned : ::std::is_unsigned<T> {};

  template <typename T>
  inline constexpr bool is_unsigned_v = ::tools::is_unsigned<T>::value;
}


#line 8 "tools/ceil.hpp"

namespace tools {
  template <typename M, typename N> requires (
    ::tools::is_integral_v<M> && !::std::is_same_v<::std::remove_cv_t<M>, bool> &&
    ::tools::is_integral_v<N> && !::std::is_same_v<::std::remove_cv_t<N>, bool>)
  constexpr ::std::common_type_t<M, N> ceil(const M x, const N y) noexcept {
    assert(y != 0);
    if (y >= 0) {
      if (x > 0) {
        return (x - 1) / y + 1;
      } else {
        if constexpr (::tools::is_unsigned_v<::std::common_type_t<M, N>>) {
          return 0;
        } else {
          return x / y;
        }
      }
    } else {
      if (x >= 0) {
        if constexpr (::tools::is_unsigned_v<::std::common_type_t<M, N>>) {
          return 0;
        } else {
          return x / y;
        }
      } else {
        return (x + 1) / y + 1;
      }
    }
  }
}


#line 16 "tools/pow_mod_cache.hpp"

namespace tools {

  template <class M>
  class pow_mod_cache {
    ::std::vector<M> m_pow;
    ::std::vector<M> m_cumsum;
    ::std::vector<M> m_inv_pow;
    ::std::vector<M> m_inv_cumsum;
    ::std::optional<::std::pair<long long, long long>> m_period;

  public:
    pow_mod_cache() = default;
    explicit pow_mod_cache(const M base) : m_pow({M(1), base}), m_cumsum({M::raw(0)}), m_inv_pow({M(1)}), m_inv_cumsum({M::raw(0)}) {
      if (base == M(-1)) {
        if (M::mod() > 2) {
          this->m_period = ::std::make_pair(0LL, 2LL);
        } else {
          this->m_period = ::std::make_pair(0LL, 1LL);
          this->m_pow.resize(1);
        }
        this->m_inv_pow.clear();
        this->m_inv_cumsum.clear();
      }
    }
    template <typename Z, ::std::enable_if_t<::std::is_integral_v<Z>, ::std::nullptr_t> = nullptr>
    explicit pow_mod_cache(const Z base) : pow_mod_cache(M(base)) {
    }

    M operator[](const long long n) {
      if (!this->m_period) {
        if (::std::max<long long>(::std::ssize(this->m_pow) - 1, n) - ::std::min<long long>(n, -(::std::ssize(this->m_inv_pow) - 1)) + 1 < M::mod() - 1) {
          if (n >= 0) {
            const long long size = ::std::ssize(this->m_pow);
            this->m_pow.resize(::std::max(size, n + 1));
            for (long long i = size; i < ::std::ssize(this->m_pow); ++i) {
              this->m_pow[i] = this->m_pow[i - 1] * this->m_pow[1];
            }
            return this->m_pow[n];
          } else {
            if (this->m_inv_pow.size() == 1) {
              this->m_inv_pow.push_back(this->m_pow[1].inv());
            }
            const long long size = ::std::ssize(this->m_inv_pow);
            this->m_inv_pow.resize(::std::max(size, -n + 1));
            for (long long i = size; i < ::std::ssize(this->m_inv_pow); ++i) {
              this->m_inv_pow[i] = this->m_inv_pow[i - 1] * this->m_inv_pow[1];
            }
            return this->m_inv_pow[-n];
          }
        }

        this->m_period = ::tools::find_cycle(this->m_pow[0], [&](const M& prev) { return prev * this->m_pow[1]; });
        const long long size = ::std::ssize(this->m_pow);
        this->m_pow.resize(this->m_period->first + this->m_period->second);
        for (long long i = size; i < ::std::ssize(this->m_pow); ++i) {
          this->m_pow[i] = this->m_pow[i - 1] * this->m_pow[1];
        }
        this->m_inv_pow.clear();
        this->m_inv_cumsum.clear();
      }

      if (this->m_period->first == 0) {
        return this->m_pow[::tools::mod(n, this->m_period->second)];
      } else {
        assert(n >= 0);
        if (n < this->m_period->first + this->m_period->second) {
          return this->m_pow[n];
        } else {
          return this->m_pow[(n - this->m_period->first) % this->m_period->second + this->m_period->first];
        }
      }
    }

    M sum(const long long l, const long long r) {
      if (l >= r) return M::raw(0);

      (*this)[r - 1];
      (*this)[l];

      {
        const long long size = ::std::ssize(this->m_cumsum);
        this->m_cumsum.resize(this->m_pow.size() + 1);
        for (long long i = size; i < ::std::ssize(this->m_cumsum); ++i) {
          this->m_cumsum[i] = this->m_cumsum[i - 1] + this->m_pow[i - 1];
        }
      }

      if (!this->m_period) {
        const long long size = ::std::ssize(this->m_inv_cumsum);
        this->m_inv_cumsum.resize(this->m_inv_pow.size() + 1);
        for (long long i = size; i < ::std::ssize(this->m_inv_cumsum); ++i) {
          this->m_inv_cumsum[i] = this->m_inv_cumsum[i - 1] + this->m_pow[i - 1];
        }

        if (l >= 0) {
          return this->m_cumsum[r] - this->m_cumsum[l];
        } else if (r <= 0) {
          return this->m_inv_cumsum[-l] - this->m_inv_cumsum[-r];
        } else {
          return (this->m_inv_cumsum[-l] - this->m_inv_cumsum[1]) + (this->m_cumsum[r] - this->m_cumsum[0]);
        }
      }

      static const auto cumsum = [&](const long long ll, const long long rr) {
        return this->m_cumsum[rr] - this->m_cumsum[ll];
      };

      if (l >= 0) {
        static const auto f = [&](const long long x) {
          if (x <= this->m_period->first + this->m_period->second) {
            return cumsum(0, x);
          } else {
            return cumsum(0, this->m_period->first) +
              cumsum(this->m_period->first, this->m_period->first + this->m_period->second) * ((x - this->m_period->first) / this->m_period->second) +
              cumsum(this->m_period->first, (x - this->m_period->first) % this->m_period->second + this->m_period->first);
          }
        };
        return f(r) - f(l);
      } else {
        const auto& n = this->m_period->second;
        return cumsum(::tools::mod(l, n), n) + cumsum(0, ::tools::mod(r, n)) + cumsum(0, n) * M(::tools::floor(r, n) - ::tools::ceil(l, n));
      }
    }
  };
}


#line 1 "tools/now.hpp"



#include <chrono>

namespace tools {
  inline long long now() {
    return ::std::chrono::duration_cast<::std::chrono::nanoseconds>(::std::chrono::high_resolution_clock::now().time_since_epoch()).count();
  }
}


#line 12 "tools/detail/rolling_hash.hpp"

namespace tools {
  class rolling_hash;

  class modint_for_rolling_hash {
  private:
    static constexpr ::std::uint64_t MASK30 = (::std::uint64_t(1) << 30) - 1;
    static constexpr ::std::uint64_t MASK31 = (::std::uint64_t(1) << 31) - 1;
    static constexpr ::std::uint64_t MOD = (::std::uint64_t(1) << 61) - 1;
    static constexpr ::std::uint64_t MASK61 = MOD;
    static constexpr ::std::uint64_t POSITIVIZER = MOD * 4;

    ::std::uint64_t m_val;

    modint_for_rolling_hash(const ::std::uint64_t x, int) : m_val(x) {
    }

    static ::std::uint64_t mul(const ::std::uint64_t a, const ::std::uint64_t b) {
      assert(a < MOD);
      assert(b < MOD);
      const ::std::uint64_t au = a >> 31;
      const ::std::uint64_t ad = a & MASK31;
      const ::std::uint64_t bu = b >> 31;
      const ::std::uint64_t bd = b & MASK31;
      const ::std::uint64_t mid = ad * bu + au * bd;
      const ::std::uint64_t midu = mid >> 30;
      const ::std::uint64_t midd = mid & MASK30;
      return au * bu * 2 + midu + (midd << 31) + ad * bd;
    }
    static ::std::uint64_t calc_mod(const ::std::uint64_t x) {
      const ::std::uint64_t xu = x >> 61;
      const ::std::uint64_t xd = x & MASK61;
      ::std::uint64_t res = xu + xd;
      if (res >= MOD) res -= MOD;
      return res;
    }

  public:
    modint_for_rolling_hash() = default;
    modint_for_rolling_hash(const ::tools::modint_for_rolling_hash&) = default;
    modint_for_rolling_hash(::tools::modint_for_rolling_hash&&) = default;
    ~modint_for_rolling_hash() = default;
    ::tools::modint_for_rolling_hash& operator=(const ::tools::modint_for_rolling_hash&) = default;
    ::tools::modint_for_rolling_hash& operator=(::tools::modint_for_rolling_hash&&) = default;

    explicit modint_for_rolling_hash(const ::std::uint64_t x) : m_val(calc_mod(x)) {
    }

    ::tools::modint_for_rolling_hash pow(const long long n) const {
      return ::tools::pow(*this, n);
    }
    ::tools::modint_for_rolling_hash inv() const {
      assert(this->m_val != 0);
      return ::tools::modint_for_rolling_hash(::std::get<0>(::tools::extgcd(this->m_val, MOD)));
    }

    ::tools::modint_for_rolling_hash operator+() const {
      return *this;
    }
    ::tools::modint_for_rolling_hash operator-() const {
      return ::tools::modint_for_rolling_hash(POSITIVIZER - this->m_val);
    }
    friend ::tools::modint_for_rolling_hash operator+(const ::tools::modint_for_rolling_hash& lhs, const ::tools::modint_for_rolling_hash& rhs) {
      return ::tools::modint_for_rolling_hash(lhs.m_val + rhs.m_val);
    }
    ::tools::modint_for_rolling_hash& operator+=(const ::tools::modint_for_rolling_hash& other) {
      this->m_val = calc_mod(this->m_val + other.m_val);
      return *this;
    }
    friend ::tools::modint_for_rolling_hash operator-(const ::tools::modint_for_rolling_hash& lhs, const ::tools::modint_for_rolling_hash& rhs) {
      return ::tools::modint_for_rolling_hash(lhs.m_val + POSITIVIZER - rhs.m_val);
    }
    ::tools::modint_for_rolling_hash& operator-=(const ::tools::modint_for_rolling_hash& other) {
      this->m_val = calc_mod(this->m_val + POSITIVIZER - other.m_val);
      return *this;
    }
    friend ::tools::modint_for_rolling_hash operator*(const ::tools::modint_for_rolling_hash& lhs, const ::tools::modint_for_rolling_hash& rhs) {
      return ::tools::modint_for_rolling_hash(mul(lhs.m_val, rhs.m_val));
    }
    ::tools::modint_for_rolling_hash& operator*=(const ::tools::modint_for_rolling_hash& other) {
      this->m_val = calc_mod(mul(this->m_val, other.m_val));
      return *this;
    }
    friend ::tools::modint_for_rolling_hash operator/(const ::tools::modint_for_rolling_hash& lhs, const ::tools::modint_for_rolling_hash& rhs) {
      return ::tools::modint_for_rolling_hash(mul(lhs.m_val, rhs.inv().m_val));
    }
    ::tools::modint_for_rolling_hash& operator/=(const ::tools::modint_for_rolling_hash& other) {
      this->m_val = calc_mod(mul(this->m_val, other.inv().m_val));
      return *this;
    }
    ::tools::modint_for_rolling_hash& operator++() {
      this->m_val = calc_mod(this->m_val + 1);
      return *this;
    }
    ::tools::modint_for_rolling_hash operator++(int) {
      const auto result = *this;
      ++(*this);
      return result;
    }
    ::tools::modint_for_rolling_hash& operator--() {
      this->m_val = calc_mod(this->m_val + POSITIVIZER - 1);
      return *this;
    }
    ::tools::modint_for_rolling_hash operator--(int) {
      const auto result = *this;
      --(*this);
      return result;
    }

    friend bool operator==(const ::tools::modint_for_rolling_hash& lhs, const ::tools::modint_for_rolling_hash& rhs) {
      return lhs.m_val == rhs.m_val;
    }
    friend bool operator!=(const ::tools::modint_for_rolling_hash& lhs, const ::tools::modint_for_rolling_hash& rhs) {
      return lhs.m_val != rhs.m_val;
    }

    long long val() const {
      return this->m_val;
    }

    static ::tools::modint_for_rolling_hash raw(const ::std::uint64_t x) {
      return ::tools::modint_for_rolling_hash(x, 0);
    }
    static long long mod() {
      return MOD;
    }

    friend ::tools::rolling_hash;
  };

  class rolling_hash {
  private:
    using mint = ::tools::modint_for_rolling_hash;
    inline static ::tools::pow_mod_cache<mint> m_pow_base = ::tools::pow_mod_cache<mint>(::tools::now());
    ::std::vector<mint> m_hash;

  public:
    rolling_hash() = default;
    rolling_hash(const ::tools::rolling_hash&) = default;
    rolling_hash(::tools::rolling_hash&&) = default;
    ~rolling_hash() = default;
    ::tools::rolling_hash& operator=(const ::tools::rolling_hash&) = default;
    ::tools::rolling_hash& operator=(::tools::rolling_hash&&) = default;

    template <typename InputIterator>
    rolling_hash(InputIterator begin, InputIterator end) {
      this->m_hash.push_back(mint::raw(0));
      const auto base = m_pow_base[1].m_val;
      for (auto it = begin; it != end; ++it) {
        this->m_hash.emplace_back(mint::mul(this->m_hash.back().m_val, base) + *it);
      }
      m_pow_base[this->m_hash.size()];
    }

    mint pow_base(const ::std::size_t i) const {
      return m_pow_base[i];
    }

    mint slice(const ::std::size_t l, const ::std::size_t r) const {
      assert(l <= r && r <= this->m_hash.size());
      return mint(this->m_hash[r].m_val + mint::POSITIVIZER - mint::mul(this->m_hash[l].m_val, m_pow_base[r - l].m_val));
    }
  };
}


#line 5 "tools/modint_for_rolling_hash.hpp"


#line 13 "tools/range_parallel_dsu.hpp"

namespace tools {
  class range_parallel_dsu {
    using mint = ::tools::modint_for_rolling_hash;
    struct monoid {
      inline static auto pow_b = ::tools::pow_mod_cache<mint>(::tools::now());
      using T = ::std::pair<int, mint>;
      static T op(const T& x, const T& y) {
        return {x.first + y.first, x.second * pow_b[y.first] + y.second};
      }
      static T e() {
        return {0, mint::raw(0)};
      }
    };

    ::atcoder::segtree<typename monoid::T, monoid::op, monoid::e> m_seg;
    ::std::vector<::std::vector<int>> m_groups;

  public:
    range_parallel_dsu() = default;
    explicit range_parallel_dsu(const int n) : m_seg([&]() {
      ::std::vector<typename monoid::T> v(n);
      for (int i = 0; i < n; ++i) {
        v[i] = {1, mint::raw(i + 1)};
      }
      return v;
    }()), m_groups(n) {
      for (int i = 0; i < n; ++i) {
        this->m_groups[i].push_back(i);
      }
    }

    int leader(const int x) const {
      assert(0 <= x && x < this->size());

      return this->m_seg.get(x).second.val() - 1;
    }

    bool same(const int x, const int y) const {
      assert(0 <= x && x < this->size());
      assert(0 <= y && y < this->size());

      return this->leader(x) == this->leader(y);
    }

    int merge(int x, int y) {
      assert(0 <= x && x < this->size());
      assert(0 <= y && y < this->size());

      x = this->leader(x);
      y = this->leader(y);
      if (x == y) return x;

      if (this->m_groups[x].size() < this->m_groups[y].size()) ::std::swap(x, y);
      ::std::ranges::copy(this->m_groups[y], ::std::back_inserter(this->m_groups[x]));
      for (const auto v : this->m_groups[y]) {
        this->m_seg.set(v, {1, mint::raw(x + 1)});
      }
      this->m_groups[y].clear();

      return x;
    }

    ::std::vector<::std::pair<int, int>> merge(int x, int y, const int k) {
      assert(k >= 0);
      assert(0 <= x && x + k <= this->size());
      assert(0 <= y && y + k <= this->size());

      ::std::vector<::std::pair<int, int>> res;
      int ok = 0;
      int ng = k + 1;
      do {
        while (ng - ok > 1) {
          const auto mid = (ok + ng) / 2;
          if (this->m_seg.prod(x, x + mid).second == this->m_seg.prod(y, y + mid).second) {
            ok = mid;
          } else {
            ng = mid;
          }
        }
        if (ok < k) {
          const auto leader_xor = this->leader(x + ok) ^ this->leader(y + ok);
          const auto new_leader = this->merge(x + ok, y + ok);
          res.emplace_back(new_leader, leader_xor ^ new_leader);
          ++ok;
          ng = k + 1;
        }
      } while (ok < k);

      return res;
    }

    int size() const {
      return this->m_groups.size();
    }

    int size(const int x) const {
      assert(0 <= x && x < this->size());

      return this->m_groups[this->leader(x)].size();
    }

    ::std::vector<::std::vector<int>> groups() const {
      ::std::vector<::std::vector<int>> res(this->size());
      for (int i = 0; i < this->size(); ++i) {
        res[this->leader(i)].push_back(i);
      }
      res.erase(::std::remove_if(res.begin(), res.end(), [](const auto& group) { return group.empty(); }), res.end());
      return res;
    }

    const ::std::vector<int>& group(const int x) const & {
      assert(0 <= x && x < this->size());

      return this->m_groups[this->leader(x)];
    }
    ::std::vector<int> group(const int x) && {
      assert(0 <= x && x < this->size());

      return ::std::move(this->m_groups[this->leader(x)]);
    }
  };
}


#line 9 "tests/range_parallel_dsu.test.cpp"

using mint = atcoder::modint998244353;

int main() {
  std::cin.tie(nullptr);
  std::ios_base::sync_with_stdio(false);

  int N, Q;
  std::cin >> N >> Q;
  std::vector<std::pair<mint, mint>> x(N);
  for (int i = 0; i < N; ++i) {
    int x_i;
    std::cin >> x_i;
    x[i] = {mint::raw(x_i), tools::square(mint::raw(x_i))};
  }

  const auto two_inv = mint::raw(2).inv();
  tools::range_parallel_dsu dsu(N);
  auto answer = mint::raw(0);
  for (int q = 0; q < Q; ++q) {
    int k, a, b;
    std::cin >> k >> a >> b;
    for (const auto& [r1, r2] : dsu.merge(a, b, k)) {
      answer -= (tools::square(x[r1].first) - x[r1].second) * two_inv;
      answer -= (tools::square(x[r2].first) - x[r2].second) * two_inv;
      x[r1].first += x[r2].first;
      x[r1].second += x[r2].second;
      x[r2] = {mint::raw(0), mint::raw(0)};
      answer += (tools::square(x[r1].first) - x[r1].second) * two_inv;
    }
    std::cout << answer.val() << '\n';
  }

  return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	decr_period_00	AC	8233 ms	71 MB
g++	decr_period_01	AC	8785 ms	74 MB
g++	decr_period_02	AC	8646 ms	73 MB
g++	decr_period_03	AC	8402 ms	75 MB
g++	example_00	AC	5 ms	4 MB
g++	example_01	AC	4 ms	4 MB
g++	large_k_00	AC	9163 ms	64 MB
g++	large_k_01	AC	8859 ms	63 MB
g++	large_k_02	AC	9081 ms	65 MB
g++	periodic_00	AC	8254 ms	73 MB
g++	periodic_01	AC	8247 ms	72 MB
g++	periodic_02	AC	8340 ms	67 MB
g++	periodic_03	AC	8059 ms	66 MB
g++	random_00	AC	7503 ms	65 MB
g++	random_01	AC	7642 ms	65 MB
g++	random_02	AC	3432 ms	11 MB
g++	small_00	AC	98 ms	4 MB
g++	small_01	AC	121 ms	4 MB
g++	small_02	AC	125 ms	4 MB
g++	small_03	AC	131 ms	4 MB
g++	small_04	AC	136 ms	4 MB
g++	small_05	AC	149 ms	4 MB
g++	small_06	AC	158 ms	4 MB
g++	small_07	AC	156 ms	4 MB
g++	small_08	AC	164 ms	4 MB
g++	small_09	AC	173 ms	4 MB
g++	small_k_00	AC	1265 ms	58 MB
g++	small_k_01	AC	1261 ms	58 MB
g++	small_k_02	AC	1257 ms	58 MB

Back to top page