#include using namespace std; // #include // using namespace atcoder; // using mint = modint998244353; using ll = long long; #define fix(x) fixed << setprecision(x) #define rep(i, n) for(int i = 0; i < n; ++i) #define all(x) (x).begin(),(x).end() templatebool chmin(T&a, const T&b){if(a>b){a=b;return 1;}return 0;} templatebool chmax(T&a, const T&b){if(a> n >> q; string s; cin >> s; int log = 0; while(n-2>(1<> seg(17576); rep(i,n-2){ int x = enc(s.substr(i,3)), idx = i+(1<>= 1; } while(q--){ int t; cin >> t; if(t==1){ int k; char c; cin >> k >> c; --k; for(int i=max(k-2,0);i>= 1; } s[k] = c; for(int i=max(k-2,0);i>= 1; } }else{ int l,r,z; string t; cin >> l >> r >> t; --l; z = l; r -= 2; if(l>r){ cout << "0\n"; continue; } l += 1<>= 1, r >>= 1; } ll cnt = tot & ((1<<18)-1); tot >>= 18; cout << tot-z*cnt << '\n'; } } return 0; }