No.2947 Sing a Song
タグ : / 解いたユーザー数 125
作問者 :
Michirakara
/ テスター :
rotti_coder
t9unkubj
Problem Statement
Michirakara loves singing songs.
Michirakara has decided to sing a song consisting of $N$ measures, where the $i$-th measure has $A_i$ notes.
However, Michirakara has forgotten the original lyrics, so he has decided to make up lyrics consisting only of his favorite words $S$ and $T$ that sing all the notes, and sing the song with them. (No note may be left blank.)
Singing $S$ requires $|S|$ notes, and singing $T$ requires $|T|$ notes. ($|X|$ denotes the length of the string $X$.)
Also, a measure must not change in the middle of a word of the modified lyrics.
Since Michirakara prefers the word $S$, among the lyrics he might sing when the number of times he sings $S$ is maximized, output any one, separating words by spaces and measures by newlines.
It is guaranteed that lyrics satisfying the conditions exist for the given input.
Input
$N$ $S$ $T$ $A_1$ $A_2$ $\dots$ $A_N$
Constraints
- $1\leq N\leq 2\times 10^5$
- $1\leq |S|,|T|\leq 2\times 10^5$
- $S,T$ are strings of lowercase English letters
- $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)$ are all positive integers
- It is guaranteed by the input that lyrics satisfying the conditions exist. (Added at 21:32:42)
Output
Output lyrics that Michirakara might sing, separating words by spaces and measures by newlines.
Print a newline at the end.
Sample
Sample 1
Input
4 og yhg 7 5 7 5
Output
og og yhg og yhg yhg og og og yhg
Sample 2
Input
3 abc cde 6 6 6
Output
abc abc abc abc abc abc
Sample 3
Input
3 abcd e 7 9 13
Output
abcd e e e abcd abcd e abcd abcd abcd e
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。