Bà Nội Đan Len

Time limit: 1.0s Memory limit: 256M Read editorial

Problem

Mùa đông năm nay, bà nội của Mai quyết định đan cho cả nhà mỗi người một chiếc khăn len. Bà đan cả đời nên chẳng bao giờ viết công thức dài dòng. Thay vào đó, bà ghi vào cuốn sổ nhỏ những dòng ký hiệu rút gọn như thế này:

2[k3[p]]k

Mai lật sổ ra và mất cả buổi tối mới hiểu được quy tắc của bà:

  • Mỗi chữ cái thường là một loại mũi đan. Ví dụ k là mũi lên, p là mũi xuống. Bà có rất nhiều loại mũi nên dùng đủ cả bảng chữ cái.
  • Ký hiệu n[S] nghĩa là đan đoạn \(S\) lặp lại đúng \(n\) lần liên tiếp. Trong đó \(n\) là một số nguyên dương, viết ngay trước dấu [ và không có chữ số \(0\) ở đầu.
  • Đoạn \(S\) bên trong ngoặc cũng là một công thức, nên có thể chứa những cặp ngoặc khác lồng vào bên trong. Đoạn \(S\) cũng có thể rỗng (có lẽ bà ghi để nhắc mình... nghỉ tay uống trà).

Ví dụ, 2[k3[p]]k được khai triển như sau: 3[p] là ppp, nên k3[p] là kppp, lặp \(2\) lần thành kpppkppp, cuối cùng thêm một mũi k thành kpppkpppk.

Mai muốn nhập công thức vào chiếc máy đan tự động mới mua cho bà, nhưng máy chỉ hiểu dãy mũi đan đã được khai triển đầy đủ. Hãy giúp Mai viết chương trình khai triển công thức của bà nhé.

"Đan một mũi thì dễ, đan một trăm nghìn mũi theo đúng thứ tự mới là nghề."

-- Bà nội của Mai

Input

  • Một dòng duy nhất chứa công thức \(s\) \((1 \leq |s| \leq 10^4)\), chỉ gồm chữ cái thường a-z, chữ số và các dấu ngoặc vuông [, ].
  • Dữ liệu đảm bảo công thức hợp lệ theo quy tắc ở trên: các ngoặc được đóng mở đúng cặp, mỗi dấu [ đều đứng ngay sau một số \(n\) \((1 \leq n \leq 10^9)\), và mỗi số đều đứng ngay trước một dấu [.
  • Dữ liệu đảm bảo dãy mũi đan sau khi khai triển có độ dài từ \(1\) đến \(2 \times 10^5\).

Output

  • In ra dãy mũi đan sau khi khai triển đầy đủ.

Sample

#InputOutput
1
3[ab]c
abababc
2
2[x3[yz]]10[o]
xyzyzyzxyzyzyzoooooooooo

Note

Sample 1: 3[ab] là ab lặp \(3\) lần thành ababab, sau đó thêm c.

Sample 2:

  • 3[yz] là yzyzyz, nên x3[yz] là xyzyzyz.
  • 2[x3[yz]] lặp đoạn trên \(2\) lần thành xyzyzyzxyzyzyz.
  • 10[o] là \(10\) chữ o (chú ý số lặp có thể có nhiều chữ số).

Comments

There are no comments at the moment.

Code editor