#992096 (C++17(gcc12)) No.3524 二進範囲更新範囲和取得

提出ソース
結果

問題	No.3524 二進範囲更新範囲和取得
コンテスト
ユーザー	👑 p-adic
提出日時	2024-06-30 08:54:51
言語	C++17(gcc12) (gcc 12.4.0 + boost 1.89.0) コンパイル: `g++-12 -O2 -lm -std=c++17 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_` 実行: `./a.out`
結果	AC
実行時間	282 ms / 2,000 ms
コード長	48,758 bytes
記録記録タグの例: 初AC ショートコード純ショートコード純主流ショートコード最速実行時間
コンパイル時間	5,487 ms
コンパイル使用メモリ	278,456 KB
実行使用メモリ	46,880 KB
平均クエリ数	1167.69
最終ジャッジ日時	2026-05-01 20:51:06
合計ジャッジ時間	14,393 ms
ジャッジサーバーID （参考情報）	judge3_1 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン	結果
other	AC * 45
権限があれば一括ダウンロードができます
ソースコード

raw source code
#ifndef INCLUDE_MODE
  #define INCLUDE_MODE
  #define REACTIVE
  // #define USE_GETLINE
#endif

#ifdef INCLUDE_MAIN

inline void Solve()
{
  // 入力の受け取り。
  CEXPR( int , bound_N , 15e5 ); CIN_ASSERT( N , 1 , bound_N );
  CEXPR( int , bound_B , 1e2 ); CIN_ASSERT( B , 1 , bound_B );
  CEXPR( int , bound_Q , 15e2 ); CIN_ASSERT( Q , 1 , bound_Q );

  // 二分木をHL分解（二分木の定義から、indexの小さいnodeがheaviest）。
  vector<int> dfs{ 1 } , HL_inv( N+1 );
  int length = 0;
  while( !dfs.empty() ){
    int temp = dfs.back();
    dfs.pop_back();
    if( temp <= N ){
      HL_inv[temp] = length++;
      dfs.push_back( temp << 1 | 1 );
      dfs.push_back( temp << 1 );
    }
  }
  
  // 二分木の各ノードの部分木に対応する区間の右端の計算。
  vector<int> R( N + 1 );
  FOREQINV( i , N , 1 ){
    int temp = i << 1;
    R[i] = temp <= N ? temp < N ? R[temp | 1] : R[temp] : HL_inv[i];
  }

  // mod Bの整数型。Derepresent()で構築し、Represent()で代表の整数値を取り出す。
  using mint = DynamicMod;
  mint::SetModulo( B );

  // HL分解後の配列をmod Bで計算。
  vector<mint> A( N );
  FOREQ( i , 1 , N ){
    ++( A[HL_inv[i]] = A[HL_inv[i-1]] );
  }

  // 写像のモノイド。
  using Func = vector<mint>;
  auto composition = [&]( const Func& f0 , const Func& f1 ){
    if( f0.empty() ){
      return f1;
    } else if( f1.empty() ){
      return f0;
    }
    auto answer = f0;
    FOR( j , 0 , B ){
      answer[j] = f0[f1[j].Represent()];
    }
    return answer;
  };
  AbstractMonoid F{ composition , Func() };

  // 写像の値への作用。
  auto application = [&]( const Func& f , const mint& n ){
    return f[n.Represent()];
  };
  AbstractRSet X{ Func() , mint() , application };
  
  // 写像の頻度表への作用。
  using Hind = vector<int>;
  auto action = [&]( const Func& f , const Hind& h ){
    if( f.empty() ){
      return h;
    }
    vector answer( B , 0 );
    FOR( j , 0 , B ){
      answer[f[j].Represent()] += h[j];
    }
    return answer;
  };
  
  // 頻度表の和倍。
  auto add = [&]( Hind h0 , const Hind& h1 ){
    FOR( j , 0 , B ){
      h0[j] += h1[j];
    }
    return move( h0 );
  };
  AbstractMonoid H{ add , Hind( B ) };
  // 頻度表のスカラー倍。
  auto scalar_product = [&]( Hind h , const int& n ){
    return n * move( h );
  };
  AbstractBiModule M{ Func() , 0 , action , scalar_product , H };
  
  // １つの値を頻度表に加算。
  auto trans = [&]( Hind h , const mint& n , const int& c ){
    h[n.Represent()] += c;
    return move( h );
  };

  // 写像の値への作用を遅延評価して頻度表を計算する平方分割。
  int bucket = SqrtDecompositionCoordinate::Sqrt( B * N );
  EquivariantLazySqrtDecomposition lsd{ F , X , M , trans , move( A ) , bucket };
  CEXPR( ll , bound_d , 1e18 );
  REPEAT( Q ){
    // クエリの受け取り。
    CIN_ASSERT( i , 1 , N );
    CIN_ASSERT( d , 0 , bound_d );
    // 作用する写像を構成。
    Func f( B );
    FOR( j , 0 , B ){
      ++( f[j] = Power( mint::Derepresent( j ) , d ) );
    }
    // 作用の遅延評価。
    lsd.IntervalAct( HL_inv[i] , R[i] , f );
    // 頻度表の区間和の計算。
    Hind h = lsd.IntervalProduct( HL_inv[i] , R[i] );
    // 区間和の計算。
    mint answer{};
    FOR( j , 0 , B ){
      answer += h[j] * j;
    }
    // 区間和の出力。
    COUT( answer );
  }
}
REPEAT_MAIN(1);

#else // INCLUDE_MAIN

#ifdef INCLUDE_LIBRARY

// https://github.com/p-adic/cpp
// VVV ライブラリは以下に挿入する。

// 圧縮用
#define TE template
#define TY typename
#define US using
#define ST static
#define AS assert
#define IN inline
#define CL class
#define PU public
#define OP operator
#define CE constexpr
#define CO const
#define NE noexcept
#define RE return 
#define WH while
#define VO void
#define VE vector
#define LI list
#define BE begin
#define EN end
#define SZ size
#define LE length
#define PW Power
#define MO move
#define TH this
#define CRI CO int&
#define CRUI CO uint&
#define CRL CO ll&
#define VI virtual 
#define IS basic_istream<char,Traits>
#define OS basic_ostream<char,Traits>
#define ST_AS static_assert
#define reMO_CO remove_const
#define is_COructible_v is_constructible_v
#define rBE rbegin
#define reSZ resize

#define DF_OF_AR_FOR_VE(V,OPR)TE <TY T> IN V<T>& OP OPR ## =(V<T>& a,CO T& t){for(auto& s:a){s OPR ## = t;}RE a;}TE <TY T> IN V<T>& OP OPR ## =(V<T>& a0,CO V<T>& a1){AS(a0.SZ()<= a1.SZ());auto IT0 = a0.BE(),EN0 = a0.EN();auto IT1 = a1.BE();WH(IT0 != EN0){*(IT0++)OPR ## = *(IT1++);}RE a0;}TE <TY T,TY U> IN V<T> OP OPR(V<T> a,CO U& u){RE MO(a OPR ## = u);}
#define DF_OF_INCREMENT_FOR_VE(V,INCR)TE <TY T> IN V<T>& OP INCR(V<T>& a){for(auto& i:a){INCR i;}RE a;}
#define DF_OF_ARS_FOR_VE(V)DF_OF_AR_FOR_VE(V,+);DF_OF_AR_FOR_VE(V,-);DF_OF_AR_FOR_VE(V,*);DF_OF_AR_FOR_VE(V,/);DF_OF_AR_FOR_VE(V,%);DF_OF_INCREMENT_FOR_VE(V,++);DF_OF_INCREMENT_FOR_VE(V,--);TE <TY T> IN V<T> OP*(CO T& scalar,V<T> v){for(auto& t:v){v *= t;}RE MO(v);}
DF_OF_ARS_FOR_VE(VE);

#define DC_OF_CPOINT(POINT)IN CO U& POINT()CO NE
#define DC_OF_POINT(POINT)IN U& POINT()NE
#define DF_OF_CPOINT(POINT)TE <TY U> IN CO U& VirtualPointedSet<U>::POINT()CO NE{RE Point();}
#define DF_OF_POINT(POINT)TE <TY U> IN U& VirtualPointedSet<U>::POINT()NE{RE Point();}
TE <TY U>CL UnderlyingSet{PU:US type = U;};TE <TY U>CL VirtualPointedSet:VI PU UnderlyingSet<U>{PU:VI CO U& Point()CO NE = 0;VI U& Point()NE = 0;DC_OF_CPOINT(Unit);DC_OF_CPOINT(Zero);DC_OF_CPOINT(One);DC_OF_CPOINT(Infty);DC_OF_POINT(init);DC_OF_POINT(root);};TE <TY U>CL PointedSet:VI PU VirtualPointedSet<U>{PU:U m_b_U;IN PointedSet(U b_u = U());IN CO U& Point()CO NE;IN U& Point()NE;};TE <TY U>CL VirtualNSet:VI PU UnderlyingSet<U>{PU:VI U Transfer(CO U& u)= 0;IN U Inverse(CO U& u);};TE <TY U,TY F_U>CL AbstractNSet:VI PU VirtualNSet<U>{PU:F_U m_f_U;IN AbstractNSet(F_U f_U);IN AbstractNSet<U,F_U>& OP=(CO AbstractNSet&)NE;IN U Transfer(CO U& u);};TE <TY U>CL VirtualMagma:VI PU UnderlyingSet<U>{PU:VI U Product(U u0,CO U& u1)= 0;IN U Sum(U u0,CO U& u1);};TE <TY U = ll>CL AdditiveMagma:VI PU VirtualMagma<U>{PU:IN U Product(U u0,CO U& u1);};TE <TY U = ll>CL MultiplicativeMagma:VI PU VirtualMagma<U>{PU:IN U Product(U u0,CO U& u1);};TE <TY U,TY M_U>CL AbstractMagma:VI PU VirtualMagma<U>{PU:M_U m_m_U;IN AbstractMagma(M_U m_U);IN AbstractMagma<U,M_U>& OP=(CO AbstractMagma<U,M_U>&)NE;IN U Product(U u0,CO U& u1);};
TE <TY U> IN PointedSet<U>::PointedSet(U b_U):m_b_U(MO(b_U)){}TE <TY U> IN CO U& PointedSet<U>::Point()CO NE{RE m_b_U;}TE <TY U> IN U& PointedSet<U>::Point()NE{RE m_b_U;}DF_OF_CPOINT(Unit);DF_OF_CPOINT(Zero);DF_OF_CPOINT(One);DF_OF_CPOINT(Infty);DF_OF_POINT(init);DF_OF_POINT(root);TE <TY U,TY F_U> IN AbstractNSet<U,F_U>::AbstractNSet(F_U f_U):m_f_U(MO(f_U)){ST_AS(is_invocable_r_v<U,F_U,U>);}TE <TY U,TY F_U> IN AbstractNSet<U,F_U>& AbstractNSet<U,F_U>::operator=(CO AbstractNSet<U,F_U>&)NE{RE *TH;}TE <TY U,TY F_U> IN U AbstractNSet<U,F_U>::Transfer(CO U& u){RE m_f_U(u);}TE <TY U> IN U VirtualNSet<U>::Inverse(CO U& u){RE Transfer(u);}TE <TY U,TY M_U> IN AbstractMagma<U,M_U>::AbstractMagma(M_U m_U):m_m_U(MO(m_U)){ST_AS(is_invocable_r_v<U,M_U,U,U>);}TE <TY U,TY M_U> IN AbstractMagma<U,M_U>& AbstractMagma<U,M_U>::OP=(CO AbstractMagma<U,M_U>&)NE{RE *TH;}TE <TY U> IN U AdditiveMagma<U>::Product(U u0,CO U& u1){RE MO(u0 += u1);}TE <TY U> IN U MultiplicativeMagma<U>::Product(U u0,CO U& u1){RE MO(u0 *= u1);}TE <TY U,TY M_U> IN U AbstractMagma<U,M_U>::Product(U u0,CO U& u1){RE m_m_U(MO(u0),u1);}TE <TY U> IN U VirtualMagma<U>::Sum(U u0,CO U& u1){RE Product(MO(u0),u1);}

TE <TY U>CL VirtualMonoid:VI PU VirtualMagma<U>,VI PU VirtualPointedSet<U>{};TE <TY U = ll>CL AdditiveMonoid:VI PU VirtualMonoid<U>,PU AdditiveMagma<U>,PU PointedSet<U>{};TE <TY U = ll>CL MultiplicativeMonoid:VI PU VirtualMonoid<U>,PU MultiplicativeMagma<U>,PU PointedSet<U>{PU:IN MultiplicativeMonoid(U e_U);};TE <TY U,TY M_U>CL AbstractMonoid:VI PU VirtualMonoid<U>,PU AbstractMagma<U,M_U>,PU PointedSet<U>{PU:IN AbstractMonoid(M_U m_U,U e_U);};
TE <TY U> IN MultiplicativeMonoid<U>::MultiplicativeMonoid(U e_U):PointedSet<U>(MO(e_U)){}TE <TY U,TY M_U> IN AbstractMonoid<U,M_U>::AbstractMonoid(M_U m_U,U e_U):AbstractMagma<U,M_U>(MO(m_U)),PointedSet<U>(MO(e_U)){}

TE <TY U>CL VirtualGroup:VI PU VirtualMonoid<U>,VI PU VirtualPointedSet<U>,VI PU VirtualNSet<U>{};TE <TY U = ll>CL AdditiveGroup:VI PU VirtualGroup<U>,PU AdditiveMonoid<U>{PU:IN U Transfer(CO U& u);};TE <TY U,TY M_U,TY I_U>CL AbstractGroup:VI PU VirtualGroup<U>,PU AbstractMonoid<U,M_U>,PU AbstractNSet<U,I_U>{PU:IN AbstractGroup(M_U m_U,U e_U,I_U i_U);};
TE <TY U,TY M_U,TY I_U> IN AbstractGroup<U,M_U,I_U>::AbstractGroup(M_U m_U,U e_U,I_U i_U):AbstractMonoid<U,M_U>(MO(m_U),MO(e_U)),AbstractNSet<U,I_U>(MO(i_U)){}TE <TY U> IN U AdditiveGroup<U>::Transfer(CO U& u){RE -u;}

TE <TY R,TY U>CL VirtualRSet:VI PU UnderlyingSet<U>{PU:VI U Action(CO R& r,U u)= 0;IN U PW(U u,CO R& r);IN U ScalarProduct(CO R& r,U u);};TE <TY U,TY MAGMA>CL RegularRSet:VI PU VirtualRSet<U,U>,PU MAGMA{PU:IN RegularRSet(MAGMA magma);IN U Action(CO U& r,U u);};TE <TY MAGMA> RegularRSet(MAGMA magma)-> RegularRSet<inner_t<MAGMA>,MAGMA>;TE <TY R,TY U,TY O_U>CL AbstractRSet:VI PU VirtualRSet<R,U>{PU:O_U m_o_U;IN AbstractRSet(CO R& dummy0,CO U& dummy1,O_U o_U);IN AbstractRSet<R,U,O_U>& OP=(CO AbstractRSet<R,U,O_U>&)NE;IN U Action(CO R& r,U u);};TE <TY R,TY U,TY O_U,TY GROUP>CL AbstractModule:PU AbstractRSet<R,U,O_U>,PU GROUP{PU:IN AbstractModule(CO R& dummy,O_U o_U,GROUP M);};TE <TY R,TY O_U,TY GROUP> AbstractModule(CO R& dummy,O_U o_U,GROUP M)-> AbstractModule<R,inner_t<GROUP>,O_U,GROUP>;TE <TY R,TY U>CL Module:VI PU VirtualRSet<R,U>,PU AdditiveGroup<U>{PU:IN U Action(CO R& r,U u);};
TE <TY R,TY MAGMA> IN RegularRSet<R,MAGMA>::RegularRSet(MAGMA magma):MAGMA(MO(magma)){}TE <TY R,TY U,TY O_U> IN AbstractRSet<R,U,O_U>::AbstractRSet(CO R& dummy0,CO U& dummy1,O_U o_U):m_o_U(MO(o_U)){ST_AS(is_invocable_r_v<U,O_U,R,U>);}TE <TY R,TY U,TY O_U,TY GROUP> IN AbstractModule<R,U,O_U,GROUP>::AbstractModule(CO R& dummy,O_U o_U,GROUP M):AbstractRSet<R,U,O_U>(dummy,M.One(),MO(o_U)),GROUP(MO(M)){ST_AS(is_same_v<U,inner_t<GROUP>>);}TE <TY R,TY U,TY O_U> IN AbstractRSet<R,U,O_U>& AbstractRSet<R,U,O_U>::OP=(CO AbstractRSet<R,U,O_U>&)NE{RE *TH;}TE <TY U,TY MAGMA> IN U RegularRSet<U,MAGMA>::Action(CO U& r,U u){RE TH->Product(r,MO(u));}TE <TY R,TY U,TY O_U> IN U AbstractRSet<R,U,O_U>::Action(CO R& r,U u){RE m_o_U(r,MO(u));}TE <TY R,TY U> IN U Module<R,U>::Action(CO R& r,U u){RE MO(u *= r);}TE <TY R,TY U> IN U VirtualRSet<R,U>::PW(U u,CO R& r){RE Action(r,MO(u));}TE <TY R,TY U> IN U VirtualRSet<R,U>::ScalarProduct(CO R& r,U u){RE Action(r,MO(u));}

TE <TY L,TY R,TY U>CL VirtualBiModule:VI PU UnderlyingSet<U>{PU:VI U LAction(CO L& l,U u)= 0;VI U RAction(U u,CO R& r)= 0;IN U ScalarProduct(CO L& l,U u);IN U PW(U u,CO R& r);};TE <TY L,TY R,TY U,TY O_U_L,TY O_U_R,TY GROUP>CL AbstractBiModule:PU VirtualBiModule<L,R,U>,PU GROUP{PU:O_U_L m_o_U_L;O_U_R m_o_U_R;IN AbstractBiModule(CO L& dummy_l,CO R& dummy_r,O_U_L o_U_L,O_U_R o_U_R,GROUP M);IN AbstractBiModule<L,R,U,O_U_L,O_U_R,GROUP>& OP=(CO AbstractBiModule<L,R,U,O_U_L,O_U_R,GROUP>&)NE;IN U LAction(CO L& l,U u);IN U RAction(U u,CO R& r);};TE <TY L,TY R,TY O_U_L,TY O_U_R,TY GROUP> AbstractBiModule(CO L& dummy_l,CO R& dummy_r,O_U_L o_U_L,O_U_R o_U_R,GROUP M)-> AbstractBiModule<L,R,inner_t<GROUP>,O_U_L,O_U_R,GROUP>;TE <TY L,TY R,TY U>CL BiModule:VI PU VirtualBiModule<L,R,U>,PU AdditiveGroup<U>{PU:IN U LAction(CO L& r,U u);IN U RAction(U u,CO R& r);};
TE <TY L,TY R,TY U,TY O_U_L,TY O_U_R,TY GROUP> IN AbstractBiModule<L,R,U,O_U_L,O_U_R,GROUP>::AbstractBiModule(CO L& dummy_l,CO R& dummy_r,O_U_L o_U_L,O_U_R o_U_R,GROUP M):GROUP(MO(M)),m_o_U_L(MO(o_U_L)),m_o_U_R(MO(o_U_R)){ST_AS(is_same_v<U,inner_t<GROUP>> && is_invocable_r_v<U,O_U_L,CO L&,U> && is_invocable_r_v<U,O_U_R,U,CO R&>);}TE <TY L,TY R,TY U,TY O_U_L,TY O_U_R,TY GROUP> IN U AbstractBiModule<L,R,U,O_U_L,O_U_R,GROUP>::LAction(CO L& l,U u){RE m_o_U_L(l,MO(u));}TE <TY L,TY R,TY U> IN U BiModule<L,R,U>::LAction(CO L& l,U u){RE MO(u *= l);}TE <TY L,TY R,TY U,TY O_U_L,TY O_U_R,TY GROUP> IN U AbstractBiModule<L,R,U,O_U_L,O_U_R,GROUP>::RAction(U u,CO R& r){RE m_o_U_R(MO(u),r);}TE <TY L,TY R,TY U> IN U BiModule<L,R,U>::RAction(U u,CO R& r){RE MO(u *= r);}TE <TY L,TY R,TY U> IN U VirtualBiModule<L,R,U>::ScalarProduct(CO L& l,U u){RE LAction(l,MO(u));}TE <TY L,TY R,TY U> IN U VirtualBiModule<L,R,U>::PW(U u,CO R& r){RE RAction(MO(u),r);}


#define RP Represent
#define DeRP Derepresent

TE <TY INT1,TY INT2> CE INT1 RS(INT1 n,CO INT2& M)NE{RE MO(n < 0?((((++n)*= -1)%= M)*= -1)+= M - 1:n < M?n:n %= M);}

TE <int NUM> CL DynamicMods;TE <int NUM>CL COantsForDynamicMods{PU:COantsForDynamicMods()= delete;ST uint g_M;ST uint g_M_minus;ST int g_order_minus_1;ST int g_order_minus_1_neg;ST bool g_M_is_prime;};
TE <int NUM> uint COantsForDynamicMods<NUM>::g_M = 0;TE <int NUM> uint COantsForDynamicMods<NUM>::g_M_minus = -1;TE <int NUM> int COantsForDynamicMods<NUM>::g_order_minus_1 = 0;TE <int NUM> int COantsForDynamicMods<NUM>::g_order_minus_1_neg = 0;TE <int NUM> bool COantsForDynamicMods<NUM>::g_M_is_prime = false;

#define DC_OF_CM_FOR_DYNAMIC_MOD(OPR)IN bool OP OPR(CO DynamicMods<NUM>& n)CO NE
#define DC_OF_AR_FOR_DYNAMIC_MOD(OPR,EX)IN DynamicMods<NUM> OP OPR(DynamicMods<NUM> n)CO EX;
#define DF_OF_CM_FOR_DYNAMIC_MOD(OPR)TE <int NUM> IN bool DynamicMods<NUM>::OP OPR(CO DynamicMods<NUM>& n)CO NE{RE m_n OPR n.m_n;}
#define DF_OF_AR_FOR_DYNAMIC_MOD(OPR,EX,LEFT,OPR2)TE <int NUM> IN DynamicMods<NUM> DynamicMods<NUM>::OP OPR(DynamicMods<NUM> n)CO EX{RE MO(LEFT OPR2 ## = *TH);}TE <int NUM,TY T> IN DynamicMods<NUM> OP OPR(T n0,CO DynamicMods<NUM>& n1)EX{RE MO(DynamicMods<NUM>(MO(n0))OPR ## = n1);}
TE <int NUM>CL DynamicMods{PU:uint m_n;IN DynamicMods()NE;IN DynamicMods(CO DynamicMods<NUM>& n)NE;IN DynamicMods(DynamicMods<NUM>&& n)NE;TE <TY T> IN DynamicMods(T n)NE;IN DynamicMods<NUM>& OP=(DynamicMods<NUM> n)NE;IN DynamicMods<NUM>& OP+=(CO DynamicMods<NUM>& n)NE;IN DynamicMods<NUM>& OP-=(CO DynamicMods<NUM>& n)NE;IN DynamicMods<NUM>& OP*=(CO DynamicMods<NUM>& n)NE;IN DynamicMods<NUM>& OP/=(DynamicMods<NUM> n);TE <TY INT> IN DynamicMods<NUM>& OP<<=(INT n);TE <TY INT> IN DynamicMods<NUM>& OP>>=(INT n);IN DynamicMods<NUM>& OP++()NE;IN DynamicMods<NUM> OP++(int)NE;IN DynamicMods<NUM>& OP--()NE;IN DynamicMods<NUM> OP--(int)NE;DC_OF_CM_FOR_DYNAMIC_MOD(==);DC_OF_CM_FOR_DYNAMIC_MOD(!=);DC_OF_CM_FOR_DYNAMIC_MOD(<);DC_OF_CM_FOR_DYNAMIC_MOD(<=);DC_OF_CM_FOR_DYNAMIC_MOD(>);DC_OF_CM_FOR_DYNAMIC_MOD(>=);DC_OF_AR_FOR_DYNAMIC_MOD(+,NE);DC_OF_AR_FOR_DYNAMIC_MOD(-,NE);DC_OF_AR_FOR_DYNAMIC_MOD(*,NE);DC_OF_AR_FOR_DYNAMIC_MOD(/,);TE <TY INT> IN DynamicMods<NUM> OP^(INT EX)CO;TE <TY INT> IN DynamicMods<NUM> OP<<(INT n)CO;TE <TY INT> IN DynamicMods<NUM> OP>>(INT n)CO;IN DynamicMods<NUM> OP-()CO NE;IN DynamicMods<NUM>& SignInvert()NE;IN DynamicMods<NUM>& Invert();TE <TY INT> IN DynamicMods<NUM>& PW(INT EX);IN VO swap(DynamicMods<NUM>& n)NE;IN CRUI RP()CO NE;ST IN DynamicMods<NUM> DeRP(uint n)NE;ST IN CO DynamicMods<NUM>& Inverse(CRUI n);ST IN CO DynamicMods<NUM>& Factorial(CRUI n);ST IN CO DynamicMods<NUM>& FactorialInverse(CRUI n);ST IN DynamicMods<NUM> Combination(CRUI n,CRUI i);ST IN CO DynamicMods<NUM>& zero()NE;ST IN CO DynamicMods<NUM>& one()NE;ST IN CRUI GetModulo()NE;ST IN VO SetModulo(CRUI M,CRI order_minus_1 = -1)NE;TE <TY INT> IN DynamicMods<NUM>& PositivePW(INT EX)NE;TE <TY INT> IN DynamicMods<NUM>& NonNegativePW(INT EX)NE;US COants = COantsForDynamicMods<NUM>;};
US DynamicMod = DynamicMods<0>;
TE <int NUM> IN DynamicMods<NUM>::DynamicMods()NE:m_n(){}TE <int NUM> IN DynamicMods<NUM>::DynamicMods(CO DynamicMods<NUM>& n)NE:m_n(n.m_n){}TE <int NUM> IN DynamicMods<NUM>::DynamicMods(DynamicMods<NUM>&& n)NE:m_n(MO(n.m_n)){}TE <int NUM> TE <TY T> IN DynamicMods<NUM>::DynamicMods(T n)NE:m_n(RS(uint(MO(n)),COants::g_M)){ST_AS(is_COructible_v<uint,decay_t<T> >);}TE <int NUM> IN DynamicMods<NUM>& DynamicMods<NUM>::OP=(DynamicMods<NUM> n)NE{m_n = MO(n.m_n);RE *TH;}TE <int NUM> IN DynamicMods<NUM>& DynamicMods<NUM>::OP+=(CO DynamicMods<NUM>& n)NE{(m_n += n.m_n)< COants::g_M?m_n:m_n -= COants::g_M;RE *TH;}TE <int NUM> IN DynamicMods<NUM>& DynamicMods<NUM>::OP-=(CO DynamicMods<NUM>& n)NE{m_n < n.m_n?(m_n += COants::g_M)-= n.m_n:m_n -= n.m_n;RE *TH;}TE <int NUM> IN DynamicMods<NUM>& DynamicMods<NUM>::OP*=(CO DynamicMods<NUM>& n)NE{m_n = RS(MO(ull(m_n)* n.m_n),COants::g_M);RE *TH;}TE <int NUM> IN DynamicMods<NUM>& DynamicMods<NUM>::OP/=(DynamicMods<NUM> n){RE OP*=(n.Invert());}TE <int NUM> TE <TY INT> IN DynamicMods<NUM>& DynamicMods<NUM>::OP<<=(INT n){AS(n >= 0);RE *TH *= DynamicMods<NUM>(2).NonNegativePW(MO(n));}TE <int NUM> TE <TY INT> IN DynamicMods<NUM>& DynamicMods<NUM>::OP>>=(INT n){AS(n >= 0);WH(n-- > 0){((m_n & 1)== 0?m_n:m_n += COants::g_M)>>= 1;}RE *TH;}TE <int NUM> IN DynamicMods<NUM>& DynamicMods<NUM>::OP++()NE{m_n < COants::g_M_minus?++m_n:m_n = 0;RE *TH;}TE <int NUM> IN DynamicMods<NUM> DynamicMods<NUM>::OP++(int)NE{DynamicMods<NUM> n{*TH};OP++();RE n;}TE <int NUM> IN DynamicMods<NUM>& DynamicMods<NUM>::OP--()NE{m_n == 0?m_n = COants::g_M_minus:--m_n;RE *TH;}TE <int NUM> IN DynamicMods<NUM> DynamicMods<NUM>::OP--(int)NE{DynamicMods<NUM> n{*TH};OP--();RE n;}DF_OF_CM_FOR_DYNAMIC_MOD(==);DF_OF_CM_FOR_DYNAMIC_MOD(!=);DF_OF_CM_FOR_DYNAMIC_MOD(>);DF_OF_CM_FOR_DYNAMIC_MOD(>=);DF_OF_CM_FOR_DYNAMIC_MOD(<);DF_OF_CM_FOR_DYNAMIC_MOD(<=);DF_OF_AR_FOR_DYNAMIC_MOD(+,NE,n,+);DF_OF_AR_FOR_DYNAMIC_MOD(-,NE,n.SignInvert(),+);DF_OF_AR_FOR_DYNAMIC_MOD(*,NE,n,*);DF_OF_AR_FOR_DYNAMIC_MOD(/,,n.Invert(),*);TE <int NUM> TE <TY INT> IN DynamicMods<NUM> DynamicMods<NUM>::OP^(INT EX)CO{RE MO(DynamicMods<NUM>(*TH).PW(MO(EX)));}TE <int NUM> TE <TY INT> IN DynamicMods<NUM> DynamicMods<NUM>::OP<<(INT n)CO{RE MO(DynamicMods<NUM>(*TH)<<= MO(n));}TE <int NUM> TE <TY INT> IN DynamicMods<NUM> DynamicMods<NUM>::OP>>(INT n)CO{RE MO(DynamicMods<NUM>(*TH)>>= MO(n));}TE <int NUM> IN DynamicMods<NUM> DynamicMods<NUM>::OP-()CO NE{RE MO(DynamicMods<NUM>(*TH).SignInvert());}TE <int NUM> IN DynamicMods<NUM>& DynamicMods<NUM>::SignInvert()NE{m_n > 0?m_n = COants::g_M - m_n:m_n;RE *TH;}TE <int NUM> IN DynamicMods<NUM>& DynamicMods<NUM>::Invert(){RE m_n <(COants::g_M_is_prime?1e6:3e4)?*TH = Inverse(m_n):NonNegativePW(COants::g_order_minus_1);}TE <int NUM> TE <TY INT> IN DynamicMods<NUM>& DynamicMods<NUM>::PositivePW(INT EX)NE{DynamicMods<NUM> PW{*TH};EX--;WH(EX != 0){(EX & 1)== 1?*TH *= PW:*TH;EX >>= 1;PW *= PW;}RE *TH;}TE <int NUM> TE <TY INT> IN DynamicMods<NUM>& DynamicMods<NUM>::NonNegativePW(INT EX)NE{RE EX == 0?(m_n = 1,*TH):PositivePW(MO(EX));}TE <int NUM> TE <TY INT> IN DynamicMods<NUM>& DynamicMods<NUM>::PW(INT EX){bool neg = EX < 0;RE neg?PositivePW(MO(EX *= COants::g_order_minus_1_neg)):NonNegativePW(MO(EX));}TE <int NUM> IN VO DynamicMods<NUM>::swap(DynamicMods<NUM>& n)NE{std::swap(m_n,n.m_n);}TE <int NUM> IN CO DynamicMods<NUM>& DynamicMods<NUM>::Inverse(CRUI n){ST VE<DynamicMods<NUM>> memory ={zero(),one()};ST uint LE_curr = 2;AS(COants::g_M == 1||(0 < n && n < COants::g_M));WH(LE_curr <= n){memory.push_back(COants::g_M_is_prime?DeRP(COants::g_M - memory[COants::g_M % LE_curr].m_n * ull(COants::g_M / LE_curr)% COants::g_M):DeRP(n).NonNegativePW(COants::g_order_minus_1));LE_curr++;}RE memory[n];}TE <int NUM> IN CO DynamicMods<NUM>& DynamicMods<NUM>::Factorial(CRUI n){ST VE<DynamicMods<NUM>> memory ={one(),one()};ST uint LE_curr = 2;if(COants::g_M <= n){RE zero();}WH(LE_curr <= n && memory.back().m_n != 0){memory.push_back(memory.back()* DeRP(LE_curr));LE_curr++;}RE LE_curr <= n?memory.back():memory[n];}TE <int NUM> IN CO DynamicMods<NUM>& DynamicMods<NUM>::FactorialInverse(CRUI n){ST VE<DynamicMods<NUM>> memory ={one(),one()};ST uint LE_curr = 2;WH(LE_curr <= n){memory.push_back(memory[LE_curr - 1]* Inverse(LE_curr));LE_curr++;}RE memory[n];}TE <int NUM> IN DynamicMods<NUM> DynamicMods<NUM>::Combination(CRUI n,CRUI i){RE i <= n?Factorial(n)* FactorialInverse(i)* FactorialInverse(n - i):zero();}TE <int NUM> IN CRUI DynamicMods<NUM>::RP()CO NE{RE m_n;}TE <int NUM> IN DynamicMods<NUM> DynamicMods<NUM>::DeRP(uint n)NE{DynamicMods<NUM> n_copy{};n_copy.m_n = MO(n);RE n_copy;}TE <int NUM> IN CO DynamicMods<NUM>& DynamicMods<NUM>::zero()NE{ST CO DynamicMods<NUM> z{};RE z;}TE <int NUM> IN CO DynamicMods<NUM>& DynamicMods<NUM>::one()NE{ST CO DynamicMods<NUM> o{1};RE o;}TE <int NUM> IN CRUI DynamicMods<NUM>::GetModulo()NE{RE COants::g_M;}TE <int NUM> IN VO DynamicMods<NUM>::SetModulo(CRUI M,CRI order_minus_1)NE{COants::g_M = M;COants::g_M_minus = M - 1;COants::g_order_minus_1 = order_minus_1 == -1?M - 2:order_minus_1;COants::g_order_minus_1_neg = -COants::g_order_minus_1;COants::g_M_is_prime = order_minus_1 == -1;}TE <int NUM> IN DynamicMods<NUM> Inverse(CO DynamicMods<NUM>& n){RE MO(DynamicMods<NUM>(n).Invert());}TE <int NUM,TY INT> IN DynamicMods<NUM> PW(DynamicMods<NUM> n,INT EX){RE MO(n.PW(MO(EX)));}TE <int NUM> IN VO swap(DynamicMods<NUM>& n0,DynamicMods<NUM>& n1)NE{n0.swap(n1);}TE <int NUM> IN string to_string(CO DynamicMods<NUM>& n)NE{RE to_string(n.RP())+ " + " + to_string(DynamicMods<NUM>::GetModulo())+ "Z";}TE <int NUM,CL Traits> IN IS& OP>>(IS& is,DynamicMods<NUM>& n){ll m;is >> m;n = m;RE is;}TE <int NUM,CL Traits> IN OS& OP<<(OS& os,CO DynamicMods<NUM>& n){RE os << n.RP();}

class SqrtDecompositionCoordinate
{

protected:
  int m_N;
  int m_N_sqrt;
  // m_N / m_N_sqrt 以上である最小の整数。
  int m_N_d;
  // m_N 以上である最小の m_N_sqrt の倍数。
  int m_N_m;

public:
  inline SqrtDecompositionCoordinate( const int& N = 0 );
  inline SqrtDecompositionCoordinate( const int& N , const int& N_sqrt );

  // 2乗がN以上である最小の正整数を返す。
  static inline int Sqrt( const int& N ) noexcept;

};

inline SqrtDecompositionCoordinate::SqrtDecompositionCoordinate( const int& N ) : SqrtDecompositionCoordinate( N , Sqrt( N ) ) {};
inline SqrtDecompositionCoordinate::SqrtDecompositionCoordinate( const int& N , const int& N_sqrt ) : m_N( N ) , m_N_sqrt( N_sqrt ) , m_N_d( ( m_N + m_N_sqrt - 1 ) / m_N_sqrt ) , m_N_m( m_N_d * m_N_sqrt ) {}

inline int SqrtDecompositionCoordinate::Sqrt( const int& N ) noexcept
{

  if( N <= 1 ){

    return 1;
    
  }
  
  int l = 0 , r = N;

  while( l + 1 < r ){

    int m = ( l + r ) >> 1;
    ( m <= ( N - 1 ) / m ? l : r ) = m;

  }

  return r;

}


// TRANSは写像trans:U \times S \times N ->Uに相当する型である。

// 入力の範囲内で要件
// (1) LはRの基点付きマグマ構造である。
// (2) M0はSの左L集合構造であって、Lの基点がSの恒等変換に対応する。
// (3) M1はUの左L作用付き非可換N加群構造であって、Lの基点がMの恒等変換に対応する。
// (4) R=intならばUのL作用と非可換N加群構造が整合的である。
// (5) あるL同変写像univ:S->Uが存在して、任意の(u,s,n) in U \times S \times N
//     に対してtrans(u,s,n) = u*univ(s)*nである。
// を満たす場合にのみサポート。

// 区間作用を行わない場合もm_L.Point()の作用を区間積に用いるため、
// dummyにせずRegularRSet(MultiplicativeMonoid(1))などを用いる必要があることに注意。

// 配列による初期化O(N)

// 一点代入O(N^{1/2})はなし。
// 区間代入O(N^{1/2})（M1の非可換N加群性を使う）
// M0.Act()による一点作用はなし。
// M0.Act()による区間作用O(N^{1/2})（univのL同変性を使う）

// 一点取得O(1)
// transに関する区間積取得O(N^{1/2})（M1のモノイド性を使う）
template <typename R , typename PT_MAGMA , typename S , typename R_SET , typename U , typename RN_BIMODULE , typename TRANS>
class EquivariantLazySqrtDecomposition :
  public SqrtDecompositionCoordinate
{

protected:
  PT_MAGMA m_L;
  R_SET m_M0;
  RN_BIMODULE m_M1;
  TRANS m_trans;
  vector<S> m_a;
  vector<U> m_b;
  // 代入の遅延評価。過去の作用の遅延評価を棄却する。
  // 区間作用はここに即座に適用する。
  vector<S> m_lazy_substitution;
  vector<bool> m_suspended;
  // 作用の遅延評価。
  vector<R> m_lazy_action;

public:
  // vectorを構築する時は
  // vector t( N , EquivariantLazySqrtDecomposition{L,M0,M1,vector<S>()} );
  // としてInitialiseすればよい。
  template <typename...Args> inline EquivariantLazySqrtDecomposition( PT_MAGMA L , R_SET M0 , RN_BIMODULE M1 , TRANS trans , vector<S> a , const Args&... args );
  
  template <typename...Args> inline void Initialise( Args&&... args );
  inline void Set( const int& i , const S& s );
  inline void IntervalSet( const int& i_start , const int& i_final , const S& s );
  inline void IntervalAct( const int& i_start , const int& i_final , const R& r );

  inline S operator[]( const int& i );
  inline S Get( const int& i );
  inline U IntervalProduct( const int& i_start , const int& i_final );

private:
  inline U Univ( const S& s , const int& n );
  inline void SetProduct( const int& i );
  inline void SolveSuspendedSubstitution( const int& d , const S& s );
  inline void IntervalSet_Body( const int& i_min , const int& i_ulim , const S& s );
  // 細かく区間を指定した方が速いが、そのi_minとi_ulimの位置関係でバグらせやすいのでこのまま。
  inline void SolveSuspendedAction( const int& d );
  inline void IntervalAct_Body( const int& i_min , const int& i_ulim , const R& r );
  inline U IntervalProduct_Body( const int& i_min , const int& i_ulim );
  
};
template <typename PT_MAGMA , typename S , typename R_SET , typename RN_BIMODULE , typename TRANS , typename...Args> EquivariantLazySqrtDecomposition( PT_MAGMA L , R_SET M0 , RN_BIMODULE M1 , TRANS trans , vector<S> a , const Args&... args ) -> EquivariantLazySqrtDecomposition<inner_t<PT_MAGMA>,PT_MAGMA,S,R_SET,inner_t<RN_BIMODULE>,RN_BIMODULE,TRANS>;

template <typename R , typename PT_MAGMA , typename S , typename R_SET , typename U , typename RN_BIMODULE , typename TRANS> template <typename...Args> inline EquivariantLazySqrtDecomposition<R,PT_MAGMA,S,R_SET,U,RN_BIMODULE,TRANS>::EquivariantLazySqrtDecomposition( PT_MAGMA L , R_SET M0 , RN_BIMODULE M1 , TRANS trans , vector<S> a , const Args&... args ) : SqrtDecompositionCoordinate( a.size() , args... ) , m_L( move( L ) ) , m_M0( move( M0 ) ) , m_M1( move( M1 ) ) , m_trans( move( trans ) ) , m_a( move( a ) ) , m_b( m_N_d , m_M1.One() ) , m_lazy_substitution( m_N_d ) , m_suspended( m_N_d ) , m_lazy_action( m_N_d , m_L.Point() )
{
  
  static_assert( is_same_v<R,inner_t<PT_MAGMA>> && is_same_v<S,inner_t<R_SET>> && is_same_v<U,inner_t<RN_BIMODULE>> && is_invocable_r_v<U,TRANS,U,const S&,const int&> );

  if( m_N_m > 0 ){

    m_a.resize( m_N_m , m_a[0] );

  }
  
  int i_min = 0;
  int i_ulim = m_N_sqrt;
  
  for( int d = 0 ; d < m_N_d ; d++ ){

    U& m_bd = m_b[d];

    for( int i = i_min ; i < i_ulim ; i++ ){

      m_bd = m_trans( move( m_bd ) , m_a[i] , 1 );

    }

    i_min = i_ulim;
    i_ulim += m_N_sqrt;

  }

}

template <typename R , typename PT_MAGMA , typename S , typename R_SET , typename U , typename RN_BIMODULE , typename TRANS> template <typename...Args> inline void EquivariantLazySqrtDecomposition<R,PT_MAGMA,S,R_SET,U,RN_BIMODULE,TRANS>::Initialise( Args&&...args ) { EquivariantLazySqrtDecomposition<R,PT_MAGMA,S,R_SET,U,RN_BIMODULE,TRANS> temp{ m_L , m_M0 , m_M1 , forward<Args>( args )... }; SqrtDecompositionCoordinate::operator=( temp ); m_a = move( temp.m_a ); m_b = move( temp.m_b ); m_lazy_substitution = move( temp.m_lazy_substitution ); m_suspended = move( temp.m_suspended ); m_lazy_action = move( temp.m_lazy_action ); }

template <typename R , typename PT_MAGMA , typename S , typename R_SET , typename U , typename RN_BIMODULE , typename TRANS> inline void EquivariantLazySqrtDecomposition<R,PT_MAGMA,S,R_SET,U,RN_BIMODULE,TRANS>::IntervalSet( const int& i_start , const int& i_final , const S& s )
{

  const int i_min = max( i_start , 0 );
  const int i_ulim = min( i_final + 1 , m_N );
  const int d_0 = ( i_min + m_N_sqrt - 1 ) / m_N_sqrt;
  const int d_1 = max( d_0 , i_ulim / m_N_sqrt );
  const int d_0_N_sqrt = d_0 * m_N_sqrt;
  const int d_1_N_sqrt = d_1 * m_N_sqrt;
  const int i_0 = min( d_0_N_sqrt , i_ulim );
  const int i_1 = max( i_0 , d_1_N_sqrt );

  if( i_min < i_0 ){

    // この時d_0 > 0になる。
    const int d_0_minus = d_0 - 1;
    const int d_0_N_sqrt_minus = d_0_N_sqrt - m_N_sqrt;
    U& m_bd = m_b[d_0_minus];
    vector<bool>::reference m_suspended_d = m_suspended[d_0_minus];

    if( m_suspended_d ){

      const S& m_lazy_substitution_d = m_lazy_substitution[d_0_minus];
      IntervalSet_Body( d_0_N_sqrt_minus , i_min , m_lazy_substitution_d );
      IntervalSet_Body( i_min , i_0 , s );
      IntervalSet_Body( i_0 , d_0_N_sqrt , m_lazy_substitution_d );
      m_suspended_d = false;
      // 非可換N加群性を使った。
      m_bd = m_trans( m_trans( Univ( m_lazy_substitution_d , i_min - d_0_N_sqrt_minus ) , s , i_0 - i_min ) , m_lazy_substitution_d , d_0_N_sqrt - i_0 );

    } else {

      SolveSuspendedAction( d_0_minus );
      IntervalSet_Body( i_min , i_0 , s );
      m_bd = m_M1.Product( m_trans( IntervalProduct_Body( d_0_N_sqrt_minus , i_min ) , s , i_0 - i_min ) , IntervalProduct_Body( i_0 , d_0_N_sqrt ) );
      
    }
    
  }

  const U power = Univ( s , m_N_sqrt );
  
  for( int d = d_0 ; d < d_1 ; d++ ){

    m_b[d] = power;
    m_lazy_substitution[d] = s;
    m_suspended[d] = true;
    m_lazy_action[d] = m_L.Point();

  }

  if( i_1 < i_ulim ){
      
    // この時d_1 < m_N_dになる。
    const int d_1_N_sqrt_plus = d_1_N_sqrt + m_N_sqrt;
    U& m_bd = m_b[d_1];
    vector<bool>::reference m_suspended_d = m_suspended[d_1];

    if( m_suspended_d ){

      const S& m_lazy_substitution_d = m_lazy_substitution[d_1];
      IntervalSet_Body( d_1_N_sqrt , i_1 , m_lazy_substitution_d );
      IntervalSet_Body( i_1 , i_ulim , s );
      IntervalSet_Body( i_ulim , d_1_N_sqrt_plus , m_lazy_substitution_d );
      m_suspended_d = false;
      m_bd = m_trans( m_trans( Univ( m_lazy_substitution_d , i_1 - d_1_N_sqrt ) , s , i_ulim - i_1 ) , m_lazy_substitution_d , d_1_N_sqrt_plus - i_ulim );

    } else {

      SolveSuspendedAction( d_1 );
      IntervalSet_Body( i_1 , i_ulim , s );
      m_bd = m_M1.Product( m_trans( IntervalProduct_Body( d_1_N_sqrt , i_1 ) , s , i_ulim - i_1 ) , IntervalProduct_Body( i_ulim , d_1_N_sqrt_plus ) );
      
    }
    
  }
  
  return;

}

template <typename R , typename PT_MAGMA , typename S , typename R_SET , typename U , typename RN_BIMODULE , typename TRANS> inline void EquivariantLazySqrtDecomposition<R,PT_MAGMA,S,R_SET,U,RN_BIMODULE,TRANS>::IntervalAct( const int& i_start , const int& i_final , const R& r )
{

  if( r != m_L.Point() ){
  
    const int i_min = max( i_start , 0 );
    const int i_ulim = min( i_final + 1 , m_N );
    const int d_0 = ( i_min + m_N_sqrt - 1 ) / m_N_sqrt;
    const int d_1 = max( d_0 , i_ulim / m_N_sqrt );
    const int d_0_N_sqrt = d_0 * m_N_sqrt;
    const int d_1_N_sqrt = d_1 * m_N_sqrt;
    const int i_0 = min( d_0_N_sqrt , i_ulim );
    const int i_1 = max( i_0 , d_1_N_sqrt );

    if( i_min < i_0 ){

      // この時d_0 > 0になる。
      const int d_0_minus = d_0 - 1;
      const int d_0_N_sqrt_minus = d_0_N_sqrt - m_N_sqrt;
      vector<bool>::reference m_suspended_d = m_suspended[d_0_minus];

      if( m_suspended_d ){

	S& m_lazy_substitution_d = m_lazy_substitution[d_0_minus];
	U& m_bd = m_b[d_0_minus];
	const S s = m_M0.Action( r , m_lazy_substitution_d );
	IntervalSet_Body( d_0_N_sqrt_minus , i_min , m_lazy_substitution_d );
	IntervalSet_Body( i_min , i_0 , s );
	IntervalSet_Body( i_0 , d_0_N_sqrt , m_lazy_substitution_d );
	m_suspended_d = false;
	// 非可換N加群性を使った。
	m_bd = m_trans( m_trans( Univ( m_lazy_substitution_d , i_min - d_0_N_sqrt_minus ) , s , i_0 - i_min ) , m_lazy_substitution_d , d_0_N_sqrt - i_0 );

      } else {

	R& m_lazy_action_d = m_lazy_action[d_0_minus];

	if( m_lazy_action_d == m_L.Point() ){

	  IntervalAct_Body( i_min , i_0 , r );

	} else {
	  
	  IntervalAct_Body( d_0_N_sqrt_minus , i_min , m_lazy_action_d );
	  IntervalAct_Body( i_min , i_0 , m_L.Product( r , m_lazy_action_d ) );
	  IntervalAct_Body( i_0 , d_0_N_sqrt , m_lazy_action_d );
	  m_lazy_action_d = m_L.Point();

	}

	SetProduct( d_0_minus );
      
      }

    }
  
    for( int d = d_0 ; d < d_1 ; d++ ){

      U& m_bd = m_b[d];
      m_bd = m_M1.ScalarProduct( r , m_bd );

      if( m_suspended[d] ){

	S& m_lazy_substitution_d = m_lazy_substitution[d];
	m_lazy_substitution_d = m_M0.Action( r , m_lazy_substitution_d );

      } else {
      
	R& m_lazy_action_d = m_lazy_action[d];
	m_lazy_action_d = m_L.Product( r , m_lazy_action_d );

      }

    }

    if( i_1 < i_ulim ){
      
      // この時d_1 < m_N_dになる。
      const int d_1_N_sqrt_plus = d_1_N_sqrt + m_N_sqrt;
      vector<bool>::reference m_suspended_d = m_suspended[d_1];

      if( m_suspended_d ){

	S& m_lazy_substitution_d = m_lazy_substitution[d_1];
	U& m_bd = m_b[d_1];
	const S s = m_M0.Action( r , m_lazy_substitution_d );
	IntervalSet_Body( d_1_N_sqrt , i_1 , m_lazy_substitution_d );
	IntervalSet_Body( i_1 , i_ulim , s );
	IntervalSet_Body( i_ulim , d_1_N_sqrt_plus , m_lazy_substitution_d );
	m_suspended_d = false;
	// 非可換N加群性を使った。
	m_bd = m_trans( m_trans( Univ( m_lazy_substitution_d , i_1 - d_1_N_sqrt ) , s , i_ulim - i_1 ) , m_lazy_substitution_d , d_1_N_sqrt_plus - i_ulim );

      } else {

	R& m_lazy_action_d = m_lazy_action[d_1];

	if( m_lazy_action_d == m_L.Point() ){

	  IntervalAct_Body( i_1 , i_ulim , r );

	} else {
	  
	  IntervalAct_Body( d_1_N_sqrt , i_1 , m_lazy_action_d );
	  IntervalAct_Body( i_1 , i_ulim , m_L.Product( r , m_lazy_action_d ) );
	  IntervalAct_Body( i_ulim , d_1_N_sqrt_plus , m_lazy_action_d );
	  m_lazy_action_d = m_L.Point();

	}
      
	SetProduct( d_1 );

      }

    }

  }
  
  return;
  
}

template <typename R , typename PT_MAGMA , typename S , typename R_SET , typename U , typename RN_BIMODULE , typename TRANS> inline U EquivariantLazySqrtDecomposition<R,PT_MAGMA,S,R_SET,U,RN_BIMODULE,TRANS>::IntervalProduct_Body( const int& i_min , const int& i_ulim )
{

  U answer = m_M1.One();
  
  for( int i = i_min ; i < i_ulim ; i++ ){

    answer = m_trans( move( answer ) , m_a[i] , 1 );

  }

  return answer;
  
}

template <typename R , typename PT_MAGMA , typename S , typename R_SET , typename U , typename RN_BIMODULE , typename TRANS> inline U EquivariantLazySqrtDecomposition<R,PT_MAGMA,S,R_SET,U,RN_BIMODULE,TRANS>::Univ( const S& s , const int& n ) { return m_trans( m_M1.One() , s , n ); }

template <typename R , typename PT_MAGMA , typename S , typename R_SET , typename U , typename RN_BIMODULE , typename TRANS> inline void EquivariantLazySqrtDecomposition<R,PT_MAGMA,S,R_SET,U,RN_BIMODULE,TRANS>::SetProduct( const int& d )
{

  U& m_bd = m_b[d] = m_M1.One();
  const int i_min = d * m_N_sqrt;
  const int i_ulim = i_min + m_N_sqrt;

  for( int i = i_min ; i < i_ulim ; i++ ){

    m_bd = m_trans( move( m_bd ) , m_a[i] , 1 );

  }

  return;

}

template <typename R , typename PT_MAGMA , typename S , typename R_SET , typename U , typename RN_BIMODULE , typename TRANS> inline void EquivariantLazySqrtDecomposition<R,PT_MAGMA,S,R_SET,U,RN_BIMODULE,TRANS>::SolveSuspendedSubstitution( const int& d , const S& s )
{

  const int i_min = d * m_N_sqrt;
  IntervalSet_Body( i_min , i_min + m_N_sqrt , s );
  m_suspended[d] = false;
  return;

}

template <typename R , typename PT_MAGMA , typename S , typename R_SET , typename U , typename RN_BIMODULE , typename TRANS> inline void EquivariantLazySqrtDecomposition<R,PT_MAGMA,S,R_SET,U,RN_BIMODULE,TRANS>::IntervalSet_Body( const int& i_min , const int& i_ulim , const S& s )
{

  for( int i = i_min ; i < i_ulim ; i++ ){

    m_a[i] = s;

  }

  return;
  
}

template <typename R , typename PT_MAGMA , typename S , typename R_SET , typename U , typename RN_BIMODULE , typename TRANS> inline void EquivariantLazySqrtDecomposition<R,PT_MAGMA,S,R_SET,U,RN_BIMODULE,TRANS>::SolveSuspendedAction( const int& d )
{

  R& m_lazy_action_d = m_lazy_action[d];

  if( m_lazy_action_d != m_L.Point() ){

    const int i_min = d * m_N_sqrt;
    const int i_ulim = i_min + m_N_sqrt;
    IntervalAct_Body( i_min , i_ulim , m_lazy_action_d );
    U& m_bd = m_b[d];
    m_bd = m_M1.ScalarProduct( m_lazy_action_d , m_bd );
    m_lazy_action_d = m_L.Point();
 
  }

  return;
  
}

template <typename R , typename PT_MAGMA , typename S , typename R_SET , typename U , typename RN_BIMODULE , typename TRANS> inline S EquivariantLazySqrtDecomposition<R,PT_MAGMA,S,R_SET,U,RN_BIMODULE,TRANS>::operator[]( const int& i ) { assert( 0 <= i && i < m_N ); const int d = i / m_N_sqrt; return m_suspended[d] ? m_lazy_substitution[d] : m_M0.Action( m_lazy_action[d] , m_a[i] ); }
template <typename R , typename PT_MAGMA , typename S , typename R_SET , typename U , typename RN_BIMODULE , typename TRANS> inline S EquivariantLazySqrtDecomposition<R,PT_MAGMA,S,R_SET,U,RN_BIMODULE,TRANS>::Get( const int& i ) { return operator[]( i ); }

template <typename R , typename PT_MAGMA , typename S , typename R_SET , typename U , typename RN_BIMODULE , typename TRANS> inline U EquivariantLazySqrtDecomposition<R,PT_MAGMA,S,R_SET,U,RN_BIMODULE,TRANS>::IntervalProduct( const int& i_start , const int& i_final )
{

  const int i_min = max( i_start , 0 );
  const int i_ulim = min( i_final + 1 , m_N );
  const int d_0 = ( i_min + m_N_sqrt - 1 ) / m_N_sqrt;
  const int d_1 = max( d_0 , i_ulim / m_N_sqrt );
  const int i_0 = min( d_0 * m_N_sqrt , i_ulim ) ;
  const int i_1 = max( i_0 , d_1 * m_N_sqrt );
  
  U answer = m_M1.One();

  if( i_min < i_0 ){

    // この時d_0 > 0になる。
    const int d_0_minus = d_0 - 1;
    // 非可換N加群性を使った。
    answer = m_suspended[d_0_minus] ? m_trans( move( answer ) , m_lazy_substitution[d_0_minus] , i_0 - i_min ) : m_M1.ScalarProduct( m_lazy_action[d_0_minus] , IntervalProduct_Body( i_min , i_0 ) );
    
  }
  
  for( int d = d_0 ; d < d_1 ; d++ ){

    answer = m_M1.Product( move( answer ) , m_b[d] );

  }

  if( i_1 < i_ulim ){

    // この時d_1 < m_N_dになる。
    // 非可換N加群性を使った。
    answer = m_suspended[d_1] ? m_trans( move( answer ), m_lazy_substitution[d_1] , i_ulim - i_1 ) : m_M1.Product( move( answer ), m_M1.ScalarProduct( m_lazy_action[d_1] , IntervalProduct_Body( i_1 , i_ulim ) ) );

  }

  return answer;

}

template <typename R , typename PT_MAGMA , typename S , typename R_SET , typename U , typename RN_BIMODULE , typename TRANS> inline void EquivariantLazySqrtDecomposition<R,PT_MAGMA,S,R_SET,U,RN_BIMODULE,TRANS>::IntervalAct_Body( const int& i_min , const int& i_ulim , const R& r )
{

  for( int i = i_min ; i < i_ulim ; i++ ){

    S& m_ai = m_a[i];
    m_ai = m_M0.Action( r , m_ai );

  }

  return;
  
}

// AAA ライブラリは以上に挿入する。

#define INCLUDE_MAIN
#include __FILE__

#else // INCLUDE_LIBRARY

#ifdef DEBUG
  #define _GLIBCXX_DEBUG
  #define DEXPR( LL , BOUND , VALUE1 , VALUE2 ) CEXPR( LL , BOUND , VALUE2 )
  #define SIGNAL signal( SIGABRT , &AlertAbort );
  #define ASSERT( A , MIN , MAX ) CERR( "ASSERTチェック： " , ( MIN ) , ( ( MIN ) <= A ? "<=" : ">" ) , A , ( A <= ( MAX ) ? "<=" : ">" ) , ( MAX ) ); assert( ( MIN ) <= A && A <= ( MAX ) )
  #define CERR( ... ) VariadicCout( cerr , __VA_ARGS__ ) << endl
  #define COUT( ... ) VariadicCout( cout << "出力： " , __VA_ARGS__ ) << endl
  #define CERR_A( A , N ) OUTPUT_ARRAY( cerr , A , N ) << endl
  #define COUT_A( A , N ) cout << "出力： "; OUTPUT_ARRAY( cout , A , N ) << endl
  #define CERR_ITR( A ) OUTPUT_ITR( cerr , A ) << endl
  #define COUT_ITR( A ) cout << "出力： "; OUTPUT_ITR( cout , A ) << endl
#else
  #pragma GCC optimize ( "O3" )
  #pragma GCC optimize ( "unroll-loops" )
  #pragma GCC target ( "sse4.2,fma,avx2,popcnt,lzcnt,bmi2" )
  #define SIGNAL 
  #define DEXPR( LL , BOUND , VALUE1 , VALUE2 ) CEXPR( LL , BOUND , VALUE1 )
  #define ASSERT( A , MIN , MAX ) assert( ( MIN ) <= A && A <= ( MAX ) )
  #define CERR( ... ) 
  #define COUT( ... ) VariadicCout( cout , __VA_ARGS__ ) << ENDL
  #define CERR_A( N , A ) 
  #define COUT_A( N , A ) OUTPUT_ARRAY( cout , N , A ) << ENDL
  #define CERR_ITR( A ) 
  #define COUT_ITR( A ) OUTPUT_ITR( cout , A ) << ENDL
#endif
#ifdef REACTIVE
  #define ENDL endl
#else
  #define ENDL "\n"
#endif
#ifdef USE_GETLINE
  #define SET_LL( A ) { GETLINE( A ## _str ); A = stoll( A ## _str ); }
  #define GETLINE_SEPARATE( SEPARATOR , ... ) string __VA_ARGS__; VariadicGetline( cin , SEPARATOR , __VA_ARGS__ )
  #define GETLINE( ... ) GETLINE_SEPARATE( '\n' , __VA_ARGS__ )
#else
  #define SET_LL( A ) cin >> A
  #define CIN( LL , ... ) LL __VA_ARGS__; VariadicCin( cin , __VA_ARGS__ )
  #define SET_A( I , N , ... ) VariadicResize( N + I , __VA_ARGS__ ); FOR( VARIABLE_FOR_SET_A , 0 , N ){ VariadicSet( cin , VARIABLE_FOR_SET_A + I , __VA_ARGS__ ); }
  #define CIN_A( LL , I , N , ... ) VE<LL> __VA_ARGS__; SET_A( I , N , __VA_ARGS__ );
  #define CIN_AA( LL , I0 , N0 , I1 , N1 , VAR ) VE<VE<LL>> VAR( N0 + I0 ); FOR( VARIABLE_FOR_CIN_AA , 0 , N0 ){ SET_A( I1 , N1 , VAR[VARIABLE_FOR_CIN_AA + I0] ); }
#endif
#include <bits/stdc++.h>
using namespace std;
#define REPEAT_MAIN( BOUND ) int main(){ ios_base::sync_with_stdio( false ); cin.tie( nullptr ); SIGNAL; CEXPR( int , bound_test_case_num , BOUND ); int test_case_num = 1; if constexpr( bound_test_case_num > 1 ){ CERR( "テストケースの個数を入力してください。" ); SET_ASSERT( test_case_num , 1 , bound_test_case_num ); } REPEAT( test_case_num ){ if constexpr( bound_test_case_num > 1 ){ CERR( "testcase " , VARIABLE_FOR_REPEAT_test_case_num , ":" ); } Solve(); CERR( "" ); } }
#define START_WATCH chrono::system_clock::time_point watch = chrono::system_clock::now()
#define CURRENT_TIME static_cast<double>( chrono::duration_cast<chrono::microseconds>( chrono::system_clock::now() - watch ).count() / 1000.0 )
#define CHECK_WATCH( TL_MS ) ( CURRENT_TIME < TL_MS - 100.0 )
#define CEXPR( LL , BOUND , VALUE ) constexpr LL BOUND = VALUE
#define SET_ASSERT( A , MIN , MAX ) SET_LL( A ); ASSERT( A , MIN , MAX )
#define SET_A_ASSERT( I , N , A , MIN , MAX ) FOR( VARIABLE_FOR_SET_A , 0 , N ){ SET_ASSERT( A[VARIABLE_FOR_SET_A + I] , MIN , MAX ); }
#define SET_AA_ASSERT( I0 , N0 , I1 , N1 , A , MIN , MAX ) FOR( VARIABLE_FOR_SET_AA0 , 0 , N0 ){ FOR( VARIABLE_FOR_SET_AA1 , 0 , N1 ){ SET_ASSERT( A[VARIABLE_FOR_SET_AA0 + I0][VARIABLE_FOR_SET_AA1 + I1] , MIN , MAX ); } }
#define CIN_ASSERT( A , MIN , MAX ) decldecay_t( MAX ) A; SET_ASSERT( A , MIN , MAX )
#define CIN_A_ASSERT( I , N , A , MIN , MAX ) vector<decldecay_t( MAX )> A( N + I ); SET_A_ASSERT( I , N , A , MIN , MAX )
#define CIN_AA_ASSERT( I0 , N0 , I1 , N1 , A , MIN , MAX ) vector A( N0 + I0 , vector<decldecay_t( MAX )>( N1 + I1 ) ); SET_AA_ASSERT( I0 , N0 , I1 , N1 , A , MIN , MAX )
#define FOR( VAR , INITIAL , FINAL_PLUS_ONE ) for( decldecay_t( FINAL_PLUS_ONE ) VAR = INITIAL ; VAR < FINAL_PLUS_ONE ; VAR ++ )
#define FOREQ( VAR , INITIAL , FINAL ) for( decldecay_t( FINAL ) VAR = INITIAL ; VAR <= FINAL ; VAR ++ )
#define FOREQINV( VAR , INITIAL , FINAL ) for( decldecay_t( INITIAL ) VAR = INITIAL ; VAR + 1 > FINAL ; VAR -- )
#define ITR( ARRAY ) auto begin_ ## ARRAY = ARRAY .BE() , itr_ ## ARRAY = begin_ ## ARRAY , end_ ## ARRAY = ARRAY .EN()
#define FOR_ITR( ARRAY ) for( ITR( ARRAY ) , itr = itr_ ## ARRAY ; itr_ ## ARRAY != end_ ## ARRAY ; itr_ ## ARRAY ++ , itr++ )
#define RUN( ARRAY , ... ) for( auto&& __VA_ARGS__ : ARRAY )
#define REPEAT( HOW_MANY_TIMES ) FOR( VARIABLE_FOR_REPEAT_ ## HOW_MANY_TIMES , 0 , HOW_MANY_TIMES )
#define SET_PRECISION( DECIMAL_DIGITS ) cout << fixed << setprecision( DECIMAL_DIGITS )
#define RETURN( ... ) COUT( __VA_ARGS__ ); return

// 型のエイリアス
#define decldecay_t( VAR ) decay_t<decltype( VAR )>
template <typename F , typename...Args> using ret_t = decltype( declval<F>()( declval<Args>()... ) );
template <typename T> using inner_t = typename T::type;
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using lld = __float128;
template <typename INT> using T2 = pair<INT,INT>;
template <typename INT> using T3 = tuple<INT,INT,INT>;
template <typename INT> using T4 = tuple<INT,INT,INT,INT>;
using path = pair<int,ll>;

// 入出力用
template <class Traits , typename T , typename U , template <typename...> typename V> inline auto operator>>( basic_istream<char,Traits>& is , V<T,U>& arg ) -> decltype((get<0>(arg),is))& { return is >> get<0>( arg ) >> get<1>( arg ); }
template <class Traits , typename T , typename U , typename V> inline basic_istream<char,Traits>& operator>>( basic_istream<char,Traits>& is , tuple<T,U,V>& arg ) { return is >> get<0>( arg ) >> get<1>( arg ) >> get<2>( arg ); }
template <class Traits , typename T , typename U , typename V , typename W> inline basic_istream<char,Traits>& operator>>( basic_istream<char,Traits>& is , tuple<T,U,V,W>& arg ) { return is >> get<0>( arg ) >> get<1>( arg ) >> get<2>( arg ) >> get<3>( arg ); }

template <class Traits , typename T , typename U , template <typename...> typename V> inline auto operator<<( basic_ostream<char,Traits>& os , const V<T,U>& arg ) -> decltype((get<0>(arg),os))& { return os << get<0>( arg ) << " " << get<1>( arg ); }
template <class Traits , typename T , typename U , typename V> inline basic_ostream<char,Traits>& operator<<( basic_ostream<char,Traits>& os , const tuple<T,U,V>& arg ) { return os << get<0>( arg ) << " " << get<1>( arg ) << " " << get<2>( arg ); }
template <class Traits , typename T , typename U , typename V , typename W> inline basic_ostream<char,Traits>& operator<<( basic_ostream<char,Traits>& os , const tuple<T,U,V,W>& arg ) { return os << get<0>( arg ) << " " << get<1>( arg ) << " " << get<2>( arg ) << " " << get<3>( arg ); }

#define DEFINITION_OF_COUT_FOR_VECTOR( V ) template <class Traits , typename Arg> inline basic_ostream<char,Traits>& operator<<( basic_ostream<char,Traits>& os , const V<Arg>& arg ) { auto begin = arg.begin() , end = arg.end(); auto itr = begin; while( itr != end ){ ( itr == begin ? os : os << " " ) << *itr; itr++; } return os; }
DEFINITION_OF_COUT_FOR_VECTOR( vector );
DEFINITION_OF_COUT_FOR_VECTOR( list );
DEFINITION_OF_COUT_FOR_VECTOR( set );
DEFINITION_OF_COUT_FOR_VECTOR( unordered_set );

inline void VariadicResize( const int& size ) {}
template <typename Arg , typename... ARGS> inline void VariadicResize( const int& size , Arg& arg , ARGS&... args ) { arg.resize( size ); VariadicResize( size , args... ); }

template <class Traits> inline basic_istream<char,Traits>& VariadicCin( basic_istream<char,Traits>& is ) { return is; }
template <class Traits , typename Arg , typename... ARGS> inline basic_istream<char,Traits>& VariadicCin( basic_istream<char,Traits>& is , Arg& arg , ARGS&... args ) { return VariadicCin( is >> arg , args... ); }
template <class Traits> inline basic_istream<char,Traits>& VariadicSet( basic_istream<char,Traits>& is , const int& i ) { return is; }
template <class Traits , typename Arg , typename... ARGS> inline basic_istream<char,Traits>& VariadicSet( basic_istream<char,Traits>& is , const int& i , Arg& arg , ARGS&... args ) { return VariadicSet( is >> arg[i] , i , args... ); }

template <class Traits> inline basic_istream<char,Traits>& VariadicGetline( basic_istream<char,Traits>& is , const char& separator ) { return is; }
template <class Traits , typename Arg , typename... ARGS> inline basic_istream<char,Traits>& VariadicGetline( basic_istream<char,Traits>& is , const char& separator , Arg& arg , ARGS&... args ) { return VariadicGetline( getline( is , arg , separator ) , separator , args... ); }

template <class Traits , typename Arg> inline basic_ostream<char,Traits>& VariadicCout( basic_ostream<char,Traits>& os , const Arg& arg ) { return os << arg; }
template <class Traits , typename Arg1 , typename Arg2 , typename... ARGS> inline basic_ostream<char,Traits>& VariadicCout( basic_ostream<char,Traits>& os , const Arg1& arg1 , const Arg2& arg2 , const ARGS&... args ) { return VariadicCout( os << arg1 << " " , arg2 , args... ); }

// デバッグ用
#ifdef DEBUG
  inline void AlertAbort( int n ) { CERR( "abort関数が呼ばれました。assertマクロのメッセージが出力されていない場合はオーバーフローの有無を確認をしてください。" ); }
#endif

#define INCLUDE_LIBRARY
#include __FILE__

#endif // INCLUDE_LIBRARY

#endif // INCLUDE_MAIN
yukicoder

結果

ソースコード
