Baby Song

Boci, boci tarka, se füle, se farka… This is the beginning of a well-known Hungarian nursery rhyme. The old melody returns in 2019 in a special way. We have collected the money on Kickstarter to create the world's first xylophone with a touch screen (and with a lot of other useful extras)! We need the best professional for programming such complicated devices, so you are our choice.

The device can play tones in two octaves. Let's denote these tones with the characters c, d, e, f, g, a, h, C, D, E, F, G, A, H. One special feature of the device is the repeat function. This means that we don't have to repeat a part of a melody multiple times, it is enough to be played once, and the device can repeat it.

Input Specification

Each line of the input describes a melody. A melody is defined inductively as follows:

• A nonempty sequence of elements of the tone set c, d, e, f, g, a, h, C, D, E, F, G, A, H is a melody.
• If M₁ and M₂ are melodies, then M₁+M₂ is a melody containing first the tones of M₁, then the tones of M₂.
• If M is a melody, then (M)*n is a melody containing the tones of M repeated n times (1 ≤ n ≤ 9).

No lines of the input contain more than 100 characters.

Output Specification

For each melody, print the sequence of tones played by the device, now without operators (+, *) and parentheses.

Sample Input

1. ceceggceceggCbagfagfedcc
2. ((ce)*2+(g)*2)*2+(Cbagfagfedcc)*1
3. (ceceggceceggCbagfagfedcc)*1
4. (cecegg)*2+Cbagfagfedcc

download as text file

Output for Sample Input

1. ceceggceceggCbagfagfedcc
2. ceceggceceggCbagfagfedcc
3. ceceggceceggCbagfagfedcc
4. ceceggceceggCbagfagfedcc

download as text file