The Genome Database of All Space Life

時間制限 : 5 sec, メモリ制限 : 65536 KB
英語版はこちら

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

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

データベースに格納したいのは.英大文字からなる単なる文字列である.ただし,宇宙生物のゲノム配列は,一般に多くの繰り返しを含んでおり,非常に長くなりうる.そこで,ストレージの有効利用のため,文字列 seqN 回の繰り返しを,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 が含まれる. si は空白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

Source: ACM International Collegiate Programming Contest , Japan Domestic Contest, Yokohama, Japan, 2006-06-30
http://www.acm-japan.org/icpc2006/