Time Limit: 3 sec / Memory Limit: 512 MB
配点 : 100 点
問題文
巷では「Saitoon」という二人対戦ゲームが流行っています。
今年も「Saitoon」の大会「Maximum-Saitoon-cup」(Maximum-cup-2018とは無関係です)が大盛況のうち無事に幕を閉じました。
この大会の運営の1人である埼大君は同運営の記録係から送られてきた大会の対戦結果の確認作業を行おうとしています。
大会の対戦結果はBNF記法で以下のように管理されています。
<CompetitionLog> | ::= | <GameResults> |
<GameResults> | ::= | <PlayerData><PlayerData> |
<PlayerData> | ::= | [<PlayerID><WinningOrLosing>] |
<PlayerID> | ::= | (<GameResults>) | (<number>) |
<WinningOrLosing> | ::= | o | x |
<number> | ::= | <digit> | <number><zero> | <number><digit> |
<digit> | ::= | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
<zero> | ::= | 0 |
また、大会の対戦結果についての詳細は以下の通りです。
- 大会はトーナメント形式で行われています。
- 対戦結果は <CompetitionLog> として送られてきます。
- 大会の各試合は <GameResults> で表されます。また、各試合は必ずどちらかが負け、どちらかが勝ちます。
- 各試合の対戦相手は隣り合った <PlayerData> で表されます。
- <PlayerID> は選手固有のIDについて表しています。中身が <number> のときはその数字が、 <GameResults> のときはその試合の勝者の <PlayerID> が当てはまります。
- <WinningOrLosing> はその試合でその選手が勝ったかどうかを表していて、oのときは勝ち、xのときは負けを表しています。
- 参加選手のIDは対戦結果を左から見ていった際に、各選手の <number> で表現される <PlayerID> の出現順に1~Nまで割り振られています。
この対戦結果と手元にある「各選手が何勝したかについてのデータ」を照合させて、正しかったら埼大君の仕事は完了です。
さて、さっそく照合を行おうとした埼大君ですが、ここで大変なことが起きていることに気が付きました。
送られてきた対戦結果の一部の情報がなくなっているのです。
幸い、手元に「各選手が何勝したかについてのデータ」があるため、なんとか復元できそうですが、埼大君の力では難しいようです。
そこで、埼大君は優秀なプログラマであるあなたに復元を頼むことにしました。
あなたの仕事は「各選手が何勝したかについてのデータ」が正しいと仮定した際の対戦結果の復元することです。
欠落した箇所は「?」で表されているので、そこにもともと何があったかを調べてください。
制約
- 12 \leq |S| \leq 200
- 2 \leq N \leq 16
- ?の数は1個以上min( \frac{|S|}{2},50)個以下です。
- 対戦結果の復元は一意に定まることが保証されています。
入力
入力は以下の形式で標準入力から与えられます。
S N a_{1} a_{2} ... a_{N}
一行目には情報が欠落した状態の対戦結果が与えられます。
二行目には参加した選手の人数が与えられます。
三行目には1~Nの各選手がこの大会で何勝したかについての情報がa_{1}~a_{N}で与えられます。
出力
正しい対戦結果を一行で出力してください。
入力例 1
[([(1)o][(2)x]??][([(?)x][(4)o])x] 4 2 0 0 1
出力例 1
[([(1)o][(2)x])o][([(3)x][(4)o])x]
選手のIDは左から1~Nと振られるので、3つ目の「?」には「3」が入ります。
復元した対戦結果は1の選手が2勝、2の選手が0勝、3の選手が0勝、4の選手が1勝となり、手元にあるデータと一致します。
入力例 2
?([?[(?)o]?(?([(2?o]??[?3)o][?4?x??x])?]??5)x??x???][????])x?[??)o? 7 1 2 1 0 0 1 1
出力例 2
[([([(1)o][([([(2)o][([(3)o][(4)x])x])o][(5)x])x])x][(6)o])x][(7)o]
復元先は必ず一意に定まります。