게임 안에서 책을 읽을 수 있다구요?

NYPC 2023 · Round 1

넥슨의 명작 게임 마비노기에는 게임 안에서 책을 읽을 수 있는 기능이 있다.

책은 시나리오 작성자가 작성한다. 작성한 파일에는 책의 내용과 함께, 플레이어에게 이 내용을 어떻게 보여줄 것인지 지정하는 태그(tag)가 포함된다.

실제로는 여러 가지가 있지만, 다음 두 가지 태그만 존재한다고 하자.

중앙정렬 태그: <CENTER>와 </CENTER> 사이에 있는 문자열은 가운데 정렬해야 한다. 좌우의 공백 문자가 합쳐서 홀수 개수인 경우, 왼쪽 공백을 오른쪽보다 하나 적게 쓴다.
우측정렬 태그: <RIGHT> 와 </RIGHT> 사이에 있는 문자열은 문서의 오른쪽 끝에 붙여서 출력해야 한다.

아무런 태그 안에 없는 경우 좌측정렬을 해야 한다. 그리고 항상 아래의 줄넘김 규칙을 지켜야 한다.

줄넘김 규칙: 단어 중간에 줄넘김이 발생하면 안 된다. 단어란 공백을 포함하지 않는 문자열을 의미한다.

또 위 규칙에서 필요한 것 외에는 공백을 넣어서는 안 되며, 출력하는 줄 수를 최소화해야 한다. 단, 처음 서로 다른 줄에 있는 단어는 출력에서 같은 줄에 위치하면 안된다. 줄 수가 최소인 출력이 여러 개인 경우 단어들을 가능한 앞쪽 줄에 출력해야 한다.

책의 내용과 출력할 문서의 폭이 주어졌을 때, 양식에 맞게 문서를 보여주는 프로그램을 작성하시오.

입력 형식

첫 줄에 책 내용의 줄 수 $N$ 과 출력할 문서의 폭 $M$ 이 공백으로 구분되어 주어진다. ( $1 \le N \le 50;$ $10 \le M \le 50$ )

이어지는 $N$ 개의 줄에 태그를 포함한 책의 내용이 입력으로 주어진다. 책의 내용에는 다음과 같은 제약이 있다.

태그는 한 줄 전체를 차지한다.
태그 사이에 문자열이 없는 경우는 없다.
빈 줄은 주어지지 않는다.
각 줄은 공백으로 시작하지도, 끝나지도 않는다.
한 단어의 길이가 출력 문서의 폭보다 크지 않다.
공백과 태그를 포함한 전체 글자 수는 $70\,000$ 을 넘지 않는다.
한 문장에는 태그가 최대 한 개 적용된다. 예를 들자면, <CENTER> <RIGHT> </RIGHT> </CENTER>와 같은 형태로는 나올 수 없다.
올바르지 않은 태그 구성은 주어지지 않는다. 예를 들자면, <CENTER> </RIGHT>와 같은 형태로는 나올 수 없다.
태그를 제외한 문자열은 영어 알파벳과 공백으로만 이루어진다.
두 개 이상의 연속한 공백 문자는 주어지지 않는다.

출력 형식

문제에서 요구한 양식에 맞게 출력한다. 단, 공백은 모두 -로 대체해서 출력한다.

예제 1

입력

7 10
<CENTER>
Hello world
</CENTER>
Hello world
<RIGHT>
Hello world
</RIGHT>

출력

--Hello--- --world--- Hello----- world----- -----Hello -----world

예제 2

입력

20 11 Lorem ipsum dolor sit amet consectetur adipiscing elit Duis tristique Nunc congue nisi vitae suscipit tellus mauris <CENTER> Nunc congue nisi vitae suscipit tellus mauris Integer quis Id venenati a condimentum vitae </CENTER> <RIGHT> Nisi est sit amet facilisis magna Volutpat ac tincidunt vitae semper quis </RIGHT>

출력

Lorem-ipsum dolor-sit-- amet------- consectetur adipiscing- elit------- Duis------- tristique-- Nunc-congue nisi------- vitae------ suscipit--- tellus----- mauris----- Nunc-congue ---nisi---- ---vitae--- -suscipit-- --tellus--- --mauris--- --Integer-- ---quis---- Id-venenati -----a----- condimentum ---vitae--- ---Nisi-est --------sit -------amet --facilisis ------magna Volutpat-ac --tincidunt ------vitae semper-quis

채점 방식

입력 케이스들은 다음과 같은 종류로 구별되며, 한 종류의 케이스를 다 맞혀야 그 종류에 배정된 점수를 받을 수 있다.

종류 1: 17점

태그가 없음.

종류 2: 38점

<CENTER>, </CENTER> 태그만 있음.

종류 3: 31점

<RIGHT>, </RIGHT> 태그만 있음.

종류 4: 14점

추가적인 제한 조건이 없음.