A. A Penchick's Tale
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
squawk squawk chirp quack chirp chirp squak [sic] Credits to Ephraim Wu for the photograph, and to Kris Darilay for the accompanying message

Have you heard the good news? Alice, Bob, and Cindy have a new friend, Penchick! Penchick has been helping them (and many students in NOI.PH) learn competitive programming, providing sage wisdom and moral support throughout their journeys. This shall be known as A Penchick's Tale (APT).

It is well known that Penchick can only say one of three things, and for each thing Penchick can say, one of Alice or Bob or Cindy becomes happy!

  • When Penchick says squawk, Alice's happiness increases by $$$a$$$.
  • When Penchick says chirp, Bob's happiness increases by $$$b$$$.
  • When Penchick says quack, Cindy's happiness increases by $$$c$$$.
We'll give you a pool of tiles, where each tile has some letter on it. Using these tiles, assemble a sentence that Penchick might say! Among all such sentences, construct any that maximizes the total happiness of Alice and Bob and Cindy.
Input

The first line of input contains the three space-separated integers $$$a$$$ and $$$b$$$ and $$$c$$$.

The second line of input contains a string $$$s$$$ encoding the pool of tiles, where each character in $$$s$$$ corresponds to a tile that has that letter on it.

Output

Output a single line containing some number of space-separated words, where each word is one of squawk or chirp or quack. If no sentence can be constructed, output penchickdead instead, which produces a happiness of $$$0$$$.

It must be the case that this entire sentence (except for the spaces) can be assembled using the tiles from the pool, and also that among all possible sentences, the total happiness of Alice and Bob and Cindy is maximized.

If there are multiple possible solutions, output any of them.

Scoring

$$$$$$\begin{align*}

&\begin{array}{|l|} \hline \text{Constraints For All Subtasks} \\ \hline 1 \leq |s| \leq 10^5 \\ \text{$s$ consists only of lowercase English letters} \\ 1 \leq a, b, c \leq 10^9 \\ \hline \end{array}\\

&\begin{array}{|c|c|l|} \hline \text{Subtask} & \text{Points} & \text{Constraints} \\ \hline 1 & \mathbf{50} & |s| \leq 10 \\ \hline 2 & \mathbf{20} & \text{$a = b = c = 1$,} \\ && \text{or the answer is }\mathtt{penchickdead}\text{} \\ \hline 3 & \mathbf{20} & \text{$a = 6$ and $b = c = 5$,} \\ && \text{or the answer is }\mathtt{penchickdead}\text{} \\ \hline 4 & \mathbf{10} & \text{No further constraints.} \\ \hline \end{array}\\

\end{align*}$$$$$$

Examples
Input
1 1 2
helpweekoldquesoequalscarsick
Output
squawk quack chirp
Input
3 2 1
kauciqhshwckpkhuiqqasacrwwuqcskupprrai
Output
squawk squawk chirp quack chirp chirp squawk