No.2947 Sing a Song
タグ : / 解いたユーザー数 95
作問者 : Michirakara / テスター : nouka28 rotti_coder t9unkubj
問題文
みちらから君は歌を歌うのが大好きです。
みちらから君は $N$ 小節からなり、$i$ 小節目に $A_i$ 個の音がある歌を歌うことにしました。
しかし、みちらから君は元の歌詞を忘れてしまったので、彼の好きな単語である $S$ と $T$ だけからなり、全ての音を歌う歌詞を作って歌を歌うことにしました。(音が空白になってはいけません)
$S$ を歌うには $|S|$ 個の音、 $T$ を歌うには $|T|$ 個の音が必要です。 ($|X|$ は文字列 $X$ の長さを表します。)
また、変更した歌詞の単語の途中で小節が変わってはいけません。
みちらから君は単語 $S$ の方が好きなので、$S$ を歌う回数を最大化した場合にみちらから君が歌う可能性のある歌詞のうち一つを各単語ごとに空白、各小節ごとに改行で区切って出力してください。
なお、与えられる入力について、条件を満たす歌詞が存在することは保証されています。
入力
$N$ $S$ $T$ $A_1$ $A_2$ $\dots$ $A_N$
制約
- $1\leq N\leq 2\times 10^5$
- $1\leq |S|,|T|\leq 2\times 10^5$
- $S,T$ は英小文字列
- $1\leq A_i\ (1\leq i \leq N)$
- $1\leq \sum_{i=1}^{N}{A_i}\leq 2\times 10^5$
- $N,A_i\ (1\leq i \leq N)$ は全て正整数
- 条件を満たす歌詞が存在することは入力から保証される。(21:32:42 追記)
出力
みちらから君の歌う可能性のある歌詞を各単語を空白、各小節を改行で区切って出力してください。
最後に改行してください。
サンプル
サンプル1
入力
4 og yhg 7 5 7 5
出力
og og yhg og yhg yhg og og og yhg
サンプル2
入力
3 abc cde 6 6 6
出力
abc abc abc abc abc abc
サンプル3
入力
3 abcd e 7 9 13
出力
abcd e e e abcd abcd e abcd abcd abcd e
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。