Thầy Tina là một tấm gương của CLB H3.2 với những bài giảng về Kỹ thuật lập trình, Đạo đức nghề nghiệp rất sâu sắc. Thầy nhấn mạnh rằng không có gì là hoàn hảo và phải biết vượt qua những khó khăn để có thể Hướng tới những vì sao. Nếu kể ra thêm thì cũng khá dài dòng nhưng hôm nay, chúng ta sẽ tìm hiểu thử một trong các bài giảng của thầy về xử lý chuỗi. Thầy rất thích các chuỗi ký tự non-palindrome, không đối xứng (là chuỗi mà đảo ngược của nó khác với chuỗi ban đầu). Thầy gọi những chuỗi như vậy là đẹp vì thầy thích những điều không hoàn hảo. Với một chuỗi ~s~ cho trước, thầy muốn cắt nó ra thành nhiều chuỗi con rời nhau mà số chuỗi đẹp trong đó là càng nhiều càng tốt (tất nhiên trong đó vẫn có thể có các chuỗi không đẹp).

Ví dụ: với chuỗi ~s_1=abcabc~, thầy có thể cắt thành ~ab~, ~ca~, ~bc~ là được ~3~ chuỗi đẹp; còn với chuỗi ~s_2=xyzz~ thì thầy có thể cắt thành ~xyz~ và ~z~ thì được ~1~ chuỗi đẹp là ~xyz~ (còn ~z~ là đối xứng nên không đẹp), chú ý rằng thầy cũng có thể giữ nguyên chuỗi ~s_2~ ban đầu vì nó cũng là một chuỗi đẹp, việc cắt ra không làm tăng số lượng chuỗi đẹp (điều này cho thấy để ra được số lượng chuỗi đẹp lớn nhất là ~1~, ta có thể có nhiều cách cắt); còn với chuỗi ~s_3=cccc~ thì không có cách cắt nào để tạo thành chuỗi đẹp nên kết quả sẽ là ~0.~

Trong một buổi thi vấn đáp, thầy có nhiều sinh viên (không quá ~10^4~ em) và có một chuỗi ký tự gốc là ~s~. Thầy muốn giao task cho mỗi SV lấy một chuỗi con từ vị trí ~L~ đến ~R~ nào đó trong ~s~ và cắt nó ra thành càng nhiều chuỗi đẹp càng tốt. Để đổi đề cho mới lạ, có thể đôi lúc thầy còn chọn một vị trí bất kỳ trong ~s~ và sửa nó lại thành một ký tự khác. Là lớp trưởng gương mẫu, Luna được thầy giao cho giải hết số bài tập này trước để thầy có đáp án mà check với các bạn coi làm đúng hay sai. Bạn hãy cùng giúp Luna thực hiện công việc này nhé.

Input

Dòng đầu tiên là một chuỗi ~s~ có độ dài ~n~ không vượt quá ~10^4~ gồm các ký tự tiếng Anh viết thường. Dòng tiếp theo là một số ~q~ cho biết số lượng câu hỏi mà thầy đặt ra cho CLB, trong đó ~1 \le q \le 10^5.~ Mỗi dòng tiếp theo trong ~q~ dòng sẽ có một trong hai dạng:

• Dạng 1: gồm một số nguyên ~k~ với ~1 \le k \le n~ và một ký tự ~c~ nào đó, cho biết sẽ gán ~s[k]=c~.

• Dạng 2: gồm hai số nguyên ~L, R~ với ~1 \le L \le R \le n~, yêu cầu tính số lượng chuỗi đẹp nhiều nhất có thể cắt ra được từ chuỗi con xét từ vị trí ~L~ đến vị trí ~R.~ Cho biết rằng có không quá ~10^4~ câu hỏi loại này.

Output

Hãy trả lời tất cả các câu hỏi dạng ~2~ ở các dòng khác nhau.

Sample input

abcabc
3
2 1 6
1 2 a
2 1 6

Sample output

3
2

Giải thích: ban đầu thì có thể cắt thành ~3~ chuỗi đẹp như trong ví dụ của đề bài, sau khi sửa ký tự ~2~ thành ~a~ thì có chuỗi mới là ~aacabc~, dễ dàng kiểm tra được chỉ có thể cắt nó được thành tối đa ~2~ chuỗi đẹp, chẳng hạn: ~aa~, ~ca~, ~bc~ (gồm ~2~ chuỗi đẹp và ~1~ chuỗi không đẹp) hoặc ~aaca~, ~bc~.