Problem E: 全宇宙生命ゲノムデータベース

西暦2300年，宇宙連邦共和国の生命科学局では，全宇宙生物のゲノム配列を解読し，ゲノムデータベースを構築する野心的なプロジェクトを開始した．長年にわたる研究の結果，いかなる種のゲノムも高々26種類の分子(AからZで表す)からなることがわかっている．

データベースに格納したいのは．英大文字からなる単なる文字列である．ただし，宇宙生物のゲノム配列は，一般に多くの繰り返しを含んでおり，非常に長くなりうる．そこで，ストレージの有効利用のため，文字列 seq の N 回の繰り返しを，N(seq)と圧縮して記す．ここで，N は 2 以上の自然数であり，seq の長さは 1 以上である．また，seq が 1 文字 c の場合には，さらに括弧を省略して Nc と記しても良いことにする．

たとえば，

ABABABABXYXYXYABABABABXYXYXYCCCCCCCCCC

というゲノム配列の断片なら，まず，先頭部分の ABABABAB を圧縮表現に置き換え

4(AB)XYXYXYABABABABXYXYXYCCCCCCCCCC

と記すことができる．続く XY, AB, C の繰り返しも同様に置換すると

4(AB)3(XY)4(AB)3(XY)10C

となる． C は1文字なので括弧を省略した．最後に，4(AB)3(XY) の繰り返しも圧縮表現に置き換えると

2(4(AB)3(XY))10C

を得る．この例からわかるように，括弧は多重にネストしてもかまわない．

あなたの仕事は，圧縮されたゲノム配列を復元するプログラムを作ることである．

Input

入力は複数の行から構成され，各入力行には文字列 s と整数 i が含まれる． s と i は空白1個で区切られる．

s は，上で述べた方法でゲノム配列を表したものであり，最短1文字，最長100文字と仮定してよい．しかし，もちろん，s が表現するゲノム配列の長さは， 100文字よりもはるかに長い可能性がある． s 中に出現する繰り返し回数を表す自然数は，高々1,000と仮定してもかまわない．

i は 0 以上100万以下である．

最後の入力行の直後に，空白で区切られた 2 個の 0 からなる行が置かれ，入力の終わりを表す．

Output

各入力行に対して，s が表現するゲノム配列の i 番目の文字を含む行を出力しなさい．ただし，ゲノム配列の長さが不足して i 番目の文字がない場合には， 0 のみを含む行を出力すること．これら以外の文字が出力行に含まれないようにすること． なお，インデックスは 1 ではなく 0 から始まる．したがって，列の先頭の文字は，0 番目である．

Sample Input

ABC 3
ABC 0
2(4(AB)3(XY))10C 30
1000(1000(1000(1000(1000(1000(NM)))))) 999999
0 0

Output for the Sample Input

0
A
C
M

---