CW_2 - COMPRESSED WORDS-2


Helen has come up with a way to shorten the length of the messages send to their counterparts in the past. Helen considers only individual words, and uses the following rules to define a "shortened word":

  1. a single, lower-case letter is a compressed word
  2. (e1 e2 ... et n) where t and n are non-negative integers and ei is a compressed word.

You should observe that a compressed word of one character is the same as an uncompressed word. To uncompress the compressed word (e1 e2 ... et n) we uncompress each ei, concatenate those uncompressed words into a new word, and repeatedly concatenate that word n times. For example:

  • a would be uncompressed as a,
  • (a 3) would be uncompressed as aaa,
  • (a (b c d 2) 3) would be uncompressed as abcdbcdabcdbcdabcdbcd.

Write a program to uncompress a compressed word.

Input

First line T, the number of test cases (=12). Next T lines contain correctly formed compressed words.

Output

For each case print in a new line the uncompressed word without spaces.

Constraints

0 < n <= 10000, 1 <= t <= 26

length of expressions will be less than 100, and the compressed worf will consist of latters (a-z), numbers and brackets.

Note: There may or may not be more than one space between brackets and letters or number. For example ( a ), (a3), ( a 3 ) are all correct expressions.

Example

Input:
3
a
( a 3 )
( a ( b c d 2 ) 3 )

Output:
a
aaa
abcdbcdabcdbcdabcdbcd

hide comments
Francky: 2014-04-08 19:07:27

What are the constraints on e_i : it is said non-negative integers, but what are the full constraints ?

REPLY-- it is mentioned that it will be characters(a-z) and time is sufficient for python
--ans--> OK, I made a confusion between e_i and n, ...

Last edit: 2014-04-08 19:12:50
Mitch Schwartz: 2014-04-08 19:07:03

"for eg ( a ),(a3),( a 3 ) are all correct expressions"

"( a )" is not a correct expression according to the definition...

REPLY-- it is correct since it is correct regular expression..i will update it

Last edit: 2014-04-08 19:06:19
Bhavik: 2014-04-08 19:07:03

i had the problem of internal error with CW2 which i could not resolve before i created this one...so i put up this one rather than CW2...though i rectified it later
--ans(Francky)--> You avoid a full answer, ... ok.
What do you think about problem title not capitalized? 2c question. ;-)
And : Is a Python solution possible, according to your test ?

Last edit: 2014-04-08 19:03:43
Mitch Schwartz: 2014-04-08 19:07:03

It's not a big deal here, but in general it's best to write constraints such that any valid test case is solvable. E.g. you could write a constraint on output size to make clear that cases like (...(a 9) 9) 9)...) [as long as possible] aren't included.

Francky: 2014-04-08 19:07:03

Please explain the troubles with CW2, it will be appreciate.


Added by:Bhavik
Date:2014-04-08
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:CW