String Expansion

You are given a string s consisting of lowercase alphabet characters, digits, and brackets"(" and ")". s encodes a longer string and is represented as concatenation of n(t), where n is the number of times t is repeated, and t is either a regular string or it’s another encoded string recursively.

Return the expanded version of s. Note that t can be the empty string.

https://binarysearch.com/problems/String-Expansion

Examples

Example 1

Input

• s = 2(ye)0(z)2(2(po)w)

Output

• answer = yeyepopowpopow

Solution