워드 클록

여러분은 워드 클록을 만드는 회사에서 일한다. 워드 클록은 일반적인 시계판 대신 글자 격자를 사용해 시간을 표시하는 시계다. 시계 안에는 글자마다 LED가 하나씩 들어 있고, 켜진 글자가 현재 시간을 문장으로 나타내도록 불을 밝힌다. 아래 예시를 보자.

그림 J.1: 3:15를 표시하는 워드 클록의 예. 효율을 위해 FIVE와 EIGHT처럼 단어끼리 겹칠 수 있다.

최근 회사가 해외로 진출하면서 여러분은 여러 언어의 시계판을 설계하는 일을 맡았다. 이를 위해 번역가 팀이 시간을 말하는 데 필요한 모든 단어 목록을 만들고, 문장에서의 위치에 따라 묶음으로 나누어 두었다. 위 예시에서는 ONE부터 TWELVE까지의 숫자가 한 묶음을 이루고, PAST와 TO도 마찬가지다. 따라서 문법은 신경 쓰지 않아도 되고, 한 번에 한 묶음만 다루면 된다.

이런 단어 묶음과 부분 격자의 크기가 주어졌을 때, 모든 단어를 격자에 배치하는 방법을 찾거나 불가능하다고 판정하라. 단어는 왼쪽에서 오른쪽으로 써야 하며, 한 줄에서 다음 줄로 넘어갈 수 없다.

입력은 다음과 같다.

• 세 정수 h, w, n이 주어지는 한 줄. 여기서

  • h (1 ≤ h ≤ 18)는 격자의 높이;
  • w (1 ≤ w ≤ 18)는 격자의 너비;
  • n (1 ≤ n ≤ 18)은 단어의 수.

• 격자에 넣을 n개의 단어가 주어지는 한 줄. 각 단어는 영어 대문자 1자 이상 18자 이하로 이루어진다. 단어는 서로 다르다.

해가 없으면 impossible을 출력한다. 그렇지 않으면 워드 클록의 격자를 나타내는 h개의 줄을 출력한다. 각 줄은 대문자 w자로 이루어진다. 해가 여러 개면 아무거나 출력해도 된다.