Odin

Time limit2sMemory limit1024 MB

Summary

Given a bracketed formula, the task rewrites first-level brackets as curly braces, second-level as square brackets, and deeper ones as round brackets.

Level: Easy2 of 10
Topics: String, Simulation
Solved: No attempts yet

Problem

Ragnarok is about to begin any minute now. But Odin does not know exactly when it will come.

Loki, the cleverest of the gods, gave Odin a formula for computing the time of Ragnarok. Odin has only one eye, so he finds it hard to track all the brackets in an expression. He decided to replace first-level brackets with curly braces, second-level brackets with square brackets, and leave the rest as round brackets. For example, $x \* (y + (z \* (5 + 3)))$ becomes $x \* \\{y + \[z \* (5 + 3)]\\}$ .

Odin cannot program, so the program is up to you. Do not anger Odin.

Input

The first and only line of the input file contains a formula made of Latin letters, arithmetic operators, spaces, digits, and brackets. The brackets form a correct bracket sequence. The length of the formula does not exceed $10^5$ .

Output

Print this string in a format that is easy for Odin to read.

Examples2

Example 1

Input

x * (y + (z * (5 + 3)))

Expected output

x * {y + [z * (5 + 3)]}

Example 2

Input

1 * (0 + k + i) * (t - h + (0 * r))

Expected output

1 * {0 + k + i} * {t - h + [0 * r]}