//g++ 1.cpp -std=c++17 -O2 -I . #include using namespace std; #include #include using namespace atcoder; using ll = long long; using ld = long double; using vi = vector; using vvi = vector; using vll = vector; using vvll = vector; using vld = vector; using vvld = vector; using vst = vector; using vvst = vector; #define fi first #define se second #define pb push_back #define eb emplace_back #define pq_big(T) priority_queue,less> #define pq_small(T) priority_queue,greater> #define all(a) a.begin(),a.end() #define rep(i,start,end) for(ll i=start;i<(ll)(end);i++) #define per(i,start,end) for(ll i=start;i>=(ll)(end);i--) #define uniq(a) sort(all(a));a.erase(unique(all(a)),a.end()) using mint = modint998244353; struct S{ int len,zero,one; mint score; tuple left,right; // 左,右から順に見た時の count(0),count(1),count(0)*count(1) の総和 }; S op(S a,S b){ S res; res.len=a.len+b.len; res.zero=a.zero+b.zero; res.one=a.one+b.one; auto [al_count0,al_count1,al_count01]=a.left; auto [ar_count0,ar_count1,ar_count01]=a.right; auto [bl_count0,bl_count1,bl_count01]=b.left; auto [br_count0,br_count1,br_count01]=b.right; res.score=a.score+b.score+a.len*bl_count01+b.len*ar_count01+ar_count0*bl_count1+ar_count1*bl_count0; res.left ={al_count0+bl_count0+a.zero*b.len,al_count1+bl_count1+a.one*b.len,al_count01+bl_count01+a.one*bl_count0+a.zero*bl_count1+b.len*a.zero*a.one}; res.right={br_count0+ar_count0+b.zero*a.len,br_count1+ar_count1+b.one*a.len,br_count01+ar_count01+b.one*ar_count0+b.zero*ar_count1+a.len*b.zero*b.one}; return res; } S e(){ S res{0,0,0,0,{0,0,0},{0,0,0}}; return res; } S zero(){ return {1,1,0,0,{1,0,0},{1,0,0}}; } S one(){ return {1,0,1,0,{0,1,0},{0,1,0}}; } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int n,q; cin>>n>>q; string s; cin>>s; vector init(n); rep(i,0,n){ if(s[i]=='0')init[i]=zero(); else init[i]=one(); } segtree seg(init); while(q--){ int t; cin>>t; if(t==1){ int i; cin>>i; i--; if(s[i]=='0'){ seg.set(i,one()); s[i]='1'; } else{ seg.set(i,zero()); s[i]='0'; } } else{ int l,r; cin>>l>>r; l--; string str=s.substr(l,r-l); cout<