Cho một xâu ký tự (S) chỉ gồm các chữ cái tiếng Anh thường.

Thực hiện phép biến đổi sau cho đến khi không thể tiếp tục:

• Nếu tồn tại hai ký tự giống nhau đứng liền kề nhau thì xóa cả hai ký tự đó khỏi xâu.

Sau mỗi lần xóa, các phần còn lại của xâu được ghép lại với nhau và có thể tạo ra những cặp ký tự giống nhau mới cần tiếp tục xóa.

Hãy xác định xâu cuối cùng thu được.

Dữ liệu vào

• Gồm một dòng chứa xâu (S).

Dữ liệu ra

• Xâu còn lại sau khi thực hiện toàn bộ các phép xóa.
• Nếu xâu trở thành rỗng, ghi ra dòng trống.

Ví dụ 1

abbaca

ca

Giải thích

abbaca
→ aaca      (xóa bb)
→ ca        (xóa aa)

Không còn hai ký tự giống nhau đứng cạnh nhau.

Ví dụ 2

INPUT

azxxzy

OUTPUT

ay

Giải thích

azxxzy
→ azzy      (xóa xx)
→ ay        (xóa zz)

Ràng buộc

• (~1 \le |S| \le 10^6~)
• Xâu chỉ gồm các ký tự từ 'a' đến 'z'.

Yêu cầu

Xây dựng chương trình có độ phức tạp thời gian (O(n)).