삼각 격자 위의 섬

삼각 격자는 한 변의 길이가 $1$인 정삼각형으로 평면을 빈틈없이 채운 것이다. 격자에서의 경로란, 이웃한 두 삼각형이 항상 한 변을 공유하도록 늘어놓은 단위 삼각형들의 유한 수열을 말한다.

유한개의 단위 삼각형이 이루는 도형에서, 그 안에 들어 있는 임의의 두 격자 삼각형이 도형 안의 삼각형들로만 이루어진 경로로 연결될 수 있으면 그 도형을 섬이라고 부른다.

그림 1.1, 1.2, 1.3의 도형은 섬이지만 그림 1.4의 도형은 섬이 아니다. 그림 2.2, 2.3, 2.5의 도형은 서로 합동이다.

$n \le 10$인 모든 $n$에 대해, $n$개의 단위 삼각형으로 만들 수 있는 서로 합동이 아닌 모든 섬을 체계적으로 기술하고, 그러한 섬이 몇 개인지 세고자 한다.

삼각형 열 개 이하로 이루어진 섬의 경계는 단위 격자 선분들로 이루어진 닫힌 꺾은선이다. 이 경계는 연필을 떼지 않고 각 선분을 정확히 한 번씩 지나 출발점으로 돌아오도록 따라 그릴 수 있으며, 어떤 꼭짓점은 두 번 이상 지나야 할 수도 있다(그림 2.4). 삼각형 열 개 이하의 섬에서는 경계가 항상 연결되어 있어 이런 식으로 따라 그릴 수 있다(그림 1.2의 도형과 달리).

경계를 따라 돌 때, 각 단위 선분을 지난 뒤 다음 중 하나로 방향을 튼다.

• a: 왼쪽으로 $120^\circ$ 회전
• b: 왼쪽으로 $60^\circ$ 회전
• c: 직진($0^\circ$)
• d: 오른쪽으로 $60^\circ$ 회전
• e: 오른쪽으로 $120^\circ$ 회전

섬을 한 바퀴 도는 각 닫힌 순회는 $\{a, b, c, d, e\}$ 위의 단어로 나타낸다. $i$번째 글자는 $i$번째 단위 선분을 지난 뒤 트는 방향이다. 단어의 길이는 경계의 선분 개수와 같으므로, 도형을 복원하는 데 꼭 필요하지는 않지만 마지막 선분 뒤의 회전까지 기록한다. 이 여분의 글자는 어떤 경계 기술을 출발점만 다른 다른 기술로 바꿀 때 유용하다.

단어 cdddcddd, dcdddcdd, cbbbcbbb는 그림 2.1의 도형을 도는 서로 다른 순회를 나타낸다. 단어 cbeddcde, adcabcbb, abcbbadc는 그림 2.2의 도형을 도는 서로 다른 순회를 나타낸다. 단어 acdabbcb, cddebced는 그림 2.3의 도형을 도는 서로 다른 순회를 나타낸다.

닫힌 순회를 도는 내내 도형의 내부가 항상 오른쪽에 있으면 그 순회를 시계 방향 순회라고 한다.

섬의 코드란 (1) 주어진 섬과 합동인 어떤 섬의 경계를 시계 방향으로 도는 순회를 나타내면서, (2) 그 조건을 만족하는 모든 단어 중 사전순으로 가장 작은 단어이다.

서로 합동인 그림 2.2와 2.3의 섬에 대해 모든 시계 방향 순회를 적으면

beddcdec, eddcdecb, ddcdecbe, dcdecbed, cdecbedd, decbeddc, ecbeddcd, cbeddcde

와

bcedcdde, cedcddeb, edcddebc, dcddebce, cddebced, ddebcedc, debcedcd, ebcedcdd

이고, 따라서 공통 코드는 이 단어들 중 가장 작은 bcedcdde이다. 그림 2.4에 있는 섬의 코드는 aadecddcddde이다.

다음 두 종류의 질의에 답하는 프로그램을 작성하라.

• 크기 $k$인 섬의 코드가 주어지면, 그 섬과 합동인 섬에 삼각형 하나를 더해 만들 수 있는 크기 $k + 1$인 모든 섬의 코드를 출력한다.
• 정수 $n$이 주어지면, 크기 $n$인 모든 섬의 코드를 출력한다.

첫 줄에 질의의 개수 $t$ ($1 \le t \le 5$)가 주어진다. 이어지는 $t$개의 줄에 각각 질의가 하나씩 주어진다.

• 1번 질의는 글자 K, 공백 하나, 그리고 삼각형 열 개 이하로 이루어진 섬의 코드로 이루어진다.
• 2번 질의는 글자 N, 공백 하나, 그리고 정수 $n$ ($1 \le n \le 10$)으로 이루어진다.

질의를 주어진 순서대로 답한다.

• 1번 질의에 대해서는, 주어진 섬과 합동인 섬에 삼각형 하나를 더해 만들 수 있는 섬들의 서로 다른 코드의 개수를 출력하고, 다음 줄에 그 코드들을 사전순으로 공백 하나씩 띄워 출력한다.
• 2번 질의에 대해서는, 크기 $n$인 섬들의 서로 다른 코드의 개수를 출력하고, 다음 줄에 그 코드들을 사전순으로 공백 하나씩 띄워 출력한다.