24 성냥개비 퍼즐

24개의 성냥개비로 이루어진 3×3 격자 퍼즐을 생각하자. 처음에는 모든 성냥개비가 다음과 같이 놓여 있다.

+--+--+--+|..|..|..||..|..|..|+--+--+--+|..|..|..||..|..|..|+--+--+--+|..|..|..||..|..|..|+--+--+--+

연속한 두 개의 -는 가로 성냥개비 하나를, 연속한 두 개의 |는 세로 성냥개비 하나를 뜻한다. +는 성냥개비 끝점들이 만날 수 있는 위치이고, .은 빈 공간이다.

처음 격자에는 정사각형이 모두 14개 있다. 크기별로는 1×1 정사각형 9개, 2×2 정사각형 4개, 3×3 정사각형 1개이다.

정수 N과 K가 주어진다. 정확히 N개의 성냥개비를 제거하여 다음 조건을 모두 만족하는 격자를 만들어야 한다.

• 제거한 성냥개비의 개수는 정확히 N개이다.
• 남은 격자에서 완성된 정사각형의 개수는 정확히 K개이다.
• 남아 있는 모든 성냥개비는 적어도 하나의 완성된 정사각형의 변으로 사용되어야 한다.

조건을 만족하는 격자 하나를 출력하는 프로그램을 작성하라.

첫 줄에 정수 N과 K가 주어진다. (1 ≤ N < 24, 1 ≤ K < 14)

N은 제거할 성냥개비의 수이고, K는 남아 있어야 하는 정사각형의 수이다.

조건을 만족하는 격자를 10줄로 출력한다.

1. 성냥개비 끝점들이 만날 수 있는 모든 위치에는 +를 출력한다. 그 위치의 위, 아래, 왼쪽, 오른쪽에 성냥개비가 없어도 +를 출력해야 한다.
2. 성냥개비가 놓이지 않은 모든 위치에는 .을 출력한다.
3. 가로 성냥개비 하나는 연속한 두 개의 -로 출력한다.
4. 세로 성냥개비 하나는 연속한 두 개의 |로 출력한다.

입력은 항상 조건을 만족하는 답이 존재하도록 주어진다. 가능한 격자가 여러 개라면 아무 것이나 출력해도 된다.