가로세로 퍼즐

다음과 같은 3x3 가로세로 퍼즐을 만들려고 한다.

가로줄 힌트

1. PC를 식히는 데 쓰는 장치
2. 고체 상태의 물
3. 얻다

세로줄 힌트

1. 작고 부드러우며 단 과일
2. 강한 카드
3. 낚시꾼의 도구

6개의 단어가 주어진다. 이 중 3개를 가로줄로, 나머지 3개를 세로줄로 사용해 3x3 퍼즐을 만들어라. 위에서 아래로 읽은 각 세로줄도 주어진 단어 중 하나여야 한다. 모든 단어는 입력에 주어진 횟수만큼만 사용할 수 있다.

6개의 줄에 알파벳 대문자 3글자로 이루어진 단어가 하나씩 주어진다. 단어들은 사전순으로 정렬되어 있으며, 같은 단어가 여러 번 주어질 수 있다.

6개 단어를 모두 사용해 3x3 퍼즐을 만들 수 없다면 0을 출력한다. 만들 수 있다면 퍼즐의 가로줄 3개를 위에서부터 한 줄에 하나씩 출력한다.

가능한 퍼즐이 여러 개라면, 출력할 세 줄을 차례대로 이어 붙인 9글자 문자열이 사전순으로 가장 앞서는 것을 출력한다.