Problem F
Around and Around We Go

A round is a musical arrangement in which two or more voices repeat the same melodic line, at times offset from one another. One of the more famous rounds is the nursery rhyme "Row, Row, Your Boat", shown here.


In western music, an integer count of time units can be assigned to each syllable to indicate how long that syllable is sung. A rest of one or more time units can be treated as a syllable that simply isn’t sung. If you know the time allocated to each syllable, and the time offset at which a second voice begins singing the song, you can determine which words will overlap in the round.

You are to write a program to display a two-voice round so that syllables that are sung simultaneously in the two voices appear vertically aligned. For each line of the original input, there are to be two lines of output: one for the original line sung by the first voice and one to display syllables (if any) that are started by the second voice during the time period where the first voice is singing the indicated line. Syllables for each voice in the output must be separated by one or more underscores (’_’), with each syllable displayed as far to the left as possible, subject to the following constraints:

Consecutive syllables on a line are separated by at least one ’_’ character.

Two syllables that begin at the same time in their respective voices are displayed with their leftmost characters in the same column.

Consider syllables S1 and S2, either sung by the same or different voices, that are displayed within the same pair of output lines. If S2 is sung beginning $k$ time units after S1 begins, for $k \geq 1$, then the first character of S2 must be displayed at least $k$ columns to the right of the first character of S1.

In some cases there will be a first-voice line when no second-voice syllables are started. Print ’/’ for the second voice instead of an empty line.

It is possible (in fact, likely), that not all syllables of the second voice will be printed, as only those syllables that start while the first voice is active are to be displayed.


The first line contains two integers, $L$ and $D$, such that $1 \leq L \leq 10$ indicates the number of lines in the song and $0 \leq D \leq 128$ indicates the delay, in time units, between the time when the first voice signs the first syllable and the time when the second voice begins singing the first syllable.

The remainder of the input consists of $L$ pairs of lines. The first line in each pair contains the syllables of that line of the song. Adjacent syllables in the input will be separated by a single space The syllables are strings of any non-whitespace characters other than underscores or ’/’. This line contains at most 80 characters.

The second line in each pair will consist of positive integers, one per syllable from the first line of the pair, indicating the time allocated to the corresponding syllables. Each such integer $t$ will satisfy $1 \leq t \leq 128$.


For each dataset, display $2L$ lines corresponding to the two voices in the round, as described above.

Sample Input 1 Sample Output 1
2 16
Hot cross buns! = Hot cross buns! =
4 4 4 4 4 4 4 4
One a pen- ny, Two a pen- ny, Hot cross buns! =
2 2 2 2 2 2 2 2 4 4 4 4
Sample Input 2 Sample Output 2
5 32
And ev- ry-
1 1 1
one neath a vine and fig tree, = shall live in
2 1 1 2 2 2 2 1 1 1 1
peace and un- a- fraid. =
2 2 2 2 6 2
And in- to plow shares beat their swords.
2 1 1 2 2 2 2 4
Na- tions shall learn war no more =
2 2 2 2 2 2 1 3

Please log in to submit a solution to this problem

Log in