Đơn thức là biểu thức đại số chỉ gồm một số, hoặc một biến, hoặc một tích giữa các số và các biến. Ví dụ: \(2xyz\), \(3x^2y\), ... là các đơn thức

Nhập vào một xâu kí tự (chỉ chứa kí tự viết thường, không chứa số, dấu nhân) là tích của các biến, bạn hãy xuất ra đơn thức ở dạng tối giản dạng (x^m)(y^n)... (các biến được sắp xếp theo thứ tự bảng chữ cái, số mũ khác \(0\)).

Đầu vào

Một xâu kí tự duy nhất, độ dài không quá \(10^6\).

Đầu ra

Một xâu kí tự duy nhất là đơn thức sau khi rút gọn.

Ví dụ

Đầu vào 1:

abhhaab

Đầu ra 1:

(a^3)(b^2)(h^2)

Đầu vào 2:

axyyxbba

Đầu ra 2:

(a^2)(b^2)(x^2)(y^2)

Đầu vào 3:

aaaaa

Đầu vào 3:

(a^5)