Xóa Mẫu ABC · canuc80k0903 · Thuật toán Canuc80k

Liên tục xóa lần xuất hiện ngoài cùng bên trái của chuỗi con ABC cho đến khi không còn, rồi in chuỗi cuối cùng.

Input

Input gồm một chuỗi $S$ trên bảng chữ cái ${A, B, C}$ .

Output

In chuỗi còn lại sau khi không thể xóa thêm ABC; nếu chuỗi rỗng thì không in ký tự nào trước dấu xuống dòng.

Constraints

$1 \leq ∣ S ∣ \leq 2 \cdot 1 0^{5}$ .
Mỗi ký tự của $S$ là $A, B$ hoặc $C$ .

Scoring

Subtask $1$ ( $50%$ số điểm): $∣ S ∣ \leq 2000$ .
Subtask $2$ ( $50%$ số điểm): Không có giới hạn bổ sung.

Example

Test 1

Input

AABCABCBA

Output

ABA

Giải thích: Xóa ABC bắt đầu ở vị trí thứ hai cho chuỗi AABCBA. Ba ký tự ở vị trí thứ hai đến thứ tư lại tạo thành ABC; xóa tiếp thì còn ABA, không chứa mẫu cần xóa.

Phân tích: Dùng một chuỗi kết quả như một stack. Đọc lần lượt từng ký tự của S và đẩy vào cuối stack. Nếu ba ký tự cuối vừa trở thành ABC, xóa ngay ba ký tự đó.
Chứng minh tính đúng đắn: Sau khi xử lý một tiền tố của S, stack đúng bằng kết quả sau khi xóa hết mọi mẫu ABC có thể xuất hiện trong tiền tố ấy. Khi thêm một ký tự mới, mẫu mới duy nhất có thể xuất hiện phải kết thúc tại cuối stack, nên chỉ cần kiểm tra ba ký tự cuối. Nếu chúng là ABC, xóa chúng sẽ khôi phục bất biến. Khi đã đọc hết chuỗi, stack vì thế là chuỗi ổn định cần tìm.
Độ phức tạp: Mỗi ký tự được thêm một lần và bị xóa nhiều nhất một lần. Thời gian là O(|S|) và bộ nhớ là O(|S|).