Cho một xâu \(s\) chỉ gồm các kí tự a, b, c và d. Bạn cần thực hiện \(q\) truy vấn thuộc một trong hai dạng sau:

• 1 i c: \(i\) là số nguyên \((1 \le i \le |s|)\), \(c\) là kí tự a, b, c hoặc d, có nghĩa là kí tự ở vị trí \(i\) của xâu \(s\) được thay thành kí tự \(c\).
• 2 l r t: \(l\), \(r\) là số nguyên \((1 \le l \le r \le |s|)\), \(t\) là một xâu chỉ chứa các kí tự a, b, c và d \((1 \le |t| \le 10)\), có nghĩa là nếu viết tiền tố của xâu \(ttt\dots\) (xâu chứa vô số xâu \(t\) được viết liên tiếp nhau) dưới xâu \(s\) từ vị trí \(l\) đến \(r\) thì số lượng vị trí mà kí tự của xâu \(s\) trùng với kí tự được viết dưới nó là bao nhiêu?

Input

• Dòng đầu tiên chứa xâu \(s\) \((1 \le |s| \le 10^5)\).
• Dòng tiếp theo chứa số nguyên \(q\) \((1 \le q \le 10^5)\).
• Trong \(q\) dòng tiếp theo, mỗi dòng chứa một trong hai dạng 1 i c hoặc 2 l r t.

Output

• Với mỗi truy vấn dạng 2 l r t, in ra một số nguyên là kết quả.

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(1 \le |s|, q \le 1000\).
• Subtask \(2\) (\(30\%\) số điểm): Tất cả các truy vấn dạng 2 l r t đều có \(|t| = 1\).
• Subtask \(3\) (\(50\%\) số điểm): Không ràng buộc gì thêm.

Example

abcdcdd
4
2 2 5 bc
2 3 7 cdc
1 5 a
2 3 7 cdc 

3
4
3