Note: Giới hạn thời gian của bài này là 4s, gấp đôi so với thông thường. Bộ nhớ là 512MB, gấp đôi so với thông thường

Pareidolia là một hội chứng mà mắt bạn có xu hướng nhìn thấy những thứ quen thuộc trong ảnh mà thậm chí không tồn tại (ví dụ như thấy một gương mặt trên đám mây). Nông dân John, một người với niềm yêu thương những chú bò của mình, thường xuyên thấy những thứ liên quan đến bò trong mọi vật dụng. Ví dụ, nếu như bác John thấy xâu "bqessiyexbesszieb", đôi mắt của bác sẽ tự động bỏ đi một số kí tự và nhầm lẫn thành "bessiexbessieb" - một xâu gồm \(2\) xâu con liên tiếp "bessie" (tên một cô bò mà bác rất yêu quý).

Với một xâu \(s\), ta gọi \(B(s)\) là số lượng xâu con liên tiếp "bessie" nhiều nhất có thể đạt được từ xâu \(s\) nếu xoá đi \(0\) hoặc nhiều kí tự trong xâu \(s\). Trong ví dụ trên, \(B(\)"bqessiyexbesszieb"\() = 2\). Và với mỗi xâu \(t\), gọi \(A(t)\) là tổng các \(B(s)\) với \(s\) là xâu con liên tiếp của xâu \(t\).

Bác John đưa cho bạn một xâu \(t\) có độ dài không quá \(2 \times 10^5\) chỉ bao gồm các chữ cái in thường. Hãy tính toán \(A(t)\) và sự thay đổi của \(A(t)\) sau \(U\) \((1 \le 2 \times 10^5)\) lần cập nhật, mỗi lần sẽ thay đổi một kí tự trong xâu \(t\). Mỗi lần cập nhật đều áp dụng trực tiếp lên xâu \(t\).

Input

• Dòng đầu tiên chứa xâu \(t\).
• Dòng tiếp theo chứa số \(U\).
• Trong \(U\) dòng tiếp theo, mỗi dòng gồm số nguyên \(p\) \((1 \le p \le |t|)\) và một chữ cái in thường \(c\), nghĩa là thay đổi \(t_p\) thành \(c\).

Output

• Gồm \(U + 1\) dòng, dòng đầu tiên là \(A(t)\) của xâu \(t\) ban đầu, \(U\) dòng tiếp theo là \(A(t)\) sau mỗi lần cập nhật xâu.

Scoring

• Subtask \(1\): \(|t|, U \le 300\).
• Subtask \(2\): \(U \le 10\).
• Subtask \(3\): \(|t|, U \le 10^5\).
• Subtask \(4\): Không có ràng buộc gì thêm.

bessiebessie
3
3 l
7 s
3 s

14
7
1
7