#line 1 "verify/monoid/commutative_flags.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/aplusb"
#include<iostream>#line 1 "acted_monoid/concept.hpp"
#include<concepts>namespacem1une{namespaceacted_monoid{// Concept defining the requirements for an Acted Monoid.template<typenameAM>conceptIsActedMonoid=requires(typenameAM::value_typea,typenameAM::value_typeb,typenameAM::operator_typef,typenameAM::operator_typeg){// 1. Value MonoidtypenameAM::value_type;{AM::id()}->std::same_as<typenameAM::value_type>;{AM::op(a,b)}->std::same_as<typenameAM::value_type>;// 2. Operator MonoidtypenameAM::operator_type;{AM::op_id()}->std::same_as<typenameAM::operator_type>;{AM::op_comp(f,g)}->std::same_as<typenameAM::operator_type>;// Composition order: f(g(x))// 3. Mapping: Operator x Value -> Value{AM::mapping(f,a)}->std::same_as<typenameAM::value_type>;};// Concept for acted monoids whose value monoid is a commutative group.// The value operation must obey commutativity and inverse laws.template<typenameAM>conceptIsCommutativeActedGroup=IsActedMonoid<AM>&&requires(typenameAM::value_typea){{AM::inv(a)}->std::same_as<typenameAM::value_type>;};}// namespace acted_monoid}// namespace m1une#line 1 "acted_monoid/range_add_range_arg_max.hpp"
#include<limits>namespacem1une{namespaceacted_monoid{template<typenameT>structRangeAddRangeArgMaxNode{Tmax_val;longlongsize;longlongord;};// Acted Monoid for Range Addition and Range Maximum Value & Index queries.template<typenameT>structRangeAddRangeArgMax{usingvalue_type=RangeAddRangeArgMaxNode<T>;usingoperator_type=T;staticconstexprboolcommutative=false;staticconstexprbooloperator_commutative=true;staticconstexprvalue_typeid(){return{std::numeric_limits<T>::lowest(),0,-1};}staticconstexprvalue_typeop(constvalue_type&a,constvalue_type&b){if(a.size==0)returnb;if(b.size==0)returna;longlongsize=a.size+b.size;if(a.max_val>=b.max_val)return{a.max_val,size,a.ord};return{b.max_val,size,b.ord+a.size};}staticconstexproperator_typeop_id(){returnT(0);}staticconstexproperator_typeop_comp(constoperator_type&f,constoperator_type&g){returnf+g;}staticconstexprvalue_typemapping(constoperator_type&f,constvalue_type&x){if(x.size==0)returnx;return{x.max_val+f,x.size,x.ord};}staticconstexprvalue_typemake(constT&val){return{val,1,0};}};}// namespace acted_monoid}// namespace m1une#line 1 "acted_monoid/range_add_range_arg_min.hpp"
#include<functional>
#line 6 "acted_monoid/range_add_range_arg_min.hpp"
#line 1 "monoid/arg_min.hpp"
#line 6 "monoid/arg_min.hpp"
namespacem1une{namespacemonoid{template<typenameT>structArgMinNode{Tvalue;longlongsize;longlongord;};// Monoid for finding the optimal value (minimum by default) and its relative order.// Ties are broken by choosing the earlier element.template<typenameT,TId=std::numeric_limits<T>::max(),typenameCompare=std::less<T>>structArgMin{usingvalue_type=ArgMinNode<T>;staticconstexprboolcommutative=false;staticconstexprvalue_typeid(){return{Id,0,-1};}staticconstexprvalue_typeop(constvalue_type&a,constvalue_type&b){if(a.size==0)returnb;if(b.size==0)returna;longlongsize=a.size+b.size;if(Compare()(a.value,b.value))return{a.value,size,a.ord};if(Compare()(b.value,a.value))return{b.value,size,b.ord+a.size};return{a.value,size,a.ord};}staticconstexprvalue_typemake(constT&val){return{val,1,0};}};}// namespace monoid}// namespace m1une#line 8 "acted_monoid/range_add_range_arg_min.hpp"
namespacem1une{namespaceacted_monoid{template<typenameT,TId=std::numeric_limits<T>::max(),typenameCompare=std::less<T>>structRangeAddRangeArgMin{usingBaseMonoid=m1une::monoid::ArgMin<T,Id,Compare>;usingvalue_type=typenameBaseMonoid::value_type;usingoperator_type=T;staticconstexprboolcommutative=false;staticconstexprbooloperator_commutative=true;// Value Monoid (ArgMin)staticconstexprvalue_typeid(){returnBaseMonoid::id();}staticconstexprvalue_typeop(constvalue_type&a,constvalue_type&b){returnBaseMonoid::op(a,b);}// Operator Monoid (Add)staticconstexproperator_typeop_id(){returnT(0);}staticconstexproperator_typeop_comp(constoperator_type&f,constoperator_type&g){returnf+g;}// Mappingstaticconstexprvalue_typemapping(constoperator_type&f,constvalue_type&x){if(x.size==0)returnx;return{x.value+f,x.size,x.ord};}// Helper for initializing a leaf nodestaticconstexprvalue_typemake(constT&val){returnBaseMonoid::make(val);}};}// namespace acted_monoid}// namespace m1une#line 1 "acted_monoid/range_add_range_max.hpp"
#include<algorithm>
#line 6 "acted_monoid/range_add_range_max.hpp"
namespacem1une{namespaceacted_monoid{template<typenameT,TId=std::numeric_limits<T>::lowest()>structRangeAddRangeMax{usingvalue_type=T;usingoperator_type=T;staticconstexprboolcommutative=true;staticconstexprbooloperator_commutative=true;// Value Monoid (Max)staticconstexprvalue_typeid(){returnId;}staticconstexprvalue_typeop(constvalue_type&a,constvalue_type&b){returnstd::max(a,b);}// Operator Monoid (Add)staticconstexproperator_typeop_id(){return0;}staticconstexproperator_typeop_comp(constoperator_type&f,constoperator_type&g){returnf+g;}// Mappingstaticconstexprvalue_typemapping(constoperator_type&f,constvalue_type&x){if(x==id())returnx;// Do not apply the operator to the identity elementreturnx+f;}};}// namespace acted_monoid}// namespace m1une#line 1 "acted_monoid/range_add_range_min.hpp"
#line 6 "acted_monoid/range_add_range_min.hpp"
namespacem1une{namespaceacted_monoid{template<typenameT,TId=std::numeric_limits<T>::max()>structRangeAddRangeMin{usingvalue_type=T;usingoperator_type=T;staticconstexprboolcommutative=true;staticconstexprbooloperator_commutative=true;// Value Monoid (Min)staticconstexprvalue_typeid(){returnId;}staticconstexprvalue_typeop(constvalue_type&a,constvalue_type&b){returnstd::min(a,b);}// Operator Monoid (Add)staticconstexproperator_typeop_id(){return0;}staticconstexproperator_typeop_comp(constoperator_type&f,constoperator_type&g){returnf+g;}// Mappingstaticconstexprvalue_typemapping(constoperator_type&f,constvalue_type&x){if(x==id())returnx;// Do not apply the operator to the identity elementreturnx+f;}};}// namespace acted_monoid}// namespace m1une#line 1 "acted_monoid/range_add_range_min_count.hpp"
#line 6 "acted_monoid/range_add_range_min_count.hpp"
#line 1 "monoid/min_count.hpp"
#line 6 "monoid/min_count.hpp"
#include<utility>namespacem1une{namespacemonoid{// Monoid for finding the optimal value and its frequency in a range.// Uses a comparison functor (Compare) to determine the optimal value (default is less, i.e., minimum).template<typenameT,TId=std::numeric_limits<T>::max(),typenameCompare=std::less<T>>structMinCount{usingvalue_type=std::pair<T,int>;staticconstexprboolcommutative=true;// The identity element has the specified Id value and a count of 0.staticconstexprvalue_typeid(){return{Id,0};}// Combines two elements, updating the optimal value and summing the counts if they are equal.staticconstexprvalue_typeop(constvalue_type&a,constvalue_type&b){if(Compare()(a.first,b.first))returna;if(Compare()(b.first,a.first))returnb;return{a.first,a.second+b.second};}// Helper to securely create a leaf node from a single value.staticconstexprvalue_typemake(constT&val,intcount=1){return{val,count};}};}// namespace monoid}// namespace m1une#line 8 "acted_monoid/range_add_range_min_count.hpp"
namespacem1une{namespaceacted_monoid{template<typenameT,TId=std::numeric_limits<T>::max(),typenameCompare=std::less<T>>structRangeAddRangeMinCount{usingBaseMonoid=m1une::monoid::MinCount<T,Id,Compare>;usingvalue_type=typenameBaseMonoid::value_type;// std::pair<T, int>usingoperator_type=T;staticconstexprboolcommutative=true;staticconstexprbooloperator_commutative=true;// Value Monoid (Min Count)staticconstexprvalue_typeid(){returnBaseMonoid::id();}staticconstexprvalue_typeop(constvalue_type&a,constvalue_type&b){returnBaseMonoid::op(a,b);}// Operator Monoid (Add)staticconstexproperator_typeop_id(){returnT(0);}staticconstexproperator_typeop_comp(constoperator_type&f,constoperator_type&g){returnf+g;}// Mappingstaticconstexprvalue_typemapping(constoperator_type&f,constvalue_type&x){if(x.second==0)returnx;// Do not apply to the identity elementreturn{x.first+f,x.second};}// Helper for initializing a leaf nodestaticconstexprvalue_typemake(constT&val,intcount=1){returnBaseMonoid::make(val,count);}};}// namespace acted_monoid}// namespace m1une#line 1 "acted_monoid/range_add_range_sum.hpp"
namespacem1une{namespaceacted_monoid{template<typenameT>structRangeAddRangeSumNode{Tsum;longlongsize;};template<typenameT>structRangeAddRangeSum{usingvalue_type=RangeAddRangeSumNode<T>;usingoperator_type=T;staticconstexprboolcommutative=true;staticconstexprbooloperator_commutative=true;// Value Monoid (Sum)staticconstexprvalue_typeid(){return{T(0),0};}staticconstexprvalue_typeop(constvalue_type&a,constvalue_type&b){return{a.sum+b.sum,a.size+b.size};}staticconstexprvalue_typeinv(constvalue_type&x){return{-x.sum,-x.size};}// Operator Monoid (Add)staticconstexproperator_typeop_id(){return0;}staticconstexproperator_typeop_comp(constoperator_type&f,constoperator_type&g){returnf+g;}// Mapping (sum + f * size)staticconstexprvalue_typemapping(constoperator_type&f,constvalue_type&x){return{x.sum+f*x.size,x.size};}// Helper for initializing a leaf nodestaticconstexprvalue_typemake(constT&val){return{val,1};}};}// namespace acted_monoid}// namespace m1une#line 1 "acted_monoid/range_affine_range_min_max.hpp"
#line 7 "acted_monoid/range_affine_range_min_max.hpp"
namespacem1une{namespaceacted_monoid{template<typenameT>structRangeAffineRangeMinMaxNode{Tmin_val;Tmax_val;};template<typenameT,TMinId=std::numeric_limits<T>::max(),TMaxId=std::numeric_limits<T>::lowest()>structRangeAffineRangeMinMax{usingvalue_type=RangeAffineRangeMinMaxNode<T>;usingoperator_type=std::pair<T,T>;staticconstexprboolcommutative=true;staticconstexprbooloperator_commutative=false;staticconstexprvalue_typeid(){return{MinId,MaxId};}staticconstexprvalue_typeop(constvalue_type&a,constvalue_type&b){return{std::min(a.min_val,b.min_val),std::max(a.max_val,b.max_val)};}staticconstexproperator_typeop_id(){return{T(1),T(0)};}staticconstexproperator_typeop_comp(constoperator_type&f,constoperator_type&g){return{f.first*g.first,f.first*g.second+f.second};}staticconstexprvalue_typemapping(constoperator_type&f,constvalue_type&x){if(x.min_val==MinId)returnx;Tv1=f.first*x.min_val+f.second;Tv2=f.first*x.max_val+f.second;if(f.first<0){return{v2,v1};}return{v1,v2};}staticconstexprvalue_typemake(constT&val){return{val,val};}};}// namespace acted_monoid}// namespace m1une#line 1 "acted_monoid/range_affine_range_sum.hpp"
#line 5 "acted_monoid/range_affine_range_sum.hpp"
namespacem1une{namespaceacted_monoid{template<typenameT>structRangeAffineRangeSumNode{Tsum;intsize;};// Designed to accept Modint or similar types as Ttemplate<typenameT>structRangeAffineRangeSum{usingvalue_type=RangeAffineRangeSumNode<T>;usingoperator_type=std::pair<T,T>;// {a, b} for ax + bstaticconstexprboolcommutative=true;staticconstexprbooloperator_commutative=false;// Value Monoidstaticconstexprvalue_typeid(){return{T(0),0};}staticconstexprvalue_typeop(constvalue_type&a,constvalue_type&b){return{a.sum+b.sum,a.size+b.size};}staticconstexprintsize(constvalue_type&value){returnvalue.size;}// Operator Monoid (Affine Composition)// f(x) = a1*x + b1, g(x) = a2*x + b2// f(g(x)) = a1*(a2*x + b2) + b1 = (a1*a2)*x + (a1*b2 + b1)staticconstexproperator_typeop_id(){return{T(1),T(0)};}staticconstexproperator_typeop_comp(constoperator_type&f,constoperator_type&g){return{f.first*g.first,f.first*g.second+f.second};}// Mapping// \sum (a*x_i + b) = a * \sum x_i + b * sizestaticconstexprvalue_typemapping(constoperator_type&f,constvalue_type&x){return{f.first*x.sum+f.second*T(x.size),x.size};}// Helper for initializing a leaf nodestaticconstexprvalue_typemake(constT&val){return{val,1};}};}// namespace acted_monoid}// namespace m1une#line 1 "acted_monoid/range_affine_range_sum_of_squares.hpp"
#line 5 "acted_monoid/range_affine_range_sum_of_squares.hpp"
namespacem1une{namespaceacted_monoid{template<typenameT>structRangeAffineRangeSumOfSquaresNode{Tsum_sq;Tsum;longlongsize;};// Designed to work with standard scalars or Modint typestemplate<typenameT>structRangeAffineRangeSumOfSquares{usingvalue_type=RangeAffineRangeSumOfSquaresNode<T>;usingoperator_type=std::pair<T,T>;// {a, b} for f(x) = a*x + bstaticconstexprboolcommutative=true;staticconstexprbooloperator_commutative=false;// Value Monoid (Sum of Squares, Sum, Size)staticconstexprvalue_typeid(){return{T(0),T(0),0};}staticconstexprvalue_typeop(constvalue_type&a,constvalue_type&b){return{a.sum_sq+b.sum_sq,a.sum+b.sum,a.size+b.size};}// Operator Monoid (Affine Composition)// f(x) = a1*x + b1, g(x) = a2*x + b2// f(g(x)) = a1*(a2*x + b2) + b1 = (a1*a2)*x + (a1*b2 + b1)staticconstexproperator_typeop_id(){return{T(1),T(0)};}staticconstexproperator_typeop_comp(constoperator_type&f,constoperator_type&g){return{f.first*g.first,f.first*g.second+f.second};}// Mapping// \sum (a*x_i + b)^2 = a^2 \sum x_i^2 + 2ab \sum x_i + b^2 * size// \sum (a*x_i + b) = a \sum x_i + b * sizestaticconstexprvalue_typemapping(constoperator_type&f,constvalue_type&x){if(x.size==0)returnx;Ta=f.first;Tb=f.second;Tsz=static_cast<T>(x.size);return{a*a*x.sum_sq+T(2)*a*b*x.sum+b*b*sz,a*x.sum+b*sz,x.size};}// Helper for initializing a leaf nodestaticconstexprvalue_typemake(constT&val){return{val*val,val,1};}};}// namespace acted_monoid}// namespace m1une#line 1 "acted_monoid/range_ap_add_range_sum.hpp"
#line 5 "acted_monoid/range_ap_add_range_sum.hpp"
namespacem1une{namespaceacted_monoid{template<typenameT>structRangeApAddRangeSumNode{Tsum;longlongsize;Tord_sum;};template<typenameT>structRangeApAddRangeSum{usingvalue_type=RangeApAddRangeSumNode<T>;usingoperator_type=std::pair<T,T>;// {a, b} for adding a * i + bstaticconstexprboolcommutative=false;staticconstexprbooloperator_commutative=true;// Value Monoid (Sum)staticconstexprvalue_typeid(){return{T(0),0,T(0)};}staticconstexprvalue_typeop(constvalue_type&a,constvalue_type&b){return{a.sum+b.sum,a.size+b.size,a.ord_sum+b.ord_sum+T(a.size)*T(b.size)};}// Operator Monoid (Add)staticconstexproperator_typeop_id(){return{T(0),T(0)};}staticconstexproperator_typeop_comp(constoperator_type&f,constoperator_type&g){return{f.first+g.first,f.second+g.second};}staticconstexprvalue_typemapping(constoperator_type&f,constvalue_type&x){returnmapping(f,x,0);}staticconstexprvalue_typemapping(constoperator_type&f,constvalue_type&x,longlongord){return{x.sum+f.first*(x.ord_sum+T(ord)*T(x.size))+f.second*T(x.size),x.size,x.ord_sum};}staticconstexproperator_typeop_shift(constoperator_type&f,longlongord){return{f.first,f.second+f.first*T(ord)};}staticconstexproperator_typeop_reverse(constoperator_type&f,longlongsize){return{-f.first,f.second+f.first*T(size-1)};}staticconstexprvalue_typemake(constT&val){return{val,1,T(0)};}};}// namespace acted_monoid}// namespace m1une#line 1 "acted_monoid/range_ap_update_range_min_max.hpp"
#line 6 "acted_monoid/range_ap_update_range_min_max.hpp"
#include<optional>
#line 8 "acted_monoid/range_ap_update_range_min_max.hpp"
namespacem1une{namespaceacted_monoid{template<typenameT>structRangeApUpdateRangeMinMaxNode{Tmin_val;Tmax_val;longlongsize;};template<typenameT,TMinId=std::numeric_limits<T>::max(),TMaxId=std::numeric_limits<T>::lowest()>structRangeApUpdateRangeMinMax{usingvalue_type=RangeApUpdateRangeMinMaxNode<T>;usingoperator_type=std::optional<std::pair<T,T>>;// {a, b} for setting to a * i + bstaticconstexprboolcommutative=true;staticconstexprbooloperator_commutative=false;// Value Monoid (Min & Max)staticconstexprvalue_typeid(){return{MinId,MaxId,0};}staticconstexprvalue_typeop(constvalue_type&a,constvalue_type&b){if(a.size==0)returnb;if(b.size==0)returna;return{std::min(a.min_val,b.min_val),std::max(a.max_val,b.max_val),a.size+b.size};}// Operator Monoid (Update)staticconstexproperator_typeop_id(){returnstd::nullopt;}staticconstexproperator_typeop_comp(constoperator_type&f,constoperator_type&g){// Newer operation (f) completely overwrites the older one (g)returnf.has_value()?f:g;}staticconstexprvalue_typemapping(constoperator_type&f,constvalue_type&x){returnmapping(f,x,0);}staticconstexprvalue_typemapping(constoperator_type&f,constvalue_type&x,longlongord){if(!f.has_value()||x.min_val==MinId)returnx;Ta=f.value().first;Tb=f.value().second;Tval_left=a*static_cast<T>(ord)+b;Tval_right=a*static_cast<T>(ord+x.size-1)+b;return{std::min(val_left,val_right),std::max(val_left,val_right),x.size};}staticconstexproperator_typeop_shift(constoperator_type&f,longlongord){if(!f.has_value())returnf;returnstd::pair<T,T>{f.value().first,f.value().second+f.value().first*T(ord)};}staticconstexproperator_typeop_reverse(constoperator_type&f,longlongsize){if(!f.has_value())returnf;returnstd::pair<T,T>{-f.value().first,f.value().second+f.value().first*T(size-1)};}staticconstexprvalue_typemake(constT&val){return{val,val,1};}};}// namespace acted_monoid}// namespace m1une#line 1 "acted_monoid/range_ap_update_range_sum.hpp"
#line 6 "acted_monoid/range_ap_update_range_sum.hpp"
namespacem1une{namespaceacted_monoid{template<typenameT>structRangeApUpdateRangeSumNode{Tsum;longlongsize;Tord_sum;};template<typenameT>structRangeApUpdateRangeSum{usingvalue_type=RangeApUpdateRangeSumNode<T>;usingoperator_type=std::optional<std::pair<T,T>>;// {a, b} for setting to a * i + bstaticconstexprboolcommutative=false;staticconstexprbooloperator_commutative=false;// Value Monoid (Sum)staticconstexprvalue_typeid(){return{T(0),0,T(0)};}staticconstexprvalue_typeop(constvalue_type&a,constvalue_type&b){return{a.sum+b.sum,a.size+b.size,a.ord_sum+b.ord_sum+T(a.size)*T(b.size)};}// Operator Monoid (Update)staticconstexproperator_typeop_id(){returnstd::nullopt;}staticconstexproperator_typeop_comp(constoperator_type&f,constoperator_type&g){// Prioritize the newer operation (f) over the older one (g)returnf.has_value()?f:g;}staticconstexprvalue_typemapping(constoperator_type&f,constvalue_type&x){returnmapping(f,x,0);}staticconstexprvalue_typemapping(constoperator_type&f,constvalue_type&x,longlongord){if(!f.has_value()||x.size==0)returnx;return{f.value().first*(x.ord_sum+T(ord)*T(x.size))+f.value().second*T(x.size),x.size,x.ord_sum};}staticconstexproperator_typeop_shift(constoperator_type&f,longlongord){if(!f.has_value())returnf;returnstd::pair<T,T>{f.value().first,f.value().second+f.value().first*T(ord)};}staticconstexproperator_typeop_reverse(constoperator_type&f,longlongsize){if(!f.has_value())returnf;returnstd::pair<T,T>{-f.value().first,f.value().second+f.value().first*T(size-1)};}staticconstexprvalue_typemake(constT&val){return{val,1,T(0)};}};}// namespace acted_monoid}// namespace m1une#line 1 "acted_monoid/range_bitwise_and_or_xor_range_sum.hpp"
#include<array>
#line 6 "acted_monoid/range_bitwise_and_or_xor_range_sum.hpp"
#include<type_traits>namespacem1une{namespaceacted_monoid{template<typenameT,intBITS>structRangeBitwiseAndOrXorRangeSumNode{Tsum;std::array<longlong,BITS>bit_count;longlongsize;};// Acted monoid for range bitwise AND, OR, and XOR updates and range sum queries.template<typenameT,intBITS=30>structRangeBitwiseAndOrXorRangeSum{static_assert(std::is_integral_v<T>&&!std::is_same_v<std::remove_cv_t<T>,bool>);static_assert(0<BITS&&BITS<=std::numeric_limits<T>::digits);usingvalue_type=RangeBitwiseAndOrXorRangeSumNode<T,BITS>;// Represents f(x) = (x & and_mask) ^ xor_mask on the lowest BITS bits.structoperator_type{Tand_mask;Txor_mask;};staticconstexprboolcommutative=true;staticconstexprbooloperator_commutative=false;staticconstexprTbit_mask(){ifconstexpr(std::is_unsigned_v<T>&&BITS==std::numeric_limits<T>::digits){return~T(0);}else{return(T(1)<<(BITS-1))|((T(1)<<(BITS-1))-1);}}staticconstexprvalue_typeid(){value_typeres;res.sum=T(0);res.bit_count.fill(0);res.size=0;returnres;}staticconstexprvalue_typeop(constvalue_type&a,constvalue_type&b){value_typeres;res.sum=a.sum+b.sum;res.size=a.size+b.size;for(inti=0;i<BITS;++i){res.bit_count[i]=a.bit_count[i]+b.bit_count[i];}returnres;}staticconstexproperator_typeop_id(){return{bit_mask(),T(0)};}// Returns f(g(x)).staticconstexproperator_typeop_comp(constoperator_type&f,constoperator_type&g){return{f.and_mask&g.and_mask,(g.xor_mask&f.and_mask)^f.xor_mask};}staticconstexprvalue_typemapping(constoperator_type&f,constvalue_type&x){value_typeres=x;res.sum=T(0);for(inti=0;i<BITS;++i){longlongcount=((f.and_mask>>i)&T(1))?x.bit_count[i]:0;if((f.xor_mask>>i)&T(1))count=x.size-count;res.bit_count[i]=count;res.sum+=static_cast<T>(count)*(T(1)<<i);}returnres;}staticconstexprvalue_typemake(constT&value){value_typeres;res.sum=value;res.size=1;for(inti=0;i<BITS;++i){res.bit_count[i]=(value>>i)&T(1);}returnres;}staticconstexproperator_typemake_and(constT&mask){return{mask&bit_mask(),T(0)};}staticconstexproperator_typemake_or(constT&mask){Tnormalized=mask&bit_mask();return{bit_mask()^normalized,normalized};}staticconstexproperator_typemake_xor(constT&mask){return{bit_mask(),mask&bit_mask()};}};}// namespace acted_monoid}// namespace m1une#line 1 "acted_monoid/range_flip_range_binary_inversion.hpp"
#line 1 "monoid/binary_inversion.hpp"
namespacem1une{namespacemonoid{template<typenameT=longlong>structBinaryInversionNode{longlongzeros;longlongones;Tinversions;};// Monoid for counting zeros, ones, and inversions (1s before 0s) in a binary array.template<typenameT=longlong>structBinaryInversion{usingvalue_type=BinaryInversionNode<T>;staticconstexprboolcommutative=false;// The identity element has 0 zeros, 0 ones, and 0 inversions.staticconstexprvalue_typeid(){return{0,0,0};}// Merges two segments and calculates the new inversions.// New inversions = left inversions + right inversions + (ones in left * zeros in right)staticconstexprvalue_typeop(constvalue_type&a,constvalue_type&b){return{a.zeros+b.zeros,a.ones+b.ones,a.inversions+b.inversions+a.ones*b.zeros};}// Helper to securely create a leaf node from a value (0 or 1).staticconstexprvalue_typemake(intval){if(val==0)return{1,0,0};return{0,1,0};}};}// namespace monoid}// namespace m1une#line 5 "acted_monoid/range_flip_range_binary_inversion.hpp"
namespacem1une{namespaceacted_monoid{template<typenameT=longlong>structRangeFlipRangeBinaryInversion{usingvalue_type=m1une::monoid::BinaryInversionNode<T>;usingoperator_type=bool;staticconstexprboolcommutative=false;staticconstexprbooloperator_commutative=true;staticconstexprvalue_typeid(){return{0,0,0};}staticconstexprvalue_typeop(constvalue_type&a,constvalue_type&b){return{a.zeros+b.zeros,a.ones+b.ones,a.inversions+b.inversions+a.ones*b.zeros};}staticconstexproperator_typeop_id(){returnfalse;}staticconstexproperator_typeop_comp(constoperator_type&f,constoperator_type&g){returnf^g;}staticconstexprvalue_typemapping(constoperator_type&f,constvalue_type&x){if(!f)returnx;return{x.ones,x.zeros,x.zeros*x.ones-x.inversions};}staticconstexprvalue_typemake(intval){if(val==0)return{1,0,0};return{0,1,0};}};}// namespace acted_monoid}// namespace m1une#line 1 "acted_monoid/range_flip_range_sum.hpp"
namespacem1une{namespaceacted_monoid{template<typenameT>structRangeFlipRangeSumNode{Tsum;longlongsize;};// Acted Monoid for binary arrays (0s and 1s).// Supports range bit inversion (flip) and range sum queries.template<typenameT=longlong>structRangeFlipRangeSum{usingvalue_type=RangeFlipRangeSumNode<T>;usingoperator_type=bool;// 'true' means flip the bits in the rangestaticconstexprboolcommutative=true;staticconstexprbooloperator_commutative=true;staticconstexprvalue_typeid(){return{T(0),0};}staticconstexprvalue_typeop(constvalue_type&a,constvalue_type&b){return{a.sum+b.sum,a.size+b.size};}staticconstexproperator_typeop_id(){returnfalse;}staticconstexproperator_typeop_comp(constoperator_type&f,constoperator_type&g){returnf^g;}staticconstexprvalue_typemapping(constoperator_type&f,constvalue_type&x){if(!f||x.size==0)returnx;// If flipped, the new number of 1s is exactly (Total Elements - Old number of 1s)return{static_cast<T>(x.size)-x.sum,x.size};}// Initialize with a 0 or 1staticconstexprvalue_typemake(constT&val){return{val,1};}};}// namespace acted_monoid}// namespace m1une#line 1 "acted_monoid/range_mul_range_sum.hpp"
namespacem1une{namespaceacted_monoid{// Acted Monoid for Range Multiplication and Range Sum queries.// Operates natively on scalars or Modint classes without needing to track segment size.template<typenameT>structRangeMulRangeSum{usingvalue_type=T;usingoperator_type=T;staticconstexprboolcommutative=true;staticconstexprbooloperator_commutative=true;// Value Monoid (Sum)staticconstexprvalue_typeid(){returnT(0);}staticconstexprvalue_typeop(constvalue_type&a,constvalue_type&b){returna+b;}// Operator Monoid (Multiply)staticconstexproperator_typeop_id(){returnT(1);}staticconstexproperator_typeop_comp(constoperator_type&f,constoperator_type&g){returnf*g;}// Mapping: Distribution Property ( f * (a+b) = f*a + f*b )staticconstexprvalue_typemapping(constoperator_type&f,constvalue_type&x){returnf*x;}// Helper for initializing a leaf nodestaticconstexprvalue_typemake(constT&val){returnval;}};}// namespace acted_monoid}// namespace m1une#line 1 "acted_monoid/range_or_range_sum.hpp"
#line 5 "acted_monoid/range_or_range_sum.hpp"
namespacem1une{namespaceacted_monoid{template<typenameT,intBITS=30>structRangeOrRangeSumNode{Tsum;std::array<int,BITS>bit_count;longlongsize;};// Acted Monoid for Range OR updates and Range Sum queries.template<typenameT,intBITS=30>structRangeOrRangeSum{usingvalue_type=RangeOrRangeSumNode<T,BITS>;usingoperator_type=T;staticconstexprboolcommutative=true;staticconstexprbooloperator_commutative=true;staticconstexprvalue_typeid(){value_typeres;res.sum=T(0);res.bit_count.fill(0);res.size=0;returnres;}staticconstexprvalue_typeop(constvalue_type&a,constvalue_type&b){value_typeres;res.sum=a.sum+b.sum;res.size=a.size+b.size;for(inti=0;i<BITS;++i){res.bit_count[i]=a.bit_count[i]+b.bit_count[i];}returnres;}staticconstexproperator_typeop_id(){returnT(0);}staticconstexproperator_typeop_comp(constoperator_type&f,constoperator_type&g){returnf|g;}staticconstexprvalue_typemapping(constoperator_type&f,constvalue_type&x){if(f==T(0)||x.size==0)returnx;value_typeres=x;res.sum=T(0);for(inti=0;i<BITS;++i){if((f>>i)&1){res.bit_count[i]=x.size;// OR forces the bit to be 1 for all elements}res.sum+=static_cast<T>(res.bit_count[i])*(T(1)<<i);}returnres;}staticconstexprvalue_typemake(constT&val){value_typeres;res.sum=val;res.size=1;for(inti=0;i<BITS;++i){res.bit_count[i]=((val>>i)&1)?1:0;}returnres;}};}// namespace acted_monoid}// namespace m1une#line 1 "acted_monoid/range_update_range_longest_true.hpp"
#line 5 "acted_monoid/range_update_range_longest_true.hpp"
#line 1 "monoid/longest_true.hpp"
#line 5 "monoid/longest_true.hpp"
namespacem1une{namespacemonoid{structLongestTrueNode{intlen;intmax_len;intl_len;intr_len;};// Monoid for finding the maximum length of a contiguous subarray// where all elements satisfy a certain condition (i.e., are "true").structLongestTrue{usingvalue_type=LongestTrueNode;staticconstexprboolcommutative=false;// The identity element represents an empty array.staticconstexprvalue_typeid(){return{0,0,0,0};}// Merges two segments.staticconstexprvalue_typeop(constvalue_type&a,constvalue_type&b){if(a.len==0)returnb;if(b.len==0)returna;value_typeres;res.len=a.len+b.len;res.max_len=std::max({a.max_len,b.max_len,a.r_len+b.l_len});res.l_len=a.l_len;if(a.len==a.l_len)res.l_len+=b.l_len;res.r_len=b.r_len;if(b.len==b.r_len)res.r_len+=a.r_len;returnres;}// Helper to securely create a leaf node from a boolean condition.staticconstexprvalue_typemake(boolval){return{1,val?1:0,val?1:0,val?1:0};}};}// namespace monoid}// namespace m1une#line 7 "acted_monoid/range_update_range_longest_true.hpp"
namespacem1une{namespaceacted_monoid{structRangeUpdateRangeLongestTrue{usingBaseMonoid=m1une::monoid::LongestTrue;usingvalue_type=typenameBaseMonoid::value_type;usingoperator_type=std::optional<bool>;staticconstexprboolcommutative=false;staticconstexprbooloperator_commutative=false;// Value Monoidstaticconstexprvalue_typeid(){returnBaseMonoid::id();}staticconstexprvalue_typeop(constvalue_type&a,constvalue_type&b){returnBaseMonoid::op(a,b);}// Operator Monoid (Update/Overwrite)staticconstexproperator_typeop_id(){returnstd::nullopt;}staticconstexproperator_typeop_comp(constoperator_type&f,constoperator_type&g){returnf.has_value()?f:g;}// Mappingstaticconstexprvalue_typemapping(constoperator_type&f,constvalue_type&x){if(!f.has_value())returnx;boolv=f.value();// If updating to 'true', the entire length satisfies the condition.// If updating to 'false', zero elements satisfy the condition.return{x.len,v?x.len:0,v?x.len:0,v?x.len:0};}// Helper for initializing a leaf nodestaticconstexprvalue_typemake(boolval){returnBaseMonoid::make(val);}};}// namespace acted_monoid}// namespace m1une#line 1 "acted_monoid/range_update_range_max.hpp"
#line 7 "acted_monoid/range_update_range_max.hpp"
namespacem1une{namespaceacted_monoid{template<typenameT,TId=std::numeric_limits<T>::lowest()>structRangeUpdateRangeMax{usingvalue_type=T;usingoperator_type=std::optional<T>;staticconstexprboolcommutative=true;staticconstexprbooloperator_commutative=false;// Value Monoid (Max)staticconstexprvalue_typeid(){returnId;}staticconstexprvalue_typeop(constvalue_type&a,constvalue_type&b){returnstd::max(a,b);}// Operator Monoid (Update)staticconstexproperator_typeop_id(){returnstd::nullopt;}staticconstexproperator_typeop_comp(constoperator_type&f,constoperator_type&g){// Prioritize the newer operation (f) over the older one (g)returnf.has_value()?f:g;}// Mappingstaticconstexprvalue_typemapping(constoperator_type&f,constvalue_type&x){if(!f.has_value()||x==id())returnx;returnf.value();}};}// namespace acted_monoid}// namespace m1une#line 1 "acted_monoid/range_update_range_max_subarray.hpp"
#line 6 "acted_monoid/range_update_range_max_subarray.hpp"
namespacem1une{namespaceacted_monoid{template<typenameT>structRangeUpdateRangeMaxSubarrayNode{Tsum,pref,suff,max_sub;longlongsize;};// Acted Monoid for Range Assignment (Update) and Max Contiguous Subarray Sum.// Note: This implementation assumes empty subarrays are allowed (max sum is at least 0).template<typenameT>structRangeUpdateRangeMaxSubarray{usingvalue_type=RangeUpdateRangeMaxSubarrayNode<T>;usingoperator_type=std::optional<T>;staticconstexprboolcommutative=false;staticconstexprbooloperator_commutative=false;staticconstexprvalue_typeid(){return{T(0),T(0),T(0),T(0),0};}staticconstexprvalue_typeop(constvalue_type&a,constvalue_type&b){if(a.size==0)returnb;if(b.size==0)returna;value_typeres;res.sum=a.sum+b.sum;res.pref=std::max(a.pref,a.sum+b.pref);res.suff=std::max(b.suff,b.sum+a.suff);res.max_sub=std::max({a.max_sub,b.max_sub,a.suff+b.pref});res.size=a.size+b.size;returnres;}staticconstexproperator_typeop_id(){returnstd::nullopt;}staticconstexproperator_typeop_comp(constoperator_type&f,constoperator_type&g){returnf?f:g;// left-biased because new updates override old ones}staticconstexprvalue_typemapping(constoperator_type&f,constvalue_type&x){if(!f||x.size==0)returnx;value_typeres;res.sum=(*f)*x.size;Tmax_val=std::max(T(0),res.sum);// If empty subarrays are NOT allowed, change to: T max_val = (*f) > 0 ? res.sum : (*f);res.pref=res.suff=res.max_sub=max_val;res.size=x.size;returnres;}staticconstexprvalue_typemake(constT&val){Tmax_val=std::max(T(0),val);return{val,max_val,max_val,max_val,1};}};}// namespace acted_monoid}// namespace m1une#line 1 "acted_monoid/range_update_range_min.hpp"
#line 7 "acted_monoid/range_update_range_min.hpp"
namespacem1une{namespaceacted_monoid{template<typenameT,TId=std::numeric_limits<T>::max()>structRangeUpdateRangeMin{usingvalue_type=T;usingoperator_type=std::optional<T>;staticconstexprboolcommutative=true;staticconstexprbooloperator_commutative=false;// Value Monoid (Min)staticconstexprvalue_typeid(){returnId;}staticconstexprvalue_typeop(constvalue_type&a,constvalue_type&b){returnstd::min(a,b);}// Operator Monoid (Update)staticconstexproperator_typeop_id(){returnstd::nullopt;}staticconstexproperator_typeop_comp(constoperator_type&f,constoperator_type&g){// Prioritize the newer operation (f) over the older one (g)returnf.has_value()?f:g;}// Mappingstaticconstexprvalue_typemapping(constoperator_type&f,constvalue_type&x){if(!f.has_value()||x==id())returnx;returnf.value();}};}// namespace acted_monoid}// namespace m1une#line 1 "acted_monoid/range_update_range_product.hpp"
#line 5 "acted_monoid/range_update_range_product.hpp"
#line 1 "monoid/concept.hpp"
#line 5 "monoid/concept.hpp"
namespacem1une{namespacemonoid{// Concept to check if a type satisfies the requirements of a Monoid.// A Monoid must have a `value_type`, an identity element `id()`, and an associative binary operation `op()`.template<typenameM>conceptIsMonoid=requires(typenameM::value_typea,typenameM::value_typeb){// 1. Must define `value_type`typenameM::value_type;// 2. Must have a static method `id()` returning `value_type`{M::id()}->std::same_as<typenameM::value_type>;// 3. Must have a static method `op(a, b)` returning `value_type`{M::op(a,b)}->std::same_as<typenameM::value_type>;};// Concept for groups. A type satisfying this concept must also obey the group// laws; concepts can check the interface but not the algebraic properties.template<typenameM>conceptIsGroup=IsMonoid<M>&&requires(typenameM::value_typea){{M::inv(a)}->std::same_as<typenameM::value_type>;};// Concept for commutative groups. Commutativity is a semantic requirement and// cannot be checked by a C++ concept.template<typenameM>conceptIsCommutativeGroup=IsGroup<M>;}// namespace monoid}// namespace m1une#line 1 "monoid/power.hpp"
#line 5 "monoid/power.hpp"
namespacem1une{namespacemonoid{// Computes a^n (a * a * ... * a, n times) for an element 'a' in Monoid 'M'.// Uses binary exponentiation to achieve O(log n) time complexity.// The template parameter 'M' is constrained by the 'IsMonoid' concept.template<IsMonoidM>constexprtypenameM::value_typepower(typenameM::value_typea,longlongn){typenameM::value_typeres=M::id();while(n>0){if(n&1){res=M::op(res,a);}a=M::op(a,a);n>>=1;}returnres;}}// namespace monoid}// namespace m1une#line 8 "acted_monoid/range_update_range_product.hpp"
namespacem1une{namespaceacted_monoid{template<m1une::monoid::IsMonoidMonoid>structRangeUpdateRangeProductNode{usingbase_type=typenameMonoid::value_type;base_typeproduct;longlongsize;};// Range assignment and range product for an arbitrary, possibly// noncommutative, monoid.template<m1une::monoid::IsMonoidMonoid>structRangeUpdateRangeProduct{usingbase_type=typenameMonoid::value_type;usingvalue_type=RangeUpdateRangeProductNode<Monoid>;usingoperator_type=std::optional<base_type>;staticconstexprboolcommutative=[]{ifconstexpr(requires{Monoid::commutative;}){returnbool(Monoid::commutative);}else{returnfalse;}}();staticconstexprbooloperator_commutative=false;staticconstexprvalue_typeid(){return{Monoid::id(),0};}staticconstexprvalue_typeop(constvalue_type&a,constvalue_type&b){return{Monoid::op(a.product,b.product),a.size+b.size};}staticconstexproperator_typeop_id(){returnstd::nullopt;}staticconstexproperator_typeop_comp(constoperator_type&f,constoperator_type&g){returnf.has_value()?f:g;}staticconstexprvalue_typemapping(constoperator_type&f,constvalue_type&x){if(!f.has_value()||x.size==0)returnx;return{m1une::monoid::power<Monoid>(f.value(),x.size),x.size};}staticconstexprvalue_typemake(constbase_type&value){return{value,1};}};}// namespace acted_monoid}// namespace m1une#line 1 "acted_monoid/range_update_range_sum.hpp"
#line 5 "acted_monoid/range_update_range_sum.hpp"
namespacem1une{namespaceacted_monoid{template<typenameT>structRangeUpdateRangeSumNode{Tsum;longlongsize;};template<typenameT>structRangeUpdateRangeSum{usingvalue_type=RangeUpdateRangeSumNode<T>;usingoperator_type=std::optional<T>;staticconstexprboolcommutative=true;staticconstexprbooloperator_commutative=false;staticconstexprvalue_typeid(){return{T(0),0};}staticconstexprvalue_typeop(constvalue_type&a,constvalue_type&b){return{a.sum+b.sum,a.size+b.size};}staticconstexproperator_typeop_id(){returnstd::nullopt;}staticconstexproperator_typeop_comp(constoperator_type&f,constoperator_type&g){returnf.has_value()?f:g;}staticconstexprvalue_typemapping(constoperator_type&f,constvalue_type&x){if(!f.has_value()||x.size==0)returnx;return{f.value()*static_cast<T>(x.size),x.size};}staticconstexprvalue_typemake(constT&val){return{val,1};}};}// namespace acted_monoid}// namespace m1une#line 1 "acted_monoid/range_xor_range_sum.hpp"
#line 5 "acted_monoid/range_xor_range_sum.hpp"
namespacem1une{namespaceacted_monoid{template<typenameT,intBITS=30>structRangeXorRangeSumNode{Tsum;std::array<int,BITS>bit_count;longlongsize;};// Acted Monoid for Range XOR updates and Range Sum queries.// BITS defines the maximum bit length (default 30 for standard integers, use 60 for long long).template<typenameT,intBITS=30>structRangeXorRangeSum{usingvalue_type=RangeXorRangeSumNode<T,BITS>;usingoperator_type=T;staticconstexprboolcommutative=true;staticconstexprbooloperator_commutative=true;staticconstexprvalue_typeid(){value_typeres;res.sum=T(0);res.bit_count.fill(0);res.size=0;returnres;}staticconstexprvalue_typeop(constvalue_type&a,constvalue_type&b){value_typeres;res.sum=a.sum+b.sum;res.size=a.size+b.size;for(inti=0;i<BITS;++i){res.bit_count[i]=a.bit_count[i]+b.bit_count[i];}returnres;}staticconstexproperator_typeop_id(){returnT(0);}staticconstexproperator_typeop_comp(constoperator_type&f,constoperator_type&g){returnf^g;}staticconstexprvalue_typemapping(constoperator_type&f,constvalue_type&x){if(f==T(0)||x.size==0)returnx;value_typeres=x;res.sum=T(0);for(inti=0;i<BITS;++i){if((f>>i)&1){res.bit_count[i]=x.size-x.bit_count[i];}res.sum+=static_cast<T>(res.bit_count[i])*(T(1)<<i);}returnres;}staticconstexprvalue_typemake(constT&val){value_typeres;res.sum=val;res.size=1;for(inti=0;i<BITS;++i){res.bit_count[i]=((val>>i)&1)?1:0;}returnres;}};}// namespace acted_monoid}// namespace m1une#line 1 "acted_monoid/range_xor_range_xor.hpp"
namespacem1une{namespaceacted_monoid{template<typenameT>structRangeXorRangeXorNode{Tval;longlongsize;};template<typenameT>structRangeXorRangeXor{usingvalue_type=RangeXorRangeXorNode<T>;usingoperator_type=T;staticconstexprboolcommutative=true;staticconstexprbooloperator_commutative=true;staticconstexprvalue_typeid(){return{T(0),0};}staticconstexprvalue_typeop(constvalue_type&a,constvalue_type&b){return{a.val^b.val,a.size+b.size};}staticconstexprvalue_typeinv(constvalue_type&x){return{x.val,-x.size};}staticconstexproperator_typeop_id(){returnT(0);}staticconstexproperator_typeop_comp(constoperator_type&f,constoperator_type&g){returnf^g;}staticconstexprvalue_typemapping(constoperator_type&f,constvalue_type&x){if(x.size%2!=0){return{x.val^f,x.size};}returnx;}staticconstexprvalue_typemake(constT&val){return{val,1};}};}// namespace acted_monoid}// namespace m1une#line 1 "acted_monoid/wrapper.hpp"
namespacem1une{namespaceacted_monoid{// Wrapper struct to generate an Acted Monoid using Non-Type Template Parameters (NTTP).// Useful for quickly defining acted monoids using callables supplied as NTTPs during contests.template<typenameT,typenameE,autoOp,autoId,autoOpComp,autoOpId,autoMapping,boolCommutative=false,boolOperatorCommutative=false>structWrapper{usingvalue_type=T;usingoperator_type=E;staticconstexprboolcommutative=Commutative;staticconstexprbooloperator_commutative=OperatorCommutative;// Returns the identity element of the value monoid.staticconstexprTid(){returnId();}// Returns the result of the value monoid binary operation.staticconstexprTop(constT&a,constT&b){returnOp(a,b);}// Returns the identity element of the operator monoid.staticconstexprEop_id(){returnOpId();}// Composes two operations f and g (corresponds to f(g(x))).staticconstexprEop_comp(constE&f,constE&g){returnOpComp(f,g);}// Applies the operator f onto the value x.staticconstexprTmapping(constE&f,constT&x){returnMapping(f,x);}};}// namespace acted_monoid}// namespace m1une#line 1 "beats_acted_monoid/concept.hpp"
#line 5 "beats_acted_monoid/concept.hpp"
#line 7 "beats_acted_monoid/concept.hpp"
namespacem1une{namespacebeats_acted_monoid{// An acted monoid whose action may require descent before it can be applied.template<typenameAM>conceptIsBeatsActedMonoid=m1une::acted_monoid::IsActedMonoid<AM>&&requires(typenameAM::value_typex,typenameAM::operator_typef){{AM::can_apply(f,x)}->std::same_as<bool>;};}// namespace beats_acted_monoid}// namespace m1une#line 1 "beats_acted_monoid/wrapper.hpp"
#line 5 "beats_acted_monoid/wrapper.hpp"
namespacem1une{namespacebeats_acted_monoid{// Wrapper for defining a Beats acted monoid with callables supplied as NTTPs.template<typenameT,typenameE,autoOp,autoId,autoOpComp,autoOpId,autoMapping,autoCanApply,autoMake=nullptr,autoMakeAt=nullptr,autoMappingAt=nullptr,autoCanApplyAt=nullptr,autoOpShift=nullptr,boolCommutative=false,boolOperatorCommutative=false>structWrapper{usingvalue_type=T;usingoperator_type=E;staticconstexprboolcommutative=Commutative;staticconstexprbooloperator_commutative=OperatorCommutative;staticconstexprTid(){returnId();}staticconstexprTop(constT&lhs,constT&rhs){returnOp(lhs,rhs);}staticconstexprEop_id(){returnOpId();}staticconstexprEop_comp(constE&f,constE&g){returnOpComp(f,g);}staticconstexprTmapping(constE&f,constT&x){returnMapping(f,x);}staticconstexprboolcan_apply(constE&f,constT&x){returnCanApply(f,x);}template<typenameU>requiresrequires(constU&value){{Make(value)}->std::convertible_to<T>;}staticconstexprTmake(constU&value){returnMake(value);}template<typenameU>requiresrequires(constU&value,intindex){{MakeAt(value,index)}->std::convertible_to<T>;}staticconstexprTmake(constU&value,intindex){returnMakeAt(value,index);}staticconstexprTmapping(constE&f,constT&x,longlongordinal)requiresrequires{{MappingAt(f,x,ordinal)}->std::convertible_to<T>;}{returnMappingAt(f,x,ordinal);}staticconstexprboolcan_apply(constE&f,constT&x,longlongordinal)requiresrequires{{CanApplyAt(f,x,ordinal)}->std::convertible_to<bool>;}{returnCanApplyAt(f,x,ordinal);}staticconstexprEop_shift(constE&f,longlongordinal)requiresrequires{{OpShift(f,ordinal)}->std::convertible_to<E>;}{returnOpShift(f,ordinal);}};}// namespace beats_acted_monoid}// namespace m1une#line 1 "monoid/add.hpp"
namespacem1une{namespacemonoid{// Monoid for addition (Range Sum).template<typenameT>structAdd{usingvalue_type=T;staticconstexprboolcommutative=true;// Returns the identity element for addition, which is 0.staticconstexprTid(){returnT(0);}// Returns the sum of a and b.staticconstexprTop(constT&a,constT&b){returna+b;}staticconstexprTinv(constT&x){return-x;}};}// namespace monoid}// namespace m1une#line 1 "monoid/affine.hpp"
#line 5 "monoid/affine.hpp"
namespacem1une{namespacemonoid{// Monoid for affine transformations f(x) = ax + b.// Represented as a pair {a, b}.template<typenameT>structAffine{usingvalue_type=std::pair<T,T>;staticconstexprboolcommutative=false;// The identity transformation is f(x) = 1*x + 0.staticconstexprvalue_typeid(){return{T(1),T(0)};}// Composes two affine transformations.// f(g(x)) where f = a, g = b.// a.first * (b.first * x + b.second) + a.second// = (a.first * b.first) * x + (a.first * b.second + a.second)staticconstexprvalue_typeop(constvalue_type&a,constvalue_type&b){return{a.first*b.first,a.first*b.second+a.second};}// Helpers to create common affine transformationsstaticconstexprvalue_typemake_add(constT&b){return{T(1),b};}staticconstexprvalue_typemake_mul(constT&a){return{a,T(0)};}staticconstexprvalue_typemake_assign(constT&b){return{T(0),b};}};}// namespace monoid}// namespace m1une#line 1 "monoid/and.hpp"
namespacem1une{namespacemonoid{// Monoid for bitwise AND (Range AND).// ~T(0) sets all bits to 1, acting as the identity for bitwise AND.template<typenameT>structAnd{usingvalue_type=T;staticconstexprboolcommutative=true;// The identity element for bitwise AND is all bits set to 1.staticconstexprTid(){return~T(0);}// Returns the bitwise AND of a and b.staticconstexprTop(constT&a,constT&b){returna&b;}};}// namespace monoid}// namespace m1une#line 1 "monoid/arg_max.hpp"
#line 6 "monoid/arg_max.hpp"
#line 8 "monoid/arg_max.hpp"
namespacem1une{namespacemonoid{// Monoid for finding the maximum value and its corresponding index.// Defined as a type alias of ArgMin using std::greater.template<typenameT,TId=std::numeric_limits<T>::lowest()>usingArgMax=ArgMin<T,Id,std::greater<T>>;}// namespace monoid}// namespace m1une#line 1 "monoid/bottom_k.hpp"
#line 5 "monoid/bottom_k.hpp"
#line 1 "monoid/top_k.hpp"
#line 6 "monoid/top_k.hpp"
#include<vector>namespacem1une{namespacemonoid{// Monoid for finding the top/bottom K elements in a range.// The elements must be stored in the order defined by the Compare functor.// Default Compare is std::greater<T> (i.e., descending order for Top K).template<typenameT,intK,typenameCompare=std::greater<T>>structTopK{usingvalue_type=std::vector<T>;staticconstexprboolcommutative=true;// The identity element is an empty vector.staticconstexprvalue_typeid(){returnstd::vector<T>();}// Merges two sorted vectors and keeps only the first K elements.staticconstexprvalue_typeop(constvalue_type&a,constvalue_type&b){value_typeres;res.reserve(std::min(K,(int)(a.size()+b.size())));inti=0,j=0;while(res.size()<(std::size_t)K&&(i<(int)a.size()||j<(int)b.size())){if(i==(int)a.size()){res.push_back(b[j++]);}elseif(j==(int)b.size()){res.push_back(a[i++]);}elseif(Compare()(a[i],b[j])){res.push_back(a[i++]);}else{res.push_back(b[j++]);}}returnres;}// Helper to securely create a leaf node from a single value.staticconstexprvalue_typemake(constT&val){return{val};}};}// namespace monoid}// namespace m1une#line 7 "monoid/bottom_k.hpp"
namespacem1une{namespacemonoid{// Monoid for finding the bottom K (smallest) elements in a range.// Defined as a type alias of TopK using std::less.template<typenameT,intK>usingBottomK=TopK<T,K,std::less<T>>;}// namespace monoid}// namespace m1une#line 1 "monoid/bracket.hpp"
#line 5 "monoid/bracket.hpp"
namespacem1une{namespacemonoid{structBracketNode{intmatched;intunmatched_right;// Count of unmatched ')'intunmatched_left;// Count of unmatched '('};// Monoid for matching parentheses (Bracket Sequences).structBracket{usingvalue_type=BracketNode;staticconstexprboolcommutative=false;// The identity element is an empty sequence.staticconstexprvalue_typeid(){return{0,0,0};}// Merges two bracket sequences.// The unmatched '(' from the left perfectly matches the unmatched ')' from the right.staticconstexprvalue_typeop(constvalue_type&a,constvalue_type&b){intmatch=std::min(a.unmatched_left,b.unmatched_right);return{a.matched+b.matched+match,a.unmatched_right+b.unmatched_right-match,a.unmatched_left+b.unmatched_left-match};}// Helper to securely create a leaf node from a single character.staticconstexprvalue_typemake(charc){if(c=='(')return{0,0,1};if(c==')')return{0,1,0};return{0,0,0};}};}// namespace monoid}// namespace m1une#line 1 "monoid/gcd.hpp"
#include<numeric>namespacem1une{namespacemonoid{// Monoid for Greatest Common Divisor (Range GCD).template<typenameT>structGcd{usingvalue_type=T;staticconstexprboolcommutative=true;// The identity element for GCD is 0.staticconstexprTid(){returnT(0);}// Returns the greatest common divisor of a and b.staticconstexprTop(constT&a,constT&b){returnstd::gcd(a,b);}};}// namespace monoid}// namespace m1une#line 1 "monoid/longest_same.hpp"
#line 5 "monoid/longest_same.hpp"
namespacem1une{namespacemonoid{template<typenameT>structLongestSameNode{intlen;intmax_len;Tl_val;intl_len;Tr_val;intr_len;};// Monoid for finding the maximum length of a contiguous subarray// where all elements have the same value.template<typenameT>structLongestSame{usingvalue_type=LongestSameNode<T>;staticconstexprboolcommutative=false;// The identity element represents an empty array.staticconstexprvalue_typeid(){return{0,0,T(),0,T(),0};}// Merges two segments.staticconstexprvalue_typeop(constvalue_type&a,constvalue_type&b){if(a.len==0)returnb;if(b.len==0)returna;value_typeres;res.len=a.len+b.len;res.max_len=std::max(a.max_len,b.max_len);if(a.r_val==b.l_val){res.max_len=std::max(res.max_len,a.r_len+b.l_len);}res.l_val=a.l_val;res.l_len=a.l_len;if(a.len==a.l_len&&a.l_val==b.l_val){res.l_len+=b.l_len;}res.r_val=b.r_val;res.r_len=b.r_len;if(b.len==b.r_len&&b.r_val==a.r_val){res.r_len+=a.r_len;}returnres;}// Helper to securely create a leaf node from a single value.staticconstexprvalue_typemake(constT&val){return{1,1,val,1,val,1};}};}// namespace monoid}// namespace m1une#line 1 "monoid/matrix.hpp"
#line 5 "monoid/matrix.hpp"
namespacem1une{namespacemonoid{// Monoid for fixed-size square matrix multiplication.template<typenameT,intN>structMatrix{usingvalue_type=std::array<std::array<T,N>,N>;staticconstexprboolcommutative=false;// The identity element is the identity matrix.staticconstexprvalue_typeid(){value_typeres{};for(inti=0;i<N;++i){res[i][i]=T(1);}returnres;}// Multiplies two matrices: a * bstaticconstexprvalue_typeop(constvalue_type&a,constvalue_type&b){value_typeres{};for(inti=0;i<N;++i){for(intk=0;k<N;++k){for(intj=0;j<N;++j){res[i][j]+=a[i][k]*b[k][j];}}}returnres;}};}// namespace monoid}// namespace m1une#line 1 "monoid/max.hpp"
#line 6 "monoid/max.hpp"
namespacem1une{namespacemonoid{// Monoid for maximum (Range Maximum).// The identity element defaults to the lowest possible value of type T, but can be overridden.template<typenameT,TId=std::numeric_limits<T>::lowest()>structMax{usingvalue_type=T;staticconstexprboolcommutative=true;// Returns the identity element for maximum.staticconstexprTid(){returnId;}// Returns the maximum of a and b.staticconstexprTop(constT&a,constT&b){returnstd::max(a,b);}};}// namespace monoid}// namespace m1une#line 1 "monoid/max_count.hpp"
#line 6 "monoid/max_count.hpp"
#line 8 "monoid/max_count.hpp"
namespacem1une{namespacemonoid{// Monoid for finding the maximum value and its frequency in a range.// Defined as a type alias of MinCount using std::greater.template<typenameT,TId=std::numeric_limits<T>::lowest()>usingMaxCount=MinCount<T,Id,std::greater<T>>;}// namespace monoid}// namespace m1une#line 1 "monoid/max_plus_matrix.hpp"
#line 7 "monoid/max_plus_matrix.hpp"
namespacem1une{namespacemonoid{// Monoid for fixed-size square matrix multiplication over the Max-Plus semiring.// Useful for Dynamic DP (Maximization) and Longest Path problems.template<typenameT,intN,TMinInf=std::numeric_limits<T>::lowest()/2>structMaxPlusMatrix{usingvalue_type=std::array<std::array<T,N>,N>;staticconstexprboolcommutative=false;// The identity matrix for max-plus algebra.// Diagonal elements are 0 (identity for addition).// Off-diagonal elements are MinInf (identity for max).staticconstexprvalue_typeid(){value_typeres{};for(inti=0;i<N;++i){for(intj=0;j<N;++j){res[i][j]=(i==j)?T(0):MinInf;}}returnres;}// Multiplies two max-plus matrices: c_{i, j} = max_k (a_{i, k} + b_{k, j})staticconstexprvalue_typeop(constvalue_type&a,constvalue_type&b){value_typeres{};for(inti=0;i<N;++i){for(intj=0;j<N;++j){res[i][j]=MinInf;}}for(inti=0;i<N;++i){for(intk=0;k<N;++k){if(a[i][k]==MinInf)continue;for(intj=0;j<N;++j){if(b[k][j]==MinInf)continue;res[i][j]=std::max(res[i][j],a[i][k]+b[k][j]);}}}returnres;}// Helper to securely create a matrix initialized with MinInf.staticconstexprvalue_typemake_inf(){value_typeres{};for(inti=0;i<N;++i){for(intj=0;j<N;++j){res[i][j]=MinInf;}}returnres;}};}// namespace monoid}// namespace m1une#line 1 "monoid/max_subarray.hpp"
#line 6 "monoid/max_subarray.hpp"
#line 1 "monoid/min_subarray.hpp"
#line 6 "monoid/min_subarray.hpp"
namespacem1une{namespacemonoid{// Node for managing the optimal subarray sum.template<typenameT>structSubarrayNode{Tsum;Tpre;Tsuf;Topt;// Holds the optimal value (e.g., min or max)};// Monoid for finding the minimum subarray sum in a range.// Uses a comparison functor (Compare) to determine the optimal value.// Can be reused for maximum subarray sum by changing the Compare functor.template<typenameT,TId=std::numeric_limits<T>::max()/2,typenameCompare=std::less<T>>structMinSubarray{usingvalue_type=SubarrayNode<T>;staticconstexprboolcommutative=false;// The identity element contains values that do not affect the result.staticconstexprvalue_typeid(){return{T(0),Id,Id,Id};}// Merges two subarray nodes.staticconstexprvalue_typeop(constvalue_type&a,constvalue_type&b){if(a.opt==Id)returnb;if(b.opt==Id)returna;// Lambda to select the optimal value according to the comparison functor.autoget_opt=[](constT&x,constT&y){returnCompare()(x,y)?x:y;};return{a.sum+b.sum,get_opt(a.pre,a.sum+b.pre),get_opt(b.suf,a.suf+b.sum),get_opt(get_opt(a.opt,b.opt),a.suf+b.pre)};}// Helper to securely create a leaf node from a single value.// Set `allow_empty = true` if empty subarrays (sum = 0) are valid answers.staticconstexprvalue_typemake(constT&val,boolallow_empty=false){if(allow_empty){Topt_val=Compare()(val,T(0))?val:T(0);return{val,opt_val,opt_val,opt_val};}return{val,val,val,val};}};}// namespace monoid}// namespace m1une#line 8 "monoid/max_subarray.hpp"
namespacem1une{namespacemonoid{// Monoid for finding the maximum subarray sum in a range.// Defined as a type alias of MinSubarray using std::greater.template<typenameT,TId=std::numeric_limits<T>::lowest()/2>usingMaxSubarray=MinSubarray<T,Id,std::greater<T>>;}// namespace monoid}// namespace m1une#line 1 "monoid/min.hpp"
#line 6 "monoid/min.hpp"
namespacem1une{namespacemonoid{// Monoid for minimum (Range Minimum).// The identity element defaults to the maximum possible value of type T, but can be overridden.template<typenameT,TId=std::numeric_limits<T>::max()>structMin{usingvalue_type=T;staticconstexprboolcommutative=true;// Returns the identity element for minimum.staticconstexprTid(){returnId;}// Returns the minimum of a and b.staticconstexprTop(constT&a,constT&b){returnstd::min(a,b);}};}// namespace monoid}// namespace m1une#line 1 "monoid/min_max.hpp"
#line 7 "monoid/min_max.hpp"
namespacem1une{namespacemonoid{// Monoid for finding both the minimum and maximum values in a range simultaneously.template<typenameT,TMinId=std::numeric_limits<T>::max(),TMaxId=std::numeric_limits<T>::lowest()>structMinMax{usingvalue_type=std::pair<T,T>;staticconstexprboolcommutative=true;// The identity element contains the bounds for min and max.staticconstexprvalue_typeid(){return{MinId,MaxId};}// Merges two elements, extracting the overall min and max.staticconstexprvalue_typeop(constvalue_type&a,constvalue_type&b){return{std::min(a.first,b.first),std::max(a.second,b.second)};}// Helper to securely create a leaf node from a single value.staticconstexprvalue_typemake(constT&val){return{val,val};}};}// namespace monoid}// namespace m1une#line 1 "monoid/min_plus_matrix.hpp"
#line 7 "monoid/min_plus_matrix.hpp"
namespacem1une{namespacemonoid{// Monoid for fixed-size square matrix multiplication over the Min-Plus (Tropical) semiring.// Useful for Dynamic DP (Minimization) and Shortest Path problems.template<typenameT,intN,TInf=std::numeric_limits<T>::max()/2>structMinPlusMatrix{usingvalue_type=std::array<std::array<T,N>,N>;staticconstexprboolcommutative=false;// The identity matrix for min-plus algebra.// Diagonal elements are 0 (identity for addition).// Off-diagonal elements are Inf (identity for min).staticconstexprvalue_typeid(){value_typeres{};for(inti=0;i<N;++i){for(intj=0;j<N;++j){res[i][j]=(i==j)?T(0):Inf;}}returnres;}// Multiplies two min-plus matrices: c_{i, j} = min_k (a_{i, k} + b_{k, j})staticconstexprvalue_typeop(constvalue_type&a,constvalue_type&b){value_typeres{};for(inti=0;i<N;++i){for(intj=0;j<N;++j){res[i][j]=Inf;}}for(inti=0;i<N;++i){for(intk=0;k<N;++k){if(a[i][k]==Inf)continue;for(intj=0;j<N;++j){if(b[k][j]==Inf)continue;res[i][j]=std::min(res[i][j],a[i][k]+b[k][j]);}}}returnres;}// Helper to securely create a matrix initialized with Inf.staticconstexprvalue_typemake_inf(){value_typeres{};for(inti=0;i<N;++i){for(intj=0;j<N;++j){res[i][j]=Inf;}}returnres;}};}// namespace monoid}// namespace m1une#line 1 "monoid/mul.hpp"
namespacem1une{namespacemonoid{// Monoid for multiplication (Range Product).template<typenameT>structMul{usingvalue_type=T;staticconstexprboolcommutative=true;// Returns the identity element for multiplication, which is 1.staticconstexprTid(){returnT(1);}// Returns the product of a and b.staticconstexprTop(constT&a,constT&b){returna*b;}};}// namespace monoid}// namespace m1une#line 1 "monoid/or.hpp"
namespacem1une{namespacemonoid{// Monoid for bitwise OR (Range OR).template<typenameT>structOr{usingvalue_type=T;staticconstexprboolcommutative=true;// The identity element for bitwise OR is 0 (all bits 0).staticconstexprTid(){returnT(0);}// Returns the bitwise OR of a and b.staticconstexprTop(constT&a,constT&b){returna|b;}};}// namespace monoid}// namespace m1une#line 1 "monoid/permutation.hpp"
#line 6 "monoid/permutation.hpp"
namespacem1une{namespacemonoid{// Monoid for Permutation Composition.// Represents a permutation of fixed size N.template<intN>structPermutation{usingvalue_type=std::array<int,N>;staticconstexprboolcommutative=false;// The identity element is the identity permutation (0, 1, 2, ..., N-1).staticconstexprvalue_typeid(){value_typeres{};std::iota(res.begin(),res.end(),0);returnres;}// Composes two permutations (applies 'a' then 'b').staticconstexprvalue_typeop(constvalue_type&a,constvalue_type&b){value_typeres{};for(inti=0;i<N;++i){res[i]=b[a[i]];}returnres;}};}// namespace monoid}// namespace m1une#line 1 "monoid/rolling_hash.hpp"
#line 5 "monoid/rolling_hash.hpp"
#line 1 "string/rolling_hash.hpp"
#line 5 "string/rolling_hash.hpp"
#include<string>
#line 8 "string/rolling_hash.hpp"
namespacem1une{namespacestring{// Standard Rolling Hash for static strings.// Precomputes hashes to answer substring queries in O(1).// Provides advanced operations like LCP, lexicographical comparison, and string repetition in O(log N).template<longlongBase=10007,longlongMod=(1LL<<61)-1>structRollingHash{std::strings;std::vector<longlong>hash;std::vector<longlong>power;RollingHash()=default;// Constructs the rolling hash table for the given string.explicitRollingHash(conststd::string&str):s(str){intn=s.size();hash.assign(n+1,0);power.assign(n+1,1);for(inti=0;i<n;++i){// Use __int128_t to prevent overflow during multiplicationhash[i+1]=(static_cast<__int128_t>(hash[i])*Base+s[i])%Mod;power[i+1]=(static_cast<__int128_t>(power[i])*Base)%Mod;}}// Returns the hash of the substring S[l..r) in O(1).longlongget(intl,intr)const{longlongres=hash[r]-(static_cast<__int128_t>(hash[l])*power[r-l])%Mod;if(res<0)res+=Mod;returnres;}// Returns the hash of the concatenated substrings S[l1..r1) and S[l2..r2).longlongconcat(intl1,intr1,intl2,intr2)const{longlongh1=get(l1,r1);longlongh2=get(l2,r2);returncombine(h1,h2,power[r2-l2]);}// Calculates the Longest Common Prefix (LCP) length of S[l1..r1) and S[l2..r2) in O(log N).intlcp(intl1,intr1,intl2,intr2)const{intlen=std::min(r1-l1,r2-l2);intlow=0,high=len+1;while(high-low>1){intmid=low+(high-low)/2;if(get(l1,l1+mid)==get(l2,l2+mid)){low=mid;}else{high=mid;}}returnlow;}// Lexicographically compares S[l1..r1) and S[l2..r2) in O(log N).// Returns -1 if S[l1..r1) < S[l2..r2), 0 if equal, and 1 if S[l1..r1) > S[l2..r2).intcompare(intl1,intr1,intl2,intr2)const{intl=lcp(l1,r1,l2,r2);boolend1=(l1+l==r1);boolend2=(l2+l==r2);if(end1&&end2)return0;if(end1)return-1;if(end2)return1;returns[l1+l]<s[l2+l]?-1:1;}// Returns the hash of the substring S[l..r) repeated 'k' times.longlongrepeat(intl,intr,longlongk)const{longlongh=get(l,r);longlongp=power[r-l];returnrepeat_hash(h,p,k);}// --- Static Helpers for dynamic processing and Monoid integration ---// Computes the hash of a single string in O(N) time and O(1) space.staticlonglongcompute_hash(conststd::string&str){longlongh=0;for(charc:str){h=(static_cast<__int128_t>(h)*Base+c)%Mod;}returnh;}// Combines two hashes. Equivalent to concatenating string 'b' to the right of string 'a'.staticconstexprlonglongcombine(longlongh1,longlongh2,longlongbase_power2){return(static_cast<__int128_t>(h1)*base_power2+h2)%Mod;}// Returns the hash of a string (with hash 'h' and base_power 'p') repeated 'k' times.staticconstexprlonglongrepeat_hash(longlongh,longlongp,longlongk){longlongres_h=0;longlongres_p=1;longlongcur_h=h;longlongcur_p=p;while(k>0){if(k&1){res_h=combine(res_h,cur_h,cur_p);res_p=(static_cast<__int128_t>(res_p)*cur_p)%Mod;}cur_h=combine(cur_h,cur_h,cur_p);cur_p=(static_cast<__int128_t>(cur_p)*cur_p)%Mod;k>>=1;}returnres_h;}// Creates the state pair {hash_value, base_power} for a single character.staticconstexprstd::pair<longlong,longlong>make_single(longlongc){return{c%Mod,Base%Mod};}};}// namespace string}// namespace m1une#line 7 "monoid/rolling_hash.hpp"
namespacem1une{namespacemonoid{// Monoid for Dynamic Rolling Hash (String Concatenation).// Acts as a clean wrapper around the mathematical logic defined in string::RollingHash.//// [Important Usage Note for Contests]// To initialize a leaf node for a single character S[i], use the `make` method://// Example:// std::vector<RH::value_type> init_data(N);// for (int i = 0; i < N; ++i) {// init_data[i] = RH::make(S[i]);// }// Segtree<RH> seg(init_data);template<longlongBase=10007,longlongMod=(1LL<<61)-1>structRollingHash{usingStringRH=m1une::string::RollingHash<Base,Mod>;usingvalue_type=std::pair<longlong,longlong>;staticconstexprboolcommutative=false;// The identity element represents an empty string.staticconstexprvalue_typeid(){return{0LL,1LL};}// Combines two hashes by delegating to string::RollingHash.staticconstexprvalue_typeop(constvalue_type&a,constvalue_type&b){return{StringRH::combine(a.first,b.first,b.second),(static_cast<__int128_t>(a.second)*b.second)%Mod};}// Helper to securely create a monoid element from a single character (or integer).// Delegates to string::RollingHash to hide the base/mod mechanics.staticconstexprvalue_typemake(longlongc){returnStringRH::make_single(c);}};}// namespace monoid}// namespace m1une#line 1 "monoid/strict_max2.hpp"
#line 6 "monoid/strict_max2.hpp"
#line 1 "monoid/strict_min2.hpp"
#line 6 "monoid/strict_min2.hpp"
namespacem1une{namespacemonoid{template<typenameT>structStrictOpt2Node{Topt1;// The strictly best valueTopt2;// The strictly second-best value};// Monoid for finding the strictly 1st and 2nd optimal (minimum by default) values in a range.template<typenameT,TId=std::numeric_limits<T>::max(),typenameCompare=std::less<T>>structStrictMin2{usingvalue_type=StrictOpt2Node<T>;staticconstexprboolcommutative=true;// The identity element has both values set to Id.staticconstexprvalue_typeid(){return{Id,Id};}// Merges two elements, preserving the top 2 strictly unique values.staticconstexprvalue_typeop(constvalue_type&a,constvalue_type&b){autoupdate=[](T&m1,T&m2,Tval){if(val==Id||val==m1||val==m2)return;if(m1==Id||Compare()(val,m1)){m2=m1;m1=val;}elseif(m2==Id||Compare()(val,m2)){m2=val;}};Tm1=Id,m2=Id;update(m1,m2,a.opt1);update(m1,m2,a.opt2);update(m1,m2,b.opt1);update(m1,m2,b.opt2);return{m1,m2};}// Helper to securely create a leaf node.staticconstexprvalue_typemake(constT&val){return{val,Id};}};}// namespace monoid}// namespace m1une#line 8 "monoid/strict_max2.hpp"
namespacem1une{namespacemonoid{// Monoid for finding the strictly 1st and 2nd maximum values in a range.// Defined as a type alias of StrictMin2 using std::greater.template<typenameT,TId=std::numeric_limits<T>::lowest()>usingStrictMax2=StrictMin2<T,Id,std::greater<T>>;}// namespace monoid}// namespace m1une#line 1 "monoid/top_k_count.hpp"
#line 8 "monoid/top_k_count.hpp"
namespacem1une{namespacemonoid{// Monoid for finding the top K distinct elements and their frequencies in a range.// The default Compare is std::greater<T> (descending order for Top K).template<typenameT,intK,typenameCompare=std::greater<T>>structTopKCount{usingvalue_type=std::vector<std::pair<T,int>>;staticconstexprboolcommutative=true;staticconstexprvalue_typeid(){returnvalue_type();}staticconstexprvalue_typeop(constvalue_type&a,constvalue_type&b){value_typeres;res.reserve(std::min(K,(int)(a.size()+b.size())));inti=0,j=0;while(res.size()<(std::size_t)K&&(i<(int)a.size()||j<(int)b.size())){if(i==(int)a.size()){res.push_back(b[j++]);}elseif(j==(int)b.size()){res.push_back(a[i++]);}elseif(a[i].first==b[j].first){// If the values are identical, merge their countsres.push_back({a[i].first,a[i].second+b[j].second});i++;j++;}elseif(Compare()(a[i].first,b[j].first)){res.push_back(a[i++]);}else{res.push_back(b[j++]);}}returnres;}// Helper to securely create a leaf node from a single value.staticconstexprvalue_typemake(constT&val,intcount=1){returnvalue_type{std::pair<T,int>{val,count}};}};}// namespace monoid}// namespace m1une#line 1 "monoid/update.hpp"
#line 5 "monoid/update.hpp"
namespacem1une{namespacemonoid{// Monoid for range updates/assignments.// Uses std::optional to represent the presence of an assignment.template<typenameT>structUpdate{usingvalue_type=std::optional<T>;staticconstexprboolcommutative=false;// The identity element represents "no operation".staticconstexprvalue_typeid(){returnstd::nullopt;}// Composes two updates. The newer operation 'a' overwrites the older 'b'.// If 'a' does not exist, it falls back to 'b'.staticconstexprvalue_typeop(constvalue_type&a,constvalue_type&b){returna.has_value()?a:b;}};}// namespace monoid}// namespace m1une#line 1 "monoid/wrapper.hpp"
namespacem1une{namespacemonoid{// Wrapper struct to generate a Monoid using Non-Type Template Parameters (NTTP).// Useful for quickly defining monoids using custom functions or constexpr lambdas during contests.template<typenameT,autoOp,autoId,boolCommutative=false>structWrapper{usingvalue_type=T;staticconstexprboolcommutative=Commutative;// Returns the identity element by invoking the provided `Id` function.staticconstexprTid(){returnId();}// Returns the result of the binary operation by invoking the provided `Op` function.staticconstexprTop(constT&a,constT&b){returnOp(a,b);}};}// namespace monoid}// namespace m1une#line 1 "monoid/xor.hpp"
namespacem1une{namespacemonoid{// Monoid for bitwise XOR (Range XOR).template<typenameT>structXor{usingvalue_type=T;staticconstexprboolcommutative=true;// Returns the identity element for bitwise XOR, which is 0.staticconstexprTid(){returnT(0);}// Returns the bitwise XOR of a and b.staticconstexprTop(constT&a,constT&b){returna^b;}staticconstexprTinv(constT&x){returnx;}};}// namespace monoid}// namespace m1une#line 67 "verify/monoid/commutative_flags.test.cpp"
namespace{structContestMonoid{usingvalue_type=int;staticconstexprintid(){return0;}staticconstexprintop(constint&a,constint&b){returna+b;}};structContestActedMonoid{usingvalue_type=int;usingoperator_type=int;staticconstexprintid(){return0;}staticconstexprintop(constint&a,constint&b){returna+b;}staticconstexprintop_id(){return0;}staticconstexprintop_comp(constint&f,constint&g){returnf+g;}staticconstexprintmapping(constint&f,constint&x){returnf+x;}};constexprautoint_add=[](constint&a,constint&b){returna+b;};constexprautoint_zero=[]{return0;};constexprautoint_mapping=[](constint&f,constint&x){returnf+x;};constexprautoalways_applicable=[](constint&,constint&){returntrue;};usingDefaultMonoidWrapper=m1une::monoid::Wrapper<int,int_add,int_zero>;usingCommutativeMonoidWrapper=m1une::monoid::Wrapper<int,int_add,int_zero,true>;usingDefaultActedWrapper=m1une::acted_monoid::Wrapper<int,int,int_add,int_zero,int_add,int_zero,int_mapping>;usingCommutativeActedWrapper=m1une::acted_monoid::Wrapper<int,int,int_add,int_zero,int_add,int_zero,int_mapping,true>;usingCommutativeOperatorActedWrapper=m1une::acted_monoid::Wrapper<int,int,int_add,int_zero,int_add,int_zero,int_mapping,false,true>;usingDefaultBeatsWrapper=m1une::beats_acted_monoid::Wrapper<int,int,int_add,int_zero,int_add,int_zero,int_mapping,always_applicable>;usingCommutativeBeatsWrapper=m1une::beats_acted_monoid::Wrapper<int,int,int_add,int_zero,int_add,int_zero,int_mapping,always_applicable,nullptr,nullptr,nullptr,nullptr,nullptr,true>;usingCommutativeOperatorBeatsWrapper=m1une::beats_acted_monoid::Wrapper<int,int,int_add,int_zero,int_add,int_zero,int_mapping,always_applicable,nullptr,nullptr,nullptr,nullptr,nullptr,false,true>;static_assert(m1une::monoid::IsMonoid<ContestMonoid>);static_assert(m1une::acted_monoid::IsActedMonoid<ContestActedMonoid>);static_assert(m1une::beats_acted_monoid::IsBeatsActedMonoid<DefaultBeatsWrapper>);static_assert(m1une::monoid::Add<int>::commutative);static_assert(m1une::monoid::And<int>::commutative);static_assert(m1une::monoid::BottomK<int,2>::commutative);static_assert(m1une::monoid::Gcd<int>::commutative);static_assert(m1une::monoid::Max<int>::commutative);static_assert(m1une::monoid::MaxCount<int>::commutative);static_assert(m1une::monoid::Min<int>::commutative);static_assert(m1une::monoid::MinCount<int>::commutative);static_assert(m1une::monoid::MinMax<int>::commutative);static_assert(m1une::monoid::Mul<int>::commutative);static_assert(m1une::monoid::Or<int>::commutative);static_assert(m1une::monoid::StrictMax2<int>::commutative);static_assert(m1une::monoid::StrictMin2<int>::commutative);static_assert(m1une::monoid::TopK<int,2>::commutative);static_assert(m1une::monoid::TopKCount<int,2>::commutative);static_assert(m1une::monoid::Xor<int>::commutative);static_assert(CommutativeMonoidWrapper::commutative);static_assert(!m1une::monoid::Affine<int>::commutative);static_assert(!m1une::monoid::ArgMax<int>::commutative);static_assert(!m1une::monoid::ArgMin<int>::commutative);static_assert(!m1une::monoid::BinaryInversion<int>::commutative);static_assert(!m1une::monoid::Bracket::commutative);static_assert(!m1une::monoid::LongestSame<int>::commutative);static_assert(!m1une::monoid::LongestTrue::commutative);static_assert(!m1une::monoid::Matrix<int,2>::commutative);static_assert(!m1une::monoid::MaxPlusMatrix<int,2>::commutative);static_assert(!m1une::monoid::MaxSubarray<int>::commutative);static_assert(!m1une::monoid::MinPlusMatrix<int,2>::commutative);static_assert(!m1une::monoid::MinSubarray<int>::commutative);static_assert(!m1une::monoid::Permutation<3>::commutative);static_assert(!m1une::monoid::RollingHash<>::commutative);static_assert(!m1une::monoid::Update<int>::commutative);static_assert(!DefaultMonoidWrapper::commutative);static_assert(m1une::acted_monoid::RangeAddRangeMax<int>::commutative);static_assert(m1une::acted_monoid::RangeAddRangeMin<int>::commutative);static_assert(m1une::acted_monoid::RangeAddRangeMinCount<int>::commutative);static_assert(m1une::acted_monoid::RangeAddRangeSum<int>::commutative);static_assert(m1une::acted_monoid::RangeAffineRangeMinMax<int>::commutative);static_assert(m1une::acted_monoid::RangeAffineRangeSum<int>::commutative);static_assert(m1une::acted_monoid::RangeAffineRangeSumOfSquares<int>::commutative);static_assert(m1une::acted_monoid::RangeApUpdateRangeMinMax<int>::commutative);static_assert(m1une::acted_monoid::RangeBitwiseAndOrXorRangeSum<int>::commutative);static_assert(m1une::acted_monoid::RangeFlipRangeSum<int>::commutative);static_assert(m1une::acted_monoid::RangeMulRangeSum<int>::commutative);static_assert(m1une::acted_monoid::RangeOrRangeSum<int>::commutative);static_assert(m1une::acted_monoid::RangeUpdateRangeMax<int>::commutative);static_assert(m1une::acted_monoid::RangeUpdateRangeMin<int>::commutative);static_assert(m1une::acted_monoid::RangeUpdateRangeProduct<m1une::monoid::Add<int>>::commutative);static_assert(m1une::acted_monoid::RangeUpdateRangeSum<int>::commutative);static_assert(m1une::acted_monoid::RangeXorRangeSum<int>::commutative);static_assert(m1une::acted_monoid::RangeXorRangeXor<int>::commutative);static_assert(CommutativeActedWrapper::commutative);static_assert(CommutativeBeatsWrapper::commutative);static_assert(!m1une::acted_monoid::RangeAddRangeArgMax<int>::commutative);static_assert(!m1une::acted_monoid::RangeAddRangeArgMin<int>::commutative);static_assert(!m1une::acted_monoid::RangeApAddRangeSum<int>::commutative);static_assert(!m1une::acted_monoid::RangeApUpdateRangeSum<int>::commutative);static_assert(!m1une::acted_monoid::RangeFlipRangeBinaryInversion<int>::commutative);static_assert(!m1une::acted_monoid::RangeUpdateRangeLongestTrue::commutative);static_assert(!m1une::acted_monoid::RangeUpdateRangeMaxSubarray<int>::commutative);static_assert(!m1une::acted_monoid::RangeUpdateRangeProduct<m1une::monoid::Affine<int>>::commutative);static_assert(!m1une::acted_monoid::RangeUpdateRangeProduct<ContestMonoid>::commutative);static_assert(!DefaultActedWrapper::commutative);static_assert(!DefaultBeatsWrapper::commutative);static_assert(m1une::acted_monoid::RangeAddRangeArgMax<int>::operator_commutative);static_assert(m1une::acted_monoid::RangeAddRangeArgMin<int>::operator_commutative);static_assert(m1une::acted_monoid::RangeAddRangeMax<int>::operator_commutative);static_assert(m1une::acted_monoid::RangeAddRangeMin<int>::operator_commutative);static_assert(m1une::acted_monoid::RangeAddRangeMinCount<int>::operator_commutative);static_assert(m1une::acted_monoid::RangeAddRangeSum<int>::operator_commutative);static_assert(m1une::acted_monoid::RangeApAddRangeSum<int>::operator_commutative);static_assert(m1une::acted_monoid::RangeFlipRangeBinaryInversion<int>::operator_commutative);static_assert(m1une::acted_monoid::RangeFlipRangeSum<int>::operator_commutative);static_assert(m1une::acted_monoid::RangeMulRangeSum<int>::operator_commutative);static_assert(m1une::acted_monoid::RangeOrRangeSum<int>::operator_commutative);static_assert(m1une::acted_monoid::RangeXorRangeSum<int>::operator_commutative);static_assert(m1une::acted_monoid::RangeXorRangeXor<int>::operator_commutative);static_assert(CommutativeOperatorActedWrapper::operator_commutative);static_assert(CommutativeOperatorBeatsWrapper::operator_commutative);static_assert(!m1une::acted_monoid::RangeAffineRangeMinMax<int>::operator_commutative);static_assert(!m1une::acted_monoid::RangeAffineRangeSum<int>::operator_commutative);static_assert(!m1une::acted_monoid::RangeAffineRangeSumOfSquares<int>::operator_commutative);static_assert(!m1une::acted_monoid::RangeApUpdateRangeMinMax<int>::operator_commutative);static_assert(!m1une::acted_monoid::RangeApUpdateRangeSum<int>::operator_commutative);static_assert(!m1une::acted_monoid::RangeBitwiseAndOrXorRangeSum<int>::operator_commutative);static_assert(!m1une::acted_monoid::RangeUpdateRangeLongestTrue::operator_commutative);static_assert(!m1une::acted_monoid::RangeUpdateRangeMax<int>::operator_commutative);static_assert(!m1une::acted_monoid::RangeUpdateRangeMaxSubarray<int>::operator_commutative);static_assert(!m1une::acted_monoid::RangeUpdateRangeMin<int>::operator_commutative);static_assert(!m1une::acted_monoid::RangeUpdateRangeProduct<m1une::monoid::Add<int>>::operator_commutative);static_assert(!m1une::acted_monoid::RangeUpdateRangeSum<int>::operator_commutative);static_assert(!DefaultActedWrapper::operator_commutative);static_assert(!DefaultBeatsWrapper::operator_commutative);static_assert(!CommutativeActedWrapper::operator_commutative);static_assert(!CommutativeBeatsWrapper::operator_commutative);static_assert(!CommutativeOperatorActedWrapper::commutative);static_assert(!CommutativeOperatorBeatsWrapper::commutative);}// namespaceintmain(){inta,b;std::cin>>a>>b;std::cout<<a+b<<'\n';}
verify/monoid/commutative_flags.test.cpp