Một xâu ký tự được gọi là đối xứng nếu như ta đọc nó từ trái sang phải hay từ phải sang trái đều như nhau. Ví dụ, các xâu a, aa, appa, và level là những xâu đối xứng.

Cho trước một xâu \(S\) rỗng, bạn hãy lập trình xử lý hai loại truy vấn sau đây:

• \((1)\) Thêm một ký tự in thường vào phía sau xâu \(S\).
• \((2)\) Xóa một ký tự ở phía sau xâu \(S\).

Sau khi xử lý mỗi truy vấn, bạn hãy đếm số lượng xâu con đối xứng của \(S\) rồi in ra bộ xuất chuẩn. Một xâu con của \(S\) là xâu thu được khi ta xóa một số ký tự ở bên trái và một số ký tự ở bên phải của \(S\) (tính cả trường hợp không xóa ký tự nào).

Input

Dòng đầu chứa số nguyên dương \(Q\) thể hiện số lượng truy vấn.

Dòng tiếp theo chứa một xâu độ dài \(Q\) thể hiện nội dung của tất cả \(Q\) truy vấn trong đề, theo thứ tự từ trái sang phải. Ký tự thứ \(i\) là - nếu truy vấn tương ứng là truy vấn loại \((2)\), ngược lại, ký tự thứ \(i\) sẽ là một chữ cái in thường thể hiện ký tự ta cần chèn vào phía sau xâu \(S\) ở truy vấn \((1)\).

Dữ liệu đảm bảo độ dài của \(S\) luôn dương sau bất kỳ truy vấn nào.

Output

In ra \(Q\) số nguyên trên cùng một dòng, thể hiện kết quả (số lượng xâu con đối xứng) của từng truy vấn tương ứng.

Ví dụ

Sample input

17
queryreuq--------

Sample output

1 2 3 4 5 7 9 11 13 11 9 7 5 4 3 2 1

Ràng buộc

Trong tất cả các test:

• \(1\leq Q\leq 10^4\).

Subtasks

• Subtask 1: \(Q\leq 500\).
• Subtask 2: Không có ràng buộc gì thêm.