Cho một biểu thức số học ở dạng trung tố (infix) gồm các toán hạng là chữ cái in hoa (A, B, C, ...) và các toán tử nhị phân ~+~, ~-~, ~*~, ~/~, cùng với dấu ngoặc tròn để biểu thị thứ tự ưu tiên.

Hãy viết chương trình chuyển đổi biểu thức này sang hai dạng:

• Biểu thức tiền tố (prefix)

Giải thích:

• Biểu thức trung tố (infix): Toán tử nằm giữa hai toán hạng, ví dụ: ~(A + B)~
• Biểu thức hậu tố (postfix): Toán tử đứng sau hai toán hạng, ví dụ: ~AB+~
• Biểu thức tiền tố (prefix): Toán tử đứng trước hai toán hạng, ví dụ: ~+AB~

Yêu cầu:

• Sử dụng cấu trúc dữ liệu stack để xử lý biểu thức.
• Giả sử biểu thức trung tố đầu vào là hợp lệ, không chứa khoảng trắng.

Input

• Một dòng duy nhất chứa biểu thức trung tố hợp lệ ~E~ có độ dài không quá 100 ký tự.

Output

• Dòng duy nhất là biểu thức tiền tố (prefix)

Ví dụ:

Input

(A+B)*(C-D)

Output

*+AB-CD