• Với thao tác ~C(i, k)~, ta có công thức để tính ~S_i~ mới sẽ bằng ~(S_i + k)~ ~mod~ ~26~ (với ~S_i~ tự ngầm hiểu là thứ tự của chữ cái đó được bắt đầu từ số ~0~).

• Để tính được ~F(T)~, ta sẽ xét các trường hợp của xâu ~T~.

  • ~F(T) = 0~ nếu ~T~ là một xâu đối xứng và được tạo bởi duy nhất một chữ cái (Ví dụ: "aaaa").

  • ~F(T) = N - 1~ nếu ~T~ là xâu đối xứng.

  • ~F(T) = N~ trong các trường hợp còn lại.

  (Độc giả tự chứng minh).

Subtask 1: Làm theo đúng yêu cầu của đề. ĐPT: ~O(N \cdot Q)~

Subtask 2: Do ~k = 0~ nên xâu sẽ không bị thay đổi. Ta có thể tiền xử lí để kiểm tra tính đối xứng xâu trong truy vấn bằng hash string. ĐPT: ~O(N + Q)~

Subtask 3: Vì ~l = r~ nên ở mỗi truy vấn ta chỉ thay đổi chính xác một vị trí duy nhất. Ta có thể sử dụng hash string kết hợp cùng Cây phân đoạn hoặc Mo with update. ĐPT: ~O(Q \cdot \log N)~ hoặc ~O(Q \cdot N^{2/3})~

Subtask 4: Vì các truy vấn loại ~1~ được thực hiện trước truy vấn loại ~2~ nên ta có thể tiền xử lí để tìm ra xâu ~S~ sau tất cả truy vấn loại ~1~ bằng Mảng cộng dồn, sau đó làm như Subtask 2. ĐPT: ~O(N + Q)~

Subtask 5:

Ta sẽ biến đổi công thức khi hashing:

• Lấy ví dụ ~S = abacb~. Ở hệ cơ số ~base~: ~S = (1, 2, 1, 3, 2)~.

• Khi chuyển về hệ cơ số 10: ~S = 1 \cdot base^4 + 2 \cdot base^3 + 1 \cdot base^2 + 3 \cdot base^1 + 2 \cdot base^0~, suy ra ~S = 1 \cdot (base^4 + base^2) + 2 \cdot (base^3 + base^0) + 3 \cdot (base^1)~.

• Từ đó, ta có công thức mới ~S = 1 \cdot cnt[1] + 2 \cdot cnt[2] + \ldots + 26 \cdot cnt[26]~, với ~cnt[i] = \sum_{t = 1}^{N} base^{N - t}~ (với điều kiện ~S_t~ bằng chữ cái thứ ~i~ trong bảng chữ cái).

Khi thực hiện bước nhảy, ta chỉ cần xoay mảng ~cnt~ một cách thích hợp là được.

Sử dụng cây phân đoạn: với mỗi nút quản lí đoạn ~[l, r]~ lưu mảng ~L~, ~R~, với ~L_i = \sum_{t = l}^{r} base^{r - t}~, ~R_i = \sum_{t = l}^{r} base^{t - l}~ (với điều kiện ~S_t~ bằng chữ cái thứ ~i~ trong bảng chữ cái).

ĐPT: ~O(Q \cdot \log(N) \cdot 26)~.

#pragma GCC optimize("unroll-loops,02,no-stack-protector")
#pragma GCC target ("avx2")

#include <bits/stdc++.h> // QioCas

#ifdef LOCAL
#include </home/cas/Cp/Lib/debug.h>
#else
#define console(...) void(2024323)
#endif

using namespace std;
using ll = long long;

const int N = 1e5 + 5;
const int MOD = 1e9 + 7;
const int base = 37;

int n, q;
string S;

struct dhash {
    int first = 0, second = 0;
    dhash() = default;
    dhash(int x): first(x % MOD), second(x) {}
    dhash(int __first, int __second): first(__first), second(__second) {}
    friend dhash operator + (const dhash& u, const dhash& v) {
        return {(u.first + v.first) % MOD, u.second + v.second};
    }
    friend dhash operator - (const dhash& u, const dhash& v) {
        return {(u.first - v.first + MOD) % MOD, u.second - v.second};
    }
    friend dhash operator * (const dhash& u, const dhash& v) {
        return {(int) (1LL * u.first * v.first % MOD), u.second * v.second};
    }
    friend bool operator == (const dhash& u, const dhash& v) {
        return u.first == v.first && u.second == v.second;
    }
};

dhash P[N], Prefix[N];

struct node_t {
    int sz = 0;
    dhash ltr[26], rtl[26];
    node_t() = default;
    node_t(char x) {
        sz = 1;
        ltr[(int) x - 'a'] = rtl[(int) x - 'a'] = 1;
    }
    void C(int k) {
        rotate(ltr, ltr + 26 - k, ltr + 26);
        rotate(rtl, rtl + 26 - k, rtl + 26);
    }
} IT[N << 2];

void merge(node_t& result, const node_t& u, const node_t& v) {
    result.sz = u.sz + v.sz;
    for(int i = 0; i < 26; ++i) {
        result.ltr[i] = u.ltr[i] * P[v.sz] + v.ltr[i];
        result.rtl[i] = u.rtl[i] + v.rtl[i] * P[u.sz]; 
    }
}

int LZ[N << 2];

#define mid ((l + r) >> 1)

void build(int id, int l, int r) {
    if(l == r) {
        IT[id] = node_t(S[l]);
        return;
    }
    build(id << 1, l, mid);
    build(id << 1 | 1, mid + 1, r);
    merge(IT[id], IT[id << 1], IT[id << 1 | 1]);
}

void update(int id, int k) {
    if((LZ[id] += k) >= 26) LZ[id] -= 26;
    IT[id].C(k);
}

void down(int id) {
    if(LZ[id] == 0) return;
    update(id << 1, LZ[id]);
    update(id << 1 | 1, LZ[id]);
    LZ[id] = 0;
}

void update(int id, int l, int r, int s, int t, int k) { 
    if(l > t || r < s) return;
    if(s <= l && r <= t) {
        update(id, k);
        return;
    }
    down(id);
    update(id << 1, l, mid, s, t, k);
    update(id << 1 | 1, mid + 1, r, s, t, k);
    merge(IT[id], IT[id << 1], IT[id << 1 | 1]);
}

struct prod_t { int sz; dhash first, second; };

prod_t prod(int id, int l, int r, int s, int t) {
    if(l > t || r < s) return prod_t{};
    if(s <= l && r <= t) {
        prod_t ret = {r - l + 1};
        for(int i = 0; i < 26; ++i) 
        {
            ret.first = ret.first + IT[id].ltr[i] * dhash(i + 1);
            ret.second = ret.second + IT[id].rtl[i] * dhash(i + 1);
        }
        return ret;
    }
    down(id);
    prod_t L = prod(id << 1, l, mid, s, t);
    prod_t R = prod(id << 1 | 1, mid + 1, r, s, t);
    return {L.sz + R.sz, L.first * P[R.sz] + R.first, L.second + R.second * P[L.sz]};
}

int main() {
    cin.tie(NULL)->sync_with_stdio(false);
    console(file());
    cin >> n >> q;
    cin >> S;
    S = " " + S;

    P[0] = Prefix[0] = dhash(1);
    for(int i = 1; i <= n; ++i) {
        P[i] = P[i - 1] * dhash(base);
        Prefix[i] = Prefix[i - 1] + P[i];
    }

    build(1, 1, n);
    while(q--) {
        int op; cin >> op;
        if(op == 1) {
            int l, r, k; cin >> l >> r >> k; k %= 26;
            update(1, 1, n, l, r, k);
        } else {
            int l, r; cin >> l >> r;

            prod_t ret = prod(1, 1, n, l, r);
            bool diff = 1;

            console(ret.first.first, ret.second.first);
            if(ret.first == ret.second)
            {
                for(int i = 0; diff && i < 26; ++i) 
                    if(ret.first == Prefix[r - l] * dhash(i + 1)) diff = 0;
                cout << (diff ? r - l : 0) << "\n";
            } else cout << r - l + 1 << "\n";

        }
    }
    return 0;
}