#938615 (C++17) No.2588 Increasing Record

提出ソース
結果

問題	No.2588 Increasing Record
ユーザー	tonegawa
提出日時	2023-12-16 03:18:08
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	WA
実行時間	-
コード長	44,937 bytes
コンパイル時間	2,152 ms
コンパイル使用メモリ	160,740 KB
実行使用メモリ	50,508 KB
最終ジャッジ日時	2024-09-27 07:21:45
合計ジャッジ時間	16,081 ms
ジャッジサーバーID （参考情報）	judge2 / judge1
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,816 KB
testcase_01	AC	2 ms 6,940 KB
testcase_02	AC	2 ms 6,940 KB
testcase_03	AC	2 ms 6,944 KB
testcase_04	AC	2 ms 6,940 KB
testcase_05	AC	2 ms 6,944 KB
testcase_06	AC	2 ms 6,944 KB
testcase_07	AC	2 ms 6,940 KB
testcase_08	WA	-
testcase_09	WA	-
testcase_10	WA	-
testcase_11	WA	-
testcase_12	AC	47 ms 6,944 KB
testcase_13	AC	46 ms 6,944 KB
testcase_14	WA	-
testcase_15	WA	-
testcase_16	WA	-
testcase_17	WA	-
testcase_18	WA	-
testcase_19	WA	-
testcase_20	WA	-
testcase_21	WA	-
testcase_22	WA	-
testcase_23	WA	-
testcase_24	WA	-
testcase_25	WA	-
testcase_26	WA	-
testcase_27	WA	-
testcase_28	WA	-
testcase_29	WA	-
testcase_30	AC	397 ms 26,948 KB
testcase_31	AC	541 ms 37,968 KB
testcase_32	AC	638 ms 48,188 KB
testcase_33	AC	663 ms 50,196 KB
testcase_34	AC	667 ms 50,508 KB
testcase_35	AC	670 ms 50,508 KB
testcase_36	AC	685 ms 50,508 KB
testcase_37	WA	-
testcase_38	WA	-
testcase_39	WA	-
testcase_40	WA	-
testcase_41	WA	-
testcase_42	WA	-
testcase_43	AC	215 ms 45,184 KB
testcase_44	WA	-
testcase_45	WA	-
testcase_46	WA	-
権限があれば一括ダウンロードができます
ソースコード

raw source code

#include <iostream>
#include <string>
#include <vector>
#include <array>
#include <tuple>
#include <stack>
#include <queue>
#include <deque>
#include <algorithm>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <cmath>
#include <functional>
#include <cassert>
#include <climits>
#include <iomanip>
#include <numeric>
#include <memory>
#include <random>
#include <thread>
#include <chrono>
#define allof(obj) (obj).begin(), (obj).end()
#define range(i, l, r) for(int i=l;i<r;i++)
#define unique_elem(obj) obj.erase(std::unique(allof(obj)), obj.end())
#define bit_subset(i, S) for(int i=S, zero_cnt=0;(zero_cnt+=i==S)<2;i=(i-1)&S)
#define bit_kpop(i, n, k) for(int i=(1<<k)-1,x_bit,y_bit;i<(1<<n);x_bit=(i&-i),y_bit=i+x_bit,i=(!i?(1<<n):((i&~y_bit)/x_bit>>1)|y_bit))
#define bit_kth(i, k) ((i >> k)&1)
#define bit_highest(i) (i?63-__builtin_clzll(i):-1)
#define bit_lowest(i) (i?__builtin_ctzll(i):-1)
#define sleepms(t) std::this_thread::sleep_for(std::chrono::milliseconds(t))
using ll = long long;
using ld = long double;
using ul = uint64_t;
using pi = std::pair<int, int>;
using pl = std::pair<ll, ll>;
using namespace std;

template<typename F, typename S>
std::ostream &operator<<(std::ostream &dest, const std::pair<F, S> &p){
  dest << p.first << ' ' << p.second;
  return dest;
}
template<typename T>
std::ostream &operator<<(std::ostream &dest, const std::vector<std::vector<T>> &v){
  int sz = v.size();
  if(sz==0) return dest;
  for(int i=0;i<sz;i++){
    int m = v[i].size();
    for(int j=0;j<m;j++) dest << v[i][j] << (i!=sz-1&&j==m-1?'\n':' ');
  }
  return dest;
}
template<typename T>
std::ostream &operator<<(std::ostream &dest, const std::vector<T> &v){
  int sz = v.size();
  if(sz==0) return dest;
  for(int i=0;i<sz-1;i++) dest << v[i] << ' ';
  dest << v[sz-1];
  return dest;
}
template<typename T, size_t sz>
std::ostream &operator<<(std::ostream &dest, const std::array<T, sz> &v){
  if(sz==0) return dest;
  for(int i=0;i<sz-1;i++) dest << v[i] << ' ';
  dest << v[sz-1];
  return dest;
}
template<typename T>
std::ostream &operator<<(std::ostream &dest, const std::set<T> &v){
  for(auto itr=v.begin();itr!=v.end();){
    dest << *itr;
    itr++;
    if(itr!=v.end()) dest << ' ';
  }
  return dest;
}
template<typename T, typename E>
std::ostream &operator<<(std::ostream &dest, const std::map<T, E> &v){
  for(auto itr=v.begin();itr!=v.end();){
    dest << '(' << itr->first << ", " << itr->second << ')';
    itr++;
    if(itr!=v.end()) dest << '\n';
  }
  return dest;
}
std::ostream &operator<<(std::ostream &dest, __int128_t value) {
  std::ostream::sentry s(dest);
  if (s) {
    __uint128_t tmp = value < 0 ? -value : value;
    char buffer[128];
    char *d = std::end(buffer);
    do {
      --d;
      *d = "0123456789"[tmp % 10];
      tmp /= 10;
    } while (tmp != 0);
    if (value < 0) {
      --d;
      *d = '-';
    }
    int len = std::end(buffer) - d;
    if (dest.rdbuf()->sputn(d, len) != len) {
      dest.setstate(std::ios_base::badbit);
    }
  }
  return dest;
}
template<typename T>
vector<T> make_vec(size_t sz, T val){return std::vector<T>(sz, val);}
template<typename T, typename... Tail>
auto make_vec(size_t sz, Tail ...tail){
  return std::vector<decltype(make_vec<T>(tail...))>(sz, make_vec<T>(tail...));
}
template<typename T>
vector<T> read_vec(size_t sz){
  std::vector<T> v(sz);
  for(int i=0;i<(int)sz;i++) std::cin >> v[i];
  return v;
}
template<typename T, typename... Tail>
auto read_vec(size_t sz, Tail ...tail){
  auto v = std::vector<decltype(read_vec<T>(tail...))>(sz);
  for(int i=0;i<(int)sz;i++) v[i] = read_vec<T>(tail...);
  return v;
}
long long max(long long a, int b){return std::max(a, (long long)b);}
long long max(int a, long long b){return std::max((long long)a, b);}
long long min(long long a, int b){return std::min(a, (long long)b);}
long long min(int a, long long b){return std::min((long long)a, b);}
long long modulo(long long a, long long m){a %= m; return a < 0 ? a + m : a;}

void io_init(){
  std::cin.tie(nullptr);
  std::ios::sync_with_stdio(false);
}








#include <limits>

struct point_min_range_min{
  template<typename T>
  static T id(){
    return std::numeric_limits<T>::max();
  }
  template<typename T>
  static T update(T a, T b){
    return std::min(a, b);
  }
  template<typename T>
  static T merge(T a, T b){
    return std::min(a, b);
  }
};
struct point_min_range_second_min{
  template<typename T>
  static T id(){
    return {std::numeric_limits<long long>::max(), std::numeric_limits<long long>::max()};
  }
  template<typename T>
  static T update(T a, T b){
    if(a.first <= b.first) return {a.first, std::min(a.second, b.first)};
    else return {b.first, std::min(a.first, b.second)};
  }
  template<typename T>
  static T merge(T a, T b){
    if(a.first <= b.first) return {a.first, std::min(a.second, b.first)};
    else return {b.first, std::min(a.first, b.second)};
  }
};
struct point_max_range_max{
  template<typename T>
  static T id(){
    return std::numeric_limits<T>::min();
  }
  template<typename T>
  static T update(T a, T b){
    return std::max(a, b);
  }
  template<typename T>
  static T merge(T a, T b){
    return std::max(a, b);
  }
  template<typename T>
  static T flip(T a){
    return a;
  }
};
struct point_max_range_second_max{
  template<typename T>
  static T id(){
    return {std::numeric_limits<long long>::min(), std::numeric_limits<long long>::min()};
  }
  template<typename T>
  static T update(T a, T b){
    if(a.first >= b.first) return {a.first, std::min(a.second, b.first)};
    else return {b.first, std::min(a.first, b.second)};
  }
  template<typename T>
  static T merge(T a, T b){
    if(a.first >= b.first) return {a.first, std::min(a.second, b.first)};
    else return {b.first, std::min(a.first, b.second)};
  }
};
struct point_mul_range_mul{
  template<typename T>
  static T id(){
    return 1;
  }
  template<typename T>
  static T update(T a, T b){
    return a * b;
  }
  template<typename T>
  static T merge(T a, T b){
    return a * b;
  }
};
struct point_add_range_min{
  template<typename T>
  static T id(){
    return std::numeric_limits<T>::max();
  }
  template<typename T>
  static T update(T a, T b){
    if(a == id<T>()) return b;
    else if(b == id<T>()) return a;
    return a + b;
  }
  template<typename T>
  static T merge(T a, T b){
    return std::min(a, b);
  }
};

struct point_add_range_max{
  template<typename T>
  static T id(){
    return std::numeric_limits<T>::min();
  }
  template<typename T>
  static T update(T a, T b){
    if(a == id<T>()) return b;
    else if(b == id<T>()) return a;
    return a + b;
  }
  template<typename T>
  static T merge(T a, T b){
    return std::max(a, b);
  }
};

struct point_add_range_sum{
  template<typename T>
  static T id(){
    return 0;
  }
  template<typename T>
  static T update(T a, T b){
    return a + b;
  }
  template<typename T>
  static T merge(T a, T b){
    return a + b;
  }
  template<typename T>
  static T flip(T a){
    return a;
  }
};
struct point_set_range_composite{
  static constexpr int mod = 998244353;
  template<typename T>
  static T id(){
    return {1, 0};
  }
  template<typename T>
  static T update(T a, T b){
    return b;
  }
  template<typename T>
  static T merge(T a, T b){
    int xy = ((long long)a.first * b.first) % mod;
    int ab = ((long long)a.second * b.first + b.second) % mod;
    return {xy, ab};
  }
};
struct excess_value{
  int rank, sum, minl, maxr;
  excess_value(){}
  excess_value(bool f): rank(f), sum(f ? 1 : -1), minl(sum), maxr(sum){}
  excess_value(int a, int b, int c, int d): rank(a), sum(b), minl(c), maxr(d){}
};
struct point_set_range_excess_value{
  const static int inf = std::numeric_limits<int>::max() / 2;
  template<typename T>
  static T id(){
    // '('を1, ')'を　-1としたときの{1の数, 和, 左を固定したsumのmin, 右を固定したsumのmin}
    return {inf, 0, 0, 0};
  }
  template<typename T>
  static T update(T a, T b){
    if(a.rank == inf) return b;
    if(b.rank == inf) return a;
    return {a.rank + b.rank, a.sum + b.sum, std::min(a.minl, a.sum + b.minl), std::max(b.maxr, a.maxr + b.sum)};
  }
  template<typename T>
  static T merge(T a, T b){
    if(a.rank == inf) return b;
    if(b.rank == inf) return a;
    return {a.rank + b.rank, a.sum + b.sum, std::min(a.minl, a.sum + b.minl), std::max(b.maxr, a.maxr + b.sum)};
  }
};
struct point_set_range_composite_flip{
  static constexpr int mod = 998244353;
  template<typename T>
  static T id(){
    return {1, 0, 0};
  }
  template<typename T>
  static T update(T a, T b){
    return b;
  }
  template<typename T>
  static T flip(T a){
    return {a[0], a[2], a[1]};
  }
  template<typename T>
  static T merge(T a, T b){
    int xy = ((long long)a[0] * b[0]) % mod;
    int ab = ((long long)a[1] * b[0] + b[1]) % mod;
    int ba = ((long long)b[2] * a[0] + a[2]) % mod;
    return {xy, ab, ba};
  }
};
// merge(a, b) = max(0, a + b)の場合, {x, 0}で初期化
struct hawker{
  static constexpr long long minf = std::numeric_limits<long long>::min() / 2;
  template<typename T>
  static T id(){
    return {0, minf};
  }
  template<typename T>
  static T update(T a, T b){
    return {a.first + b.first, std::max(a.second + b.first, b.second)};
  }
  template<typename T>
  static T merge(T a, T b){
    return {a.first + b.first, std::max(a.second + b.first, b.second)};
  }
};

struct point_add_range_gcd{
  template<typename Val>
  static Val __binary_gcd(Val a, Val b){
    if(!a || !b) return !a ? b : a;
    if(a < 0) a *= -1;
    if(b < 0) b *= -1;
    int shift = __builtin_ctzll(a | b); // [1] gcd(2a', 2b') = 2 * gcd(a', b')
    a >>= __builtin_ctzll(a);
    do{
      // if b is odd
      // gcd(2a', b) = gcd(a', b), if a = 2a'(a is even)
      // gcd(a, b) = gcd(|a - b|, min(a, b)), if a is odd
      b >>= __builtin_ctzll(b); // make b odd
      if(a > b) std::swap(a, b);
      b -= a;
    }while(b); // gcd(a, 0) = a
    return a << shift; // [1]
  }
  template<typename Val>
  static Val id(){
    return 0;
  }
  template<typename Val>
  static Val update(Val a, Val b){
    return a + b;
  }
  template<typename Val>
  static Val merge(Val a, Val b){
    return __binary_gcd(a, b);
  }
};
// 区間set, これまでにsetした物の中ならどれかを取得
struct range_set_get_any{
  template<typename Val>
  static Val id1(){
    return nullptr;
  }
  template<typename Lazy>
  static Lazy id2(){
    return nullptr;
  }
  template<typename Lazy>
  static Lazy propagate(Lazy l, Lazy x){
    return (x == nullptr ? l : x);
  }
  template<typename Val, typename Lazy>
  static Val apply(Val v, Lazy x, int l, int r){
    return (x == nullptr ? v : x);
  }
};

struct range_add_range_sum{
  template<typename T>
  static T id1(){
    return T(0);
  }
  template<typename E>
  static E id2(){
    return E(0);
  }
  template<typename T>
  static T merge(T a, T b){
    return a + b;
  }
  template<typename T, typename E>
  static T apply(T a, E b, int l, int r){
    return a + b * (r - l);
  }
  template<typename E>
  static E propagate(E a, E b){
    return a + b;
  }
  template<typename T>
  static T flip(T a){
    return a;
  }
};

struct range_min_range_min{
  template<typename T>
  static T id1(){
    return std::numeric_limits<T>::max();
  }
  template<typename E>
  static E id2(){
    return std::numeric_limits<E>::max();
  }
  template<typename T>
  static T merge(T a, T b){
    return std::min(a, b);
  }
  template<typename T, typename E>
  static T apply(T a, E b, int l, int r){
    return std::min(a, b);
  }
  template<typename E>
  static E propagate(E a, E b){
    return std::min(a, b);
  }
};
struct range_max_range_max{
  template<typename T>
  static T id1(){
    return std::numeric_limits<T>::min();
  }
  template<typename E>
  static E id2(){
    return std::numeric_limits<E>::min();
  }
  template<typename T>
  static T merge(T a, T b){
    return std::max(a, b);
  }
  template<typename T, typename E>
  static T apply(T a, E b, int l, int r){
    return std::max(a, b);
  }
  template<typename E>
  static E propagate(E a, E b){
    return std::max(a, b);
  }
};

struct range_set_range_min{
  template<typename T>
  static T id1(){
    return std::numeric_limits<T>::max();
  }
  template<typename E>
  static E id2(){
    return std::numeric_limits<E>::max();
  }
  template<typename T>
  static T merge(T a, T b){
    return std::min(a, b);
  }
  template<typename T, typename E>
  static T apply(T a, E b, int l, int r){
    return b;
  }
  template<typename E>
  static E propagate(E a, E b){
    return b;
  }
};
struct range_set_range_sum{
  template<typename T>
  static T id1(){
    return 0;
  }
  template<typename E>
  static E id2(){
    return std::numeric_limits<E>::max();
  }
  template<typename T>
  static T merge(T a, T b){
    return a + b;
  }
  template<typename T, typename E>
  static T apply(T a, E b, int l, int r){
    return b * (r - l);
  }
  template<typename E>
  static E propagate(E a, E b){
    return b;
  }
};
struct range_add_range_max{
  template<typename T>
  static T id1(){
    return std::numeric_limits<T>::min();
  }
  template<typename E>
  static E id2(){
    return 0;
  }
  template<typename T>
  static T merge(T a, T b){
    return std::max(a, b);
  }
  template<typename T, typename E>
  static T apply(T a, E b, int l, int r){
    if(a == id1<T>()) return b;
    return a + b;
  }
  template<typename E>
  static E propagate(E a, E b){
    return a + b;
  }
};

struct range_add_range_min{
  template<typename T>
  static T id1(){
    return std::numeric_limits<T>::max() / 2;
  }
  template<typename E>
  static E id2(){
    return 0;
  }
  template<typename T>
  static T merge(T a, T b){
    return std::min(a, b);
  }
  template<typename T, typename E>
  static T apply(T a, E b, int l, int r){
    if(a == id1<T>()) return b;
    return a + b;
  }
  template<typename E>
  static E propagate(E a, E b){
    return a + b;
  }
};

struct range_add_range_argmin{
  template<typename T>
  static T id1(){
    return {std::numeric_limits<long long>::max(), -1} ;
  }
  template<typename E>
  static E id2(){
    return 0;
  }
  template<typename T>
  static T merge(T a, T b){
    return std::min(a, b);
  }
  template<typename T, typename E>
  static T apply(T a, E b, int l, int r){
    if(a == id1<T>()) return a;
    return {a.first + b, a.second};
  }
  template<typename E>
  static E propagate(E a, E b){
    return a + b;
  }
};

/*
#include <array>
struct range_affine_range_sum{
  const static long long MOD = 998244353;
  template<typename T>
  static T id1(){
    return 0;
  }
  template<typename E>
  static E id2(){
    return E{1, 0};
  }
  template<typename T>
  static T merge(T a, T b){
    return (a + b) % MOD;
  }
  template<typename T, typename E>
  static T apply(T a, E b, int l, int r){
    return (a * b[0] + b[1] * (r - l)) % MOD;
  }
  template<typename E>
  static E propagate(E a, E b){
    return E{(a[0] * b[0]) % MOD, (a[1] * b[0] + b[1]) % MOD};
  }
};
*/
struct range_affine_range_sum{
  const static int MOD = 998244353;
  template<typename T>
  static T id1(){
    return 0;
  }
  template<typename E>
  static E id2(){
    return E{1, 0};
  }
  template<typename T>
  static T merge(T a, T b){
    return (a + b) % MOD;
  }
  template<typename T, typename E>
  static T apply(T a, E b, int l, int r){
    return ((long long)a * b.first + (long long)b.second * (r - l)) % MOD;
  }
  template<typename E>
  static E propagate(E a, E b){
    return E{((long long)a.first * b.first) % MOD, ((long long)a.second * b.first + b.second) % MOD};
  }
};

struct range_add_range_min_count{
  static constexpr int INF = std::numeric_limits<int>::max();
  template<typename T>
  static T id1(){
    return {INF, 0};
  }
  template<typename E>
  static E id2(){
    return 0;
  }
  template<typename T>
  static T merge(T a, T b){
    if(a.first != b.first) return a.first < b.first ? a : b;
    return {a.first, a.second + b.second};
  }
  template<typename T, typename E>
  static T apply(T a, E b, int l, int r){
    if(a.first == INF) return {b, r - l};
    return {a.first + b, a.second};
  }
  template<typename E>
  static E propagate(E a, E b){
    return a + b;
  }
};

struct range_composite_lct{
  static constexpr int MOD = 998244353;
  template<typename T>
  // 1x + 0, 1x + 0
  static T id1(){
    return std::array<int, 3>{1, 0, 0};
  }
  // no use
  template<typename E>
  static E id2(){
    return false;
  }
  // b(a(x)), a(b(x))
  template<typename T>
  static T merge(T a, T b){
    int ba1 = ((long long)b[0] * a[0]) % MOD;
    int ba2 = ((long long)b[0] * a[1] + b[1]) % MOD;
    int ab2 = ((long long)a[0] * b[2] + a[2]) % MOD;
    return std::array<int, 3>{ba1, ba2, ab2};
  }
  // no use
  template<typename T, typename E>
  static T apply(T a, E b, int l, int r){
    return a;
  }
  // no use
  template<typename E>
  static E propagate(E a, E b){
    return false;
  }
  //
  template<typename T>
  static T flip(T a){
    return std::array<int, 3>{a[0], a[2], a[1]};
  }
};


template<typename monoid, typename Val>
struct red_black_tree_monoid{
  struct node{
    node *l, *r, *p;
    bool red;
    int ra, sz;
    Val val;
    // 葉
    node(Val val): l(nullptr), r(nullptr), p(nullptr), red(false), ra(0), sz(1), val(val){}
    // 中間ノード
    node(node *l, node *r, bool red): l(l), r(r), p(nullptr), red(red), ra(l->ra + !(l->red)), sz(l->sz + r->sz){
      l->p = r->p = this;
      val = monoid::template merge<Val>(l->val, r->val);
    }
  };
  static std::vector<node*> stock;
  static node *reuse(node *a, node *l, node *r, bool red){
    a->l = l, a->r = r, a->p = nullptr, a->red = red;
    l->p = r->p = a;
    a->ra = l->ra + !(l->red);
    a->sz = l->sz + r->sz;
    a->val = monoid::template merge<Val>(a->l->val, a->r->val);
    return a;
  }
  node *root;
  using pn = std::pair<node*, node*>;
  static node *merge_sub(node *a, node *b){
    if(a->ra < b->ra){
      node *c = merge_sub(a, b->l);
      if(!b->red && c->red && c->l->red){
        if(!b->r->red){
          return reuse(c, c->l, reuse(b, c->r, b->r, 1), 0);
        }else{
          b->r->red = 0;
          c->red = 0;
          return reuse(b, c, b->r, 1);
        }
      }else{
        return reuse(b, c, b->r, b->red);
      }
    }else if(a->ra > b->ra){
      node *c = merge_sub(a->r, b);
      if(!a->red && c->red && c->r->red){
        if(!a->l->red){
          return reuse(c, reuse(a, a->l, c->l, 1), c->r, 0);
        }else{
          a->l->red = 0;
          c->red = 0;
          return reuse(a, a->l, c, 1);
        }
      }else{
        return reuse(a, a->l, c, a->red);
      }
    }else{
      if(stock.empty()) return new node(a, b, 1);
      node *u = stock.back();
      stock.pop_back();
      return reuse(u, a, b, 1);
    }
  }
  static node *merge(node *a, node *b){
    if(!a || !b) return !a ? b : a;
    node *c = merge_sub(a, b);
    c->red = 0;
    return c;
  }
  static node *as_root(node *a){
    if(!a) return nullptr;
    a->red = 0;
    return a;
  }
  static pn split(node *a, int k){
    int sz = a->sz, szl = (a->l ? a->l->sz : 0);
    if(k == 0 || k == sz) return (!k ? pn{nullptr, a} : pn{a, nullptr});
    pn res;
    if(k < szl){
      auto [l, r] = split(a->l, k);
      res = pn{l, merge(r, as_root(a->r))};
    }else if(k > szl){
      auto [l, r] = split(a->r, k - szl);
      res = pn{merge(as_root(a->l), l), r};
    }else{
      res = pn{as_root(a->l), as_root(a->r)};
    }
    if(a) stock.push_back(a);
    return res;
  }
  void set(node *a, int k, Val x){
    if(!a->l && !a->r){
      assert(k == 0);
      a->val = x;
      return;
    }
    int szl = a->l ? a->l->sz : 0;
    if(k < szl) set(a->l, k, x);
    else set(a->r, k - szl, x);
    a->val = monoid::template merge<Val>(a->l->val, a->r->val);
  }
  Val get(node *a, int k){
    if(!a->l && !a->r){
      assert(k == 0);
      return a->val;
    }
    int szl = a->l ? a->l->sz : 0;
    if(k < szl) return get(a->l, k);
    else return get(a->r, k - szl);
  }
  static Val query(node *a, int l, int r){
    if(!a || l >= r || a->sz <= l || r <= 0) return monoid::template id<Val>();
    if(l <= 0 && a->sz <= r) return a->val;
    if(!a->l && !a->r) return a->val;
    int szl = a->l->sz;
    if(r <= szl) return query(a->l, l, r);
    if(szl <= l) return query(a->r, l - szl, r - szl);
    return monoid::template merge<Val>(query(a->l, l, szl), query(a->r, 0, r - szl));
  }
  node *build(const std::vector<Val> &v, int l, int r){
    if(l == r) return nullptr;
    if(r - l == 1) return new node(v[l]);
    int mid = (l + r) / 2;
    node *L = build(v, l, mid);
    node *R = build(v, mid, r);
    return merge(L, R);
  }
  red_black_tree_monoid(node *a): root(a){}
  red_black_tree_monoid(): root(nullptr){}
  red_black_tree_monoid(const std::vector<Val> &v): root(build(v, 0, v.size())){}

  int size()const{
    return root ? root->sz : 0;
  }
  void set(int k, Val x){
    assert(k < size());
    set(root, k, x);
  }
  Val get(int k){
    assert(k < size());
    return get(root, k);
  }
  // k番目にxを挿入
  void insert(int k, Val x){
    auto [a, b] = split(root, k);
    root = merge(a, merge(new node(x), b));
  }
  void erase(int k){
    assert(root->sz > k);
    auto [a, b] = split(root, k);
    assert(b);
    auto [b2, c] = split(b, 1);
    root = merge(a, c);
    if(b2) stock.push_back(b2);
  }
  Val query(int l, int r)const{
    assert(0 <= l && r <= size());
    return query(root, l, r);
  }
  Val query_all(){
    return !root ? monoid::template id1<Val>() : root->val;
  }
  using rbtm = red_black_tree_monoid<monoid, Val>;
  std::pair<rbtm, rbtm> split(int k){
    return split(*this, k);
  }
  // 2つに分割. 永続でないためこれ自身のaのrootはnullptrになる
  static std::pair<rbtm, rbtm> split(rbtm &a, int k){
    assert(k <= a.size());
    auto [l, r] = split(a.root, k);
    a.root = nullptr;
    return {rbtm(l), rbtm(r)};
  }
  // a, bをマージ. 永続でないためa, bのrootはnullptrになる
  static rbtm merge(rbtm &a, rbtm &b){
    rbtm res(merge(a.root, b.root));
    a.root = b.root = nullptr;
    return res;
  }
};
template<typename monoid, typename Val>
std::vector<typename red_black_tree_monoid<monoid, Val>::node*> red_black_tree_monoid<monoid, Val>::stock;

template<typename monoid, typename Val, typename Lazy>
struct lazy_red_black_tree_monoid{
  struct node{
    node *l, *r, *p;
    bool red;
    int ra, sz;
    Val val;
    Lazy lazy;
    // 葉
    node(Val val): l(nullptr), r(nullptr), p(nullptr), red(false), ra(0), sz(1), val(val), lazy(monoid::template id2<Lazy>()){}
    // 中間ノード
    node(node *l, node *r, bool red): l(l), r(r), p(nullptr), red(red), ra(l->ra + !(l->red)), sz(l->sz + r->sz), lazy(monoid::template id2<Lazy>()){
      l->p = r->p = this;
      val = monoid::template merge<Val>(l->val, r->val);
    }
  };
  static std::vector<node*> stock;
  static node *reuse(node *a, node *l, node *r, bool red){
    a->l = l, a->r = r, a->p = nullptr, a->red = red;
    l->p = r->p = a;
    a->ra = l->ra + !(l->red);
    a->sz = l->sz + r->sz;
    a->val = monoid::template merge<Val>(a->l->val, a->r->val);
    a->lazy = monoid::template id2<Lazy>();
    return a;
  }
  static void propagate(node *a, Lazy x){
    a->val = monoid::template apply<Val, Lazy>(a->val, x, 0, a->sz);
    a->lazy = monoid::template propagate<Lazy>(a->lazy, x);
  }
  static void push_down(node *a){
    if(a->lazy == monoid::template id2<Lazy>()) return;
    if(a->l) propagate(a->l, a->lazy);
    if(a->r) propagate(a->r, a->lazy);
    a->lazy = monoid::template id2<Lazy>();
  }
  node *root;
  using pn = std::pair<node*, node*>;
  static node *merge_sub(node *a, node *b){
    if(a->ra < b->ra){
      push_down(b);
      node *c = merge_sub(a, b->l);
      if(!b->red && c->red && c->l->red){
        if(!b->r->red){
          return reuse(c, c->l, reuse(b, c->r, b->r, 1), 0);
        }else{
          b->r->red = 0;
          c->red = 0;
          return reuse(b, c, b->r, 1);
        }
      }else{
        return reuse(b, c, b->r, b->red);
      }
    }else if(a->ra > b->ra){
      push_down(a);
      node *c = merge_sub(a->r, b);
      if(!a->red && c->red && c->r->red){
        if(!a->l->red){
          return reuse(c, reuse(a, a->l, c->l, 1), c->r, 0);
        }else{
          a->l->red = 0;
          c->red = 0;
          return reuse(a, a->l, c, 1);
        }
      }else{
        return reuse(a, a->l, c, a->red);
      }
    }else{
      if(stock.empty()) return new node(a, b, 1);
      node *u = stock.back();
      stock.pop_back();
      return reuse(u, a, b, 1);
    }
  }
  static node *merge(node *a, node *b){
    if(!a || !b) return !a ? b : a;
    node *c = merge_sub(a, b);
    c->red = 0;
    return c;
  }
  static node *as_root(node *a){
    if(!a) return nullptr;
    a->red = 0;
    return a;
  }
  static pn split(node *a, int k){
    int sz = a->sz, szl = (a->l ? a->l->sz : 0);
    if(k == 0 || k == sz) return (!k ? pn{nullptr, a} : pn{a, nullptr});
    pn res;
    push_down(a);
    if(k < szl){
      auto [l, r] = split(a->l, k);
      res = pn{l, merge(r, as_root(a->r))};
    }else if(k > szl){
      auto [l, r] = split(a->r, k - szl);
      res = pn{merge(as_root(a->l), l), r};
    }else{
      res = pn{as_root(a->l), as_root(a->r)};
    }
    if(a) stock.push_back(a);
    return res;
  }
  void set(node *a, int k, Val x){
    if(!a->l && !a->r){
      assert(k == 0);
      a->val = x;
      return;
    }
    push_down(a);
    int szl = a->l ? a->l->sz : 0;
    if(k < szl) set(a->l, k, x);
    else set(a->r, k - szl, x);
    a->val = monoid::template merge<Val>(a->l->val, a->r->val);
  }
  Val get(node *a, int k){
    if(!a->l && !a->r){
      assert(k == 0);
      return a->val;
    }
    push_down(a);
    int szl = a->l ? a->l->sz : 0;
    if(k < szl) return get(a->l, k);
    else return get(a->r, k - szl);
  }
  static void update(node *a, int l, int r, Lazy x){
    if(!a || l >= r || a->sz <= l || r <= 0) return;
    if(l <= 0 && a->sz <= r){
      propagate(a, x);
      return;
    }
    if(!a->l && !a->r){
      a->val = monoid::template apply<Val, Lazy>(a->val, x, 0, 1);
      return;
    }
    push_down(a);
    int szl = a->l->sz;
    update(a->l, l, r, x);
    update(a->r, l - szl, r - szl, x);
    a->val = monoid::template merge<Val>(a->l->val, a->r->val);
  }
  static Val query(node *a, int l, int r){
    if(!a || l >= r || a->sz <= l || r <= 0) return monoid::template id1<Val>();
    if(l <= 0 && a->sz <= r) return a->val;
    if(!a->l && !a->r) return a->val;
    push_down(a);
    int szl = a->l->sz;
    if(r <= szl) return query(a->l, l, r);
    if(szl <= l) return query(a->r, l - szl, r - szl);
    return monoid::template merge<Val>(query(a->l, l, szl), query(a->r, 0, r - szl));
  }
  node *build(const std::vector<Val> &v, int l, int r){
    if(l == r) return nullptr;
    if(r - l == 1) return new node(v[l]);
    int mid = (l + r) / 2;
    node *L = build(v, l, mid);
    node *R = build(v, mid, r);
    return merge(L, R);
  }
  lazy_red_black_tree_monoid(node *a): root(a){}
  lazy_red_black_tree_monoid(): root(nullptr){}
  lazy_red_black_tree_monoid(const std::vector<Val> &v): root(build(v, 0, v.size())){}

  int size()const{
    return root ? root->sz : 0;
  }
  void set(int k, Val x){
    assert(k < size());
    set(root, k, x);
  }
  Val get(int k){
    assert(k < size());
    return get(root, k);
  }
  // k番目にxを挿入
  void insert(int k, Val x){
    auto [a, b] = split(root, k);
    root = merge(a, merge(new node(x), b));
  }
  void erase(int k){
    assert(root->sz > k);
    auto [a, b] = split(root, k);
    assert(b);
    auto [b2, c] = split(b, 1);
    root = merge(a, c);
    if(b2) stock.push_back(b2);
  }
  void update(int l, int r, Lazy x){
    assert(0 <= l && r <= size());
    return update(root, l, r, x);
  }
  Val query(int l, int r)const{
    assert(0 <= l && r <= size());
    return query(root, l, r);
  }
  void update_all(Lazy x){
    if(root) propagate(root, x);
  }
  Val query_all(){
    return !root ? monoid::template id1<Val>() : root->val;
  }
  using rbtm = lazy_red_black_tree_monoid<monoid, Val, Lazy>;
  std::pair<rbtm, rbtm> split(int k){
    return split(*this, k);
  }
  // 2つに分割. 永続でないためこれ自身のaのrootはnullptrになる
  static std::pair<rbtm, rbtm> split(rbtm &a, int k){
    assert(k <= a.size());
    auto [l, r] = split(a.root, k);
    a.root = nullptr;
    return {rbtm(l), rbtm(r)};
  }
  rbtm merge(rbtm &b){
    rbtm res = merge(*this, b);
    root = b.root = nullptr;
    return res;
  }
  // a, bをマージ. 永続でないためa, bのrootはnullptrになる
  static rbtm merge(rbtm &a, rbtm &b){
    rbtm res(merge(a.root, b.root));
    a.root = b.root = nullptr;
    return res;
  }
};
template<typename monoid, typename Val, typename Lazy>
std::vector<typename lazy_red_black_tree_monoid<monoid, Val, Lazy>::node*> lazy_red_black_tree_monoid<monoid, Val, Lazy>::stock;

template<typename monoid, typename Val>
struct union_find_monoid{
private:
  using rbt = red_black_tree_monoid<monoid, Val>;
  using node = typename rbt::node;
  std::vector<node*> V;
  std::unordered_map<node*, int> rev;
  node *__find(int a){
    node *v = V[a];
    while(v->p) v = v->p;
    return v;
  }
public:
  union_find_monoid(int n): V(n){
    for(int i = 0; i < n; i++){
      V[i] = new node(monoid::template id<Val>());
      rev.emplace(V[i], i);
    }
  }
  union_find_monoid(const std::vector<Val> &val): V(val.size()){
    for(int i = 0; i < val.size(); i++){
      V[i] = new node(val[i]);
      rev.emplace(V[i], i);
    }
  }
  void unite(int a, int b){
    node *u = __find(a);
    node *v = __find(b);
    if(u == v) return;
    rbt::merge(u, v);
  }
  // 通常のunion-find木ではunite(a, b)後の根はaの根, bの根のうちサイズがあ大きい方であるが, このfindはそのルールを守らない
  // 同じ木の状態で同じ連結成分の要素から呼ばれると同じ値[0, n)を返すことのみ保証される
  int find(int a){
    node *v = V[a];
    while(v->p) v = v->p;
    while(v->l) v = v->l;
    return rev[v];
  }
  bool same(int a, int b){
    return __find(a) == __find(b);
  }
  int size(int a){
    return __find(a)->sz;
  }
  Val query(int a){
    return __find(a)->val;
  }
  Val get(int a){
    return V[a]->val;    
  }
  void set(int a, Val x){
    node *v = V[a];
    v->val = x;
    while(v->p){
      v = v->p;
      v->val = monoid::template merge<Val>(v->l->val, v->r->val);
    }
  }
  std::vector<int> enumerate(int a){
    std::vector<int> res;
    node *v = V[a];
    while(v->p) v = v->p;
    std::queue<node*> q;
    q.push(v);
    while(!q.empty()){
      v = q.front();
      q.pop();
      if(v->l){
        q.push(v->l);
        q.push(v->r);
      }else{
        res.push_back(rev[v]);
      }
    }
    return res;
  }
};
template<typename monoid, typename Val, typename Lazy>
struct lazy_union_find_monoid{
private:
  using rbt = lazy_red_black_tree_monoid<monoid, Val, Lazy>;
  using node = typename rbt::node;
  std::vector<node*> V;
  std::unordered_map<node*, int> rev;
  node *__find(int a){
    node *v = V[a];
    while(v->p) v = v->p;
    return v;
  }
public:
  lazy_union_find_monoid(int n): V(n){
    for(int i = 0; i < n; i++){
      V[i] = new node(monoid::template id1<Val>());
      rev.emplace(V[i], i);
    }
  }
  lazy_union_find_monoid(const std::vector<Val> &val): V(val.size()){
    for(int i = 0; i < val.size(); i++){
      V[i] = new node(val[i]);
      rev.emplace(V[i], i);
    }
  }
  void unite(int a, int b){
    node *u = __find(a);
    node *v = __find(b);
    if(u == v) return;
    rbt::merge(u, v);
  }
  // 通常のunion-find木ではunite(a, b)後の根はaの根, bの根のうちサイズがあ大きい方であるが, このfindはそのルールを守らない
  // 同じ木の状態で同じ連結成分の要素から呼ばれると同じ値[0, n)を返すことのみ保証される
  int find(int a){
    node *v = V[a];
    while(v->p) v = v->p;
    while(v->l) v = v->l;
    return rev[v];
  }
  bool same(int a, int b){
    return __find(a) == __find(b);
  }
  int size(int a){
    return __find(a)->sz;
  }
  void update(int a, Lazy x){
    node *v = __find(a);
    rbt::propagate(v, x);
  }
  Val query(int a){
    return __find(a)->val;
  }
  Val get(int a){
    std::vector<node*> path;
    node *v = V[a];
    while(v->p){
      v = v->p;
      path.push_back(v);
    }
    int m = path.size();
    for(int i = m - 1; i >= 0; i--) rbt::push_down(path[i]);
    return V[a]->val;
  }
  void set(int a, Val x){
    std::vector<node*> path;
    node *v = V[a];
    while(v->p){
      v = v->p;
      path.push_back(v);
    }
    int m = path.size();
    for(int i = m - 1; i >= 0; i--) rbt::push_down(path[i]);
    V[a]->val = x;
    for(int i = 0; i < m; i++) path[i]->val = monoid::template merge<Val>(path[i]->l->val, path[i]->r->val);
  }
  std::vector<int> enumerate(int a){
    std::vector<int> res;
    node *v = V[a];
    while(v->p) v = v->p;
    std::queue<node*> q;
    q.push(v);
    while(!q.empty()){
      v = q.front();
      q.pop();
      if(v->l){
        q.push(v->l);
        q.push(v->r);
      }else{
        res.push_back(rev[v]);
      }
    }
    return res;
  }
};



#include <type_traits>
#include <ostream>


// @param m `1 <= m`
constexpr long long safe_mod(long long x, long long m){
  x %= m;
  if (x < 0) x += m;
  return x;
}
struct barrett{
  unsigned int _m;
  unsigned long long im;
  explicit barrett(unsigned int m) : _m(m), im((unsigned long long)(-1) / m + 1){}
  unsigned int umod()const{return _m;}
  unsigned int mul(unsigned int a, unsigned int b)const{
    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`
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;
}
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);

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);

int ceil_pow2(int n){
  int x = 0;
  while ((1U << x) < (unsigned int)(n)) x++;
  return x;
}
int bsf(unsigned int n){
  return __builtin_ctz(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};
  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;
    auto tmp = s;
    s = t;
    t = tmp;
    tmp = m0;
    m0 = m1;
    m1 = tmp;
  }
  if(m0 < 0) m0 += b / s;
  return {s, m0};
}



template<int m>
long long modpow(long long a, long long b){
  assert(0 <= b);
  assert(0 < m);
  a = safe_mod(a, m);
  long long ret = 1;
  while(b){
    if(b & 1) ret = (ret * a) % m;
    a = (a * a) % m;
    b >>= 1;
  }
  return ret;
}
// @param 0 <= b, 0 < m
long long modpow(long long a, long long b, int m){
  assert(0 <= b);
  assert(0 < m);
  a = safe_mod(a, m);
  long long ret = 1;
  while(b){
    if(b & 1) ret = (ret * a) % m;
    a = (a * a) % m;
    b >>= 1;
  }
  return ret;
}

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

template <int m, std::enable_if_t<(1 <= m)>* = nullptr>
struct static_modint : 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>
  static_modint(T v){
    long long x = v % (long long)umod();
    if (x < 0) x += umod();
    _v = x;
  }
  unsigned 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 = 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 = is_prime<m>;
};

template<int id> 
struct dynamic_modint : modint_base{
  using mint = dynamic_modint;
public:
  static int mod(){return (int)(bt.umod());}
  static void set_mod(int m){
    assert(1 <= m);
    bt = barrett(m);
  }
  static mint raw(int v){
    mint x;
    x._v = v;
    return x;
  }
  dynamic_modint(): _v(0){}
  template <class T>
  dynamic_modint(T v){
    long long x = v % (long long)(mod());
    if (x < 0) x += mod();
    _v = x;
  }
  unsigned 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 = 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 barrett bt;
  static unsigned int umod(){return bt.umod();}
};
template <int id>
barrett dynamic_modint<id>::bt(998244353);
using modint = dynamic_modint<-1>;

using modint998244353 = static_modint<998244353>;
using modint1000000007 = static_modint<1000000007>;
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>;
template <class T>
using is_static_modint = std::is_base_of<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>;
template<int m>
std::ostream &operator<<(std::ostream &dest, const static_modint<m> &a){
  dest << a.val();
  return dest;
}
template<int id>
std::ostream &operator<<(std::ostream &dest, const dynamic_modint<id> &a){
  dest << a.val();
  return dest;
}

// 0 <= n < m <= int_max
// 前処理 O(n + log(m))
// 各種計算 O(1)
// 変数 <= n
template<typename mint, is_modint<mint>* = nullptr>
struct modcomb{
private:
  int n;
  std::vector<mint> f, i, fi;
  void init(int _n){
    assert(0 <= _n && _n < mint::mod());
    if(_n < f.size()) return;
    n = _n;
    f.resize(n + 1), i.resize(n + 1), fi.resize(n + 1);
    f[0] = fi[0] = mint(1);
    if(n) f[1] = fi[1] = i[1] = mint(1);
    for(int j = 2; j <= n; j++) f[j] = f[j - 1] * j;
    fi[n] = f[n].inv();
    for(int j = n; j >= 2; j--){
      fi[j - 1] = fi[j] * j;
      i[j] = f[j - 1] * fi[j];
    }
  }
public:
  modcomb(): n(-1){}
  modcomb(int _n){
    init(_n);
  }
  void recalc(int _n){
    init(std::min(mint::mod() - 1, 1 << ceil_pow2(_n)));
  }
  mint comb(int a, int b){
    if((a < 0) || (b < 0) || (a < b)) return 0;
    return f[a] * fi[a - b] * fi[b];
  }
  mint combinv(int a, int b){
    assert(0 <= b && b <= a);
    return fi[a] * f[a - b] * f[b];
  }
  mint perm(int a, int b){
    if((a < 0) || (b < 0) || (a < b)) return 0;
    return f[a] * fi[a - b];
  }
  mint perminv(int a, int b){
    assert(0 <= b && b <= a);
    return fi[a] * f[a - b];
  }
  mint fac(int x){
    assert(0 <= x && x <= n);
    return f[x];
  }
  mint inv(int x){
    assert(0 < x && x <= n);
    return i[x];
  }
  mint finv(int x){
    assert(0 <= x && x <= n);
    return fi[x];
  }
};
template<typename mint, is_modint<mint>* = nullptr>
struct modpow_table{
  std::vector<mint> v;
  // x^maxkまで計算できる
  modpow_table(){}
  void init(int x, int maxk){
    v.resize(maxk + 1);
    v[0] = 1;
    for(int i = 1; i <= maxk; i++) v[i] = v[i - 1] * x;
  }
  mint pow(int k){
    assert(0 <= k && k < v.size());
    return v[k];
  }
};


using mint = modint998244353;
int main(){
  io_init();
  int n, m;
  std::cin >> n >> m;
  vector<vector<int>> g(n);
  range(i, 0, m){
    int a, b;
    std::cin >> a >> b;
    a--, b--;
    if(a < b) swap(a, b);
    g[a].push_back(b);
  }
  vector<mint> tmp(n, 1);
  lazy_union_find_monoid<range_add_range_sum, mint, mint> uf(tmp);

  mint ans = 0;
  range(i, 0, n){
    mint s = 0;
    sort(allof(g[i]));
    //reverse(allof(g[i]));
    for(int t : g[i]){
      if(!uf.same(i, t)) s += uf.get(t);
      uf.unite(i, t);
    }
    ans += s + 1;
    uf.update(i, s + 1);
    uf.set(i, s + 1);
  }
  std::cout << ans << '\n';
}
yukicoder

結果

テストケース

ソースコード
