돌고 도는 돌림노래

돌림노래는 두 성부 이상이 같은 선율을 서로 다른 시각에 시작해서 부르는 방식이다. 위에 실린 동요 "Row, Row, Row Your Boat"는 잘 알려진 돌림노래다. 첫째 성부가 '*' 가운데 어느 하나에 이르면 새 성부가 들어올 수 있다.

노래의 각 음절은 정수 단위 시간만큼 소리를 낸다. 소리를 내지 않는 쉼도 기호 하나로 적고 같은 방식으로 지속 시간을 받는다. 각 기호의 지속 시간과 둘째 성부가 들어오는 시각을 알면 두 성부의 어느 기호가 같은 순간에 울리는지 계산할 수 있다.

같은 순간에 울리는 기호가 같은 열에 놓이도록 두 성부의 돌림노래를 출력하는 프로그램을 작성하라.

노래는 $L$줄이다. 노래의 $i$번째 줄마다 출력 두 줄을 낸다. 먼저 첫째 성부 줄, 다음에 둘째 성부 줄이다.

첫째 성부 줄에는 노래 $i$번째 줄의 기호만 담는다. 이 줄이 시간 구간 하나를 정한다. 구간은 그 줄의 첫 기호가 소리를 시작하는 시각에 열리고, 마지막 기호가 소리를 마치는 시각에 닫힌다.

둘째 성부 줄에는 둘째 성부가 이 구간 안에서 소리를 시작하는 노래의 모든 기호를 시각 순서로 담는다. 구간이 닫히는 시각에 정확히 시작하는 기호는 이 쌍이 아니라 다음 출력 쌍에 들어간다. 둘째 성부 줄의 마지막 기호는 구간이 닫힌 뒤까지 소리가 이어지기도 한다.

열은 0부터 센다. 어떤 기호도 덮지 않는 출력 줄의 자리에는 더하기 기호 '+'를 채운다. 줄은 마지막 기호로 끝나므로 '+'로 끝나는 줄은 없다. 각 기호는 다음 규칙이 허용하는 가장 왼쪽 열에서 시작한다.

• 같은 출력 줄의 두 기호 사이에는 '+'가 적어도 하나 놓인다.
• 첫째 성부 줄의 첫 기호는 0번 열에서 시작한다.
• 각자의 성부에서 같은 시각에 시작하는 두 기호는 같은 열에서 시작한다.
• 한 성부의 기호 $S_2$가 다른 성부의 기호 $S_1$보다 $K$ 시간 단위 늦게 시작하면, $S_2$는 $S_1$보다 적어도 $K$열 오른쪽에서 시작한다.

뒤의 두 규칙은 한 성부를 다른 성부와 견준다. 같은 성부에 속한 두 기호 사이에는 분리 규칙만 적용되고, 시작 시각의 차이는 적용되지 않는다.

둘째 성부 줄은 비어 있을 수 있고, 그때는 빈 줄을 출력한다. 둘째 성부의 기호 가운데 한 번도 출력되지 않는 것도 있다.

첫 줄에 정수 $L$과 $N$이 주어진다. $L$은 노래의 줄 수로 $0 < L \leq 10$이다. $N$은 둘째 성부가 들어오는 시각이고, 첫째 성부는 시각 0에 들어온다. $0 \leq N \leq 128$이다.

이어서 두 줄씩 $L$쌍이 주어진다.

각 쌍의 첫 줄에는 노래 그 줄의 기호가 주어진다. 기호는 공백이 아닌 문자로 이루어진 문자열이고, 이웃한 기호는 공백 한 칸으로 나뉜다. 이 줄의 길이는 최대 80자다.

각 쌍의 둘째 줄에는 위 줄의 기호마다 하나씩, 같은 순서로 양의 정수가 주어진다. 각 정수는 그 기호에 배정된 시간이고 $1 \ldots 128$ 범위다.

위에서 설명한 대로 노래 한 줄마다 두 줄씩, 모두 $2L$줄을 출력한다.