Một xâu được gọi là xâu đối xứng nếu như viết xâu đó từ trái sang phải giống cách viết xâu ấy từ phải sang trái. Ví dụ về xâu đối xứng là "ioi", "madam", ~\dots~ Ví dụ về xâu không phải xâu đối xứng là "vnoi", "abab", ~\dots~

Gọi ~F(T)~ là độ dài của xâu con liên tiếp dài nhất của ~T~ mà không phải là xâu đối xứng. Ví dụ: ~F(~"ioi"~) = 2~, ~F(~"vnoi"~) = 4~, ~F(~"zzz"~) = 0~.

Cho một xâu ~S~ có độ dài ~N~ gồm các chữ cái viết thường. Một chữ cái ~c~ được gọi là thực hiện bước nhảy là khi ta thay thế ~c~ bằng chữ cái sau chữ cái ~c~ trong bảng alphabet, riêng chữ cái sau z là chữ a. Thao tác ~C(i, k)~ sẽ làm cho kí tự ~S_i~ thực hiện bước nhảy ~k~ lần.

Ta có ~Q~ truy vấn, mỗi truy vấn thuộc một trong ~2~ loại sau đây:

• ~1~ ~l~ ~r~ ~k~ ~(1 \le l \le r \le N, 0 \le k \le 10^9)~: Thực hiện thao tác ~C(i, k)~ với tất cả ~i~ từ ~l~ tới ~r~.

• ~2~ ~l~ ~r~ ~(1 \le l \le r \le N)~: In ra ~F(T)~ với ~T~ là xâu con liên tiếp gồm các ký tự từ ~l~ tới ~r~ của ~S~.

Input

• Dòng đầu tiên gồm ~2~ số nguyên ~N, Q~ ~(1 \le N, Q \le 10^5)~ — độ dài của xâu ~S~ và số lượng truy vấn.

• Dòng thứ hai chứa xâu ~S~.

• ~Q~ dòng cuối cùng, mỗi dòng có dạng thuộc một trong ~2~ loại đã nói ở trên.

Output

• Với mỗi truy vấn loại ~2~, in ra đáp án của truy vấn trên một dòng.

Scoring

Sample Input 1

3 3
uwu
2 1 3
1 2 3 4
2 2 3

Sample Output 1

2
2

Sample Input 2

10 3
toiyeuvnoi
2 5 10
1 1 9 21
2 8 10

Sample Output 2

6
2

Notes

Giải thích bộ test thứ nhất:

• Ban đầu, ~S~ = "uwu".

• Truy vấn ~1~, ~F(~"uwu"~) = 2~, xâu con dài nhất thõa mãn có thể là "uw" hoặc "wu".

• Truy vấn ~2~, ~S_2 =~ w lần lượt nhảy tới x, y, z, và rồi tới a, còn ~S_3 =~ u sau ~4~ lần nhảy sẽ nhảy tới y. Do đó lúc này ~S =~ "uay".

• Truy vấn ~3~, ~F(~"ay"~) = 2~, xâu con thỏa mãn dài nhất là chính nó.