시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 7 4 4 57.143%

문제

24 성냥개비 퍼즐은 혼자서 즐길 수 있는 아주 재미있는 게임이다.

놀이 방법은 아래와 같다.

먼저, 24개의 성냥개비를 아래 그림처럼 놓는다.

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

두 개의 연속된 '-'는 가로로 놓인 성냥개비를, 두 개의 연속된 '|'는 세로로 놓인 성냥개비를 의미한다.

또한, '+' 표시는 성냥개비 두 개 이상의 끝점이 만날 수 있는 위치를 의미하며, '.' 은 빈 공간이다.

이제 위의 그리드에는 총 14개의 정사각형이 있다. (1*1 정사각형 9개, 2*2 정사각형 4개, 3*3 정사각형 1개)

성냥개비를 다 놓은 이후, 적당한 정수 N과 K를 고른다.

이제 아래 조건을 만족하도록 그리드에서 성냥개비를 제거하면 된다.

  • 그리드에서 제거하는 성냥개비의 개수는 정확히 N개이다.
  • 남은 그리드에서 찾을 수 있는 정사각형의 수는 정확히 K개이다.
  • 남아 있는 모든 성냥개비는 최소한 하나의 정사각형을 이루는 데 쓰여야 한다.

재혁이는 지난 1년간 매일 동아리방에서 혼자 성냥개비 퍼즐을 가지고 놀았지만 성냥개비 퍼즐에 성공한 경우가 없었다.

재혁이는 이것이 자신의 실수가 아니라 N과 K의 값을 잘못 골라 퍼즐의 정답이 존재하지 않는 것이 원인이라 생각했다.

남규는 이런 재혁이의 핑계를 깨부수기 위해, N과 K가 주어지면 해당 퍼즐의 정답을 찾아주는 프로그램을 작성하려 한다.

입력

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

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

출력

문제의 조건을 만족하는 그리드를 아래와 같이 출력한다.

  1. 성냥개비 두 개가 만날 수 있는 모든 점 : '+' (성냥개비가 해당 위치의 상,하,좌,우에 놓이지 않아도 '+'를 출력해야 한다).
  2. 성냥개비가 놓여 있지 않은 모든 점 : '.'
  3. 가로로 놓인 성냥개비 : 연속된 두 개의 '-'
  4. 세로로 놓인 성냥개비 : 연속된 두 개의 '|'

항상 정답이 존재하는 입력만 주어진다.

만약 문제의 조건을 만족하는 그리드가 여러 가지라면, 임의의 하나를 출력한다.

예제 입력 1

5 4

예제 출력 1

+--+--+--+
|..|..|..|
|..|..|..|
+--+--+..+
|.....|..|
|.....|..|
+--+--+..+
|........|
|........|
+--+--+--+
W3sicHJvYmxlbV9pZCI6IjMxNjAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiIyNCBcdWMxMzFcdWIwZTVcdWFjMWNcdWJlNDQgXHVkMzdjXHVjOTkwIiwiZGVzY3JpcHRpb24iOiI8cD4yNCBcdWMxMzFcdWIwZTVcdWFjMWNcdWJlNDQgXHVkMzdjXHVjOTkwXHVjNzQwIFx1ZDYzY1x1Yzc5MFx1YzExYyBcdWM5OTBcdWFlMzggXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWM1NDRcdWM4ZmMgXHVjN2FjXHViYmY4XHVjNzg4XHViMjk0IFx1YWM4Y1x1Yzc4NFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViMTgwXHVjNzc0IFx1YmMyOVx1YmM5NVx1Yzc0MCBcdWM1NDRcdWI3OThcdWM2NDAgXHVhYzE5XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWJhM2NcdWM4MDAsIDI0XHVhYzFjXHVjNzU4IFx1YzEzMVx1YjBlNVx1YWMxY1x1YmU0NFx1Yjk3YyBcdWM1NDRcdWI3OTggXHVhZGY4XHViOWJjXHVjYzk4XHViN2ZjIFx1YjE5M1x1YjI5NFx1YjJlNC48XC9wPlxyXG5cclxuPHByZT5cclxuKy0tKy0tKy0tKyBcclxufC4ufC4ufC4ufCBcclxufC4ufC4ufC4ufCBcclxuKy0tKy0tKy0tKyBcclxufC4ufC4ufC4ufCBcclxufC4ufC4ufC4ufCBcclxuKy0tKy0tKy0tKyBcclxufC4ufC4ufC4ufCBcclxufC4ufC4ufC4ufCBcclxuKy0tKy0tKy0tKyA8XC9wcmU+XHJcblxyXG48cD5cdWI0NTAgXHVhYzFjXHVjNzU4IFx1YzVmMFx1YzE4ZFx1YjQxYyZuYnNwOyYjMzk7LSYjMzk7XHViMjk0IFx1YWMwMFx1Yjg1Y1x1Yjg1YyBcdWIxOTNcdWM3NzggXHVjMTMxXHViMGU1XHVhYzFjXHViZTQ0XHViOTdjLCBcdWI0NTAgXHVhYzFjXHVjNzU4IFx1YzVmMFx1YzE4ZFx1YjQxYyAmIzM5O3wmIzM5O1x1YjI5NCBcdWMxMzhcdWI4NWNcdWI4NWMgXHViMTkzXHVjNzc4IFx1YzEzMVx1YjBlNVx1YWMxY1x1YmU0NFx1Yjk3YyBcdWM3NThcdWJiZjhcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjYxMFx1ZDU1YywgJiMzOTsrJiMzOTsgXHVkNDVjXHVjMmRjXHViMjk0IFx1YzEzMVx1YjBlNVx1YWMxY1x1YmU0NCBcdWI0NTAgXHVhYzFjIFx1Yzc3NFx1YzBjMVx1Yzc1OCBcdWIwNWRcdWM4MTBcdWM3NzQgXHViOWNjXHViMGEwIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjNzA0XHVjZTU4XHViOTdjIFx1Yzc1OFx1YmJmOFx1ZDU1OFx1YmE3MCwgJiMzOTsuJiMzOTsgXHVjNzQwIFx1YmU0OCBcdWFjZjVcdWFjMDRcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc3NFx1YzgxYyBcdWM3MDRcdWM3NTggXHVhZGY4XHViOWFjXHViNGRjXHVjNWQwXHViMjk0IFx1Y2QxZCAxNFx1YWMxY1x1Yzc1OCBcdWM4MTVcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3NzQgXHVjNzg4XHViMmU0LiAoMSoxIFx1YzgxNVx1YzBhY1x1YWMwMVx1ZDYxNSA5XHVhYzFjLCAyKjIgXHVjODE1XHVjMGFjXHVhYzAxXHVkNjE1IDRcdWFjMWMsIDMqMyBcdWM4MTVcdWMwYWNcdWFjMDFcdWQ2MTUgMVx1YWMxYyk8XC9wPlxyXG5cclxuPHA+XHVjMTMxXHViMGU1XHVhYzFjXHViZTQ0XHViOTdjIFx1YjJlNCBcdWIxOTNcdWM3NDAgXHVjNzc0XHVkNmM0LCBcdWM4MDFcdWIyZjlcdWQ1NWMgXHVjODE1XHVjMjE4IE5cdWFjZmMgS1x1Yjk3YyBcdWFjZTBcdWI5NzhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc3NFx1YzgxYyBcdWM1NDRcdWI3OTggXHVjODcwXHVhYzc0XHVjNzQ0IFx1YjljY1x1Yzg3MVx1ZDU1OFx1YjNjNFx1Yjg1ZCBcdWFkZjhcdWI5YWNcdWI0ZGNcdWM1ZDBcdWMxMWMgXHVjMTMxXHViMGU1XHVhYzFjXHViZTQ0XHViOTdjIFx1YzgxY1x1YWM3MFx1ZDU1OFx1YmE3NCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+XHVhZGY4XHViOWFjXHViNGRjXHVjNWQwXHVjMTFjIFx1YzgxY1x1YWM3MFx1ZDU1OFx1YjI5NCBcdWMxMzFcdWIwZTVcdWFjMWNcdWJlNDRcdWM3NTggXHVhYzFjXHVjMjE4XHViMjk0IFx1YzgxNVx1ZDY1NVx1ZDc4OCBOXHVhYzFjXHVjNzc0XHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWIwYThcdWM3NDAgXHVhZGY4XHViOWFjXHViNGRjXHVjNWQwXHVjMTFjJm5ic3A7XHVjYzNlXHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjODE1XHVjMGFjXHVhYzAxXHVkNjE1XHVjNzU4IFx1YzIxOFx1YjI5NCBcdWM4MTVcdWQ2NTVcdWQ3ODggS1x1YWMxY1x1Yzc3NFx1YjJlNC48XC9saT5cclxuXHQ8bGk+XHViMGE4XHVjNTQ0IFx1Yzc4OFx1YjI5NCBcdWJhYThcdWI0ZTAgXHVjMTMxXHViMGU1XHVhYzFjXHViZTQ0XHViMjk0IFx1Y2Q1Y1x1YzE4Y1x1ZDU1YyBcdWQ1NThcdWIwOThcdWM3NTggXHVjODE1XHVjMGFjXHVhYzAxXHVkNjE1XHVjNzQ0IFx1Yzc3NFx1YjhlOFx1YjI5NCBcdWIzNzAgXHVjNGYwXHVjNWVjXHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5cdWM3YWNcdWQ2MDFcdWM3NzRcdWIyOTQgXHVjOWMwXHViMDljIDFcdWIxNDRcdWFjMDQgXHViOWU0XHVjNzdjIFx1YjNkOVx1YzU0NFx1YjlhY1x1YmMyOVx1YzVkMFx1YzExYyBcdWQ2M2NcdWM3OTAmbmJzcDtcdWMxMzFcdWIwZTVcdWFjMWNcdWJlNDQgXHVkMzdjXHVjOTkwXHVjNzQ0IFx1YWMwMFx1YzljMFx1YWNlMCBcdWIxODBcdWM1NThcdWM5YzBcdWI5Y2MmbmJzcDtcdWMxMzFcdWIwZTVcdWFjMWNcdWJlNDQgXHVkMzdjXHVjOTkwXHVjNWQwIFx1YzEzMVx1YWNmNVx1ZDU1YyZuYnNwO1x1YWNiZFx1YzZiMFx1YWMwMCBcdWM1YzZcdWM1YzhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzdhY1x1ZDYwMVx1Yzc3NFx1YjI5NCBcdWM3NzRcdWFjODNcdWM3NzQgXHVjNzkwXHVjMmUwXHVjNzU4IFx1YzJlNFx1YzIxOFx1YWMwMCBcdWM1NDRcdWIyYzhcdWI3N2MmbmJzcDtOXHVhY2ZjIEtcdWM3NTggXHVhYzEyXHVjNzQ0IFx1Yzc5OFx1YmFiYiBcdWFjZThcdWI3N2MgXHVkMzdjXHVjOTkwXHVjNzU4IFx1YzgxNVx1YjJmNVx1Yzc3NCBcdWM4NzRcdWM3YWNcdWQ1NThcdWM5YzAgXHVjNTRhXHViMjk0Jm5ic3A7XHVhYzgzXHVjNzc0IFx1YzZkMFx1Yzc3OFx1Yzc3NFx1Yjc3YyBcdWMwZGRcdWFjMDFcdWQ1ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjBhOFx1YWRkY1x1YjI5NCBcdWM3NzRcdWI3ZjAgXHVjN2FjXHVkNjAxXHVjNzc0XHVjNzU4IFx1ZDU1MVx1YWNjNFx1Yjk3YyBcdWFlNjhcdWJkODBcdWMyMThcdWFlMzAgXHVjNzA0XHVkNTc0LCBOXHVhY2ZjIEtcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWMwXHViYTc0IFx1ZDU3NFx1YjJmOSBcdWQzN2NcdWM5OTBcdWM3NTggXHVjODE1XHViMmY1XHVjNzQ0IFx1Y2MzZVx1YzU0NFx1YzhmY1x1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHViODI0IFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYiBcdWM5MDRcdWM1ZDAgXHVjODE1XHVjMjE4IE5cdWFjZmMgS1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxJm5ic3A7JmxlOyBOICZsdDsgMjQsIDEmbmJzcDsmbGU7IEsmbmJzcDsmbHQ7IDE0KTxcL3A+XHJcblxyXG48cD5OXHVjNzQwIFx1YzgxY1x1YWM3MFx1ZDU2MCBcdWMxMzFcdWIwZTVcdWFjMWNcdWJlNDRcdWM3NTggXHVjMjE4LCBLXHViMjk0IFx1YjBhOFx1YzU0NCBcdWM3ODhcdWM1YjRcdWM1N2MgXHVkNTYwIFx1YzgxNVx1YzBhY1x1YWMwMVx1ZDYxNVx1Yzc1OCBcdWMyMThcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHViYjM4XHVjODFjXHVjNzU4IFx1Yzg3MFx1YWM3NFx1Yzc0NCBcdWI5Y2NcdWM4NzFcdWQ1NThcdWIyOTQgXHVhZGY4XHViOWFjXHViNGRjXHViOTdjIFx1YzU0NFx1Yjc5OFx1YzY0MCBcdWFjMTlcdWM3NzQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48b2w+XHJcblx0PGxpPlx1YzEzMVx1YjBlNVx1YWMxY1x1YmU0NCBcdWI0NTAgXHVhYzFjXHVhYzAwIFx1YjljY1x1YjBhMCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YmFhOFx1YjRlMCBcdWM4MTAmbmJzcDs6Jm5ic3A7JiMzOTsrJiMzOTsgKFx1YzEzMVx1YjBlNVx1YWMxY1x1YmU0NFx1YWMwMCBcdWQ1NzRcdWIyZjkgXHVjNzA0XHVjZTU4XHVjNzU4IFx1YzBjMSxcdWQ1NTgsXHVjODhjLFx1YzZiMFx1YzVkMCZuYnNwO1x1YjE5M1x1Yzc3NFx1YzljMCBcdWM1NGFcdWM1NDRcdWIzYzQgJiMzOTsrJiMzOTtcdWI5N2MgXHVjZDljXHViODI1XHVkNTc0XHVjNTdjIFx1ZDU1Y1x1YjJlNCkuPFwvbGk+XHJcblx0PGxpPlx1YzEzMVx1YjBlNVx1YWMxY1x1YmU0NFx1YWMwMCBcdWIxOTNcdWM1ZWMgXHVjNzg4XHVjOWMwIFx1YzU0YVx1Yzc0MCBcdWJhYThcdWI0ZTAgXHVjODEwIDogJiMzOTsuJiMzOTs8XC9saT5cclxuXHQ8bGk+XHVhYzAwXHViODVjXHViODVjIFx1YjE5M1x1Yzc3OCBcdWMxMzFcdWIwZTVcdWFjMWNcdWJlNDQgOiZuYnNwO1x1YzVmMFx1YzE4ZFx1YjQxYyBcdWI0NTAgXHVhYzFjXHVjNzU4ICYjMzk7LSYjMzk7PFwvbGk+XHJcblx0PGxpPlx1YzEzOFx1Yjg1Y1x1Yjg1YyBcdWIxOTNcdWM3NzggXHVjMTMxXHViMGU1XHVhYzFjXHViZTQ0IDombmJzcDtcdWM1ZjBcdWMxOGRcdWI0MWMgXHViNDUwIFx1YWMxY1x1Yzc1OCAmIzM5O3wmIzM5OzxcL2xpPlxyXG48XC9vbD5cclxuXHJcbjxwPlx1ZDU2ZFx1YzBjMSBcdWM4MTVcdWIyZjVcdWM3NzQgXHVjODc0XHVjN2FjXHVkNTU4XHViMjk0IFx1Yzc4NVx1YjgyNVx1YjljYyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjljY1x1YzU3ZCBcdWJiMzhcdWM4MWNcdWM3NTggXHVjODcwXHVhYzc0XHVjNzQ0IFx1YjljY1x1Yzg3MVx1ZDU1OFx1YjI5NCBcdWFkZjhcdWI5YWNcdWI0ZGNcdWFjMDAgXHVjNWVjXHViN2VjIFx1YWMwMFx1YzljMFx1Yjc3Y1x1YmE3NCwgXHVjNzg0XHVjNzU4XHVjNzU4IFx1ZDU1OFx1YjA5OFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMzE2MCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6InNpYmljZSIsImRlc2NyaXB0aW9uIjoiPHA+MjQgbWF0Y2hlcyBhcmUgYXJyYW5nZWQgdG8gZm9ybSBhIDN4MyBncmlkIGFzIGlsbHVzdHJhdGVkIGluIHRoZSBmaWd1cmUgYmVsb3cuJm5ic3A7PFwvcD5cclxuXHJcbjxwcmU+XHJcbistLSstLSstLSsgXHJcbnwuLnwuLnwuLnwgXHJcbnwuLnwuLnwuLnwgXHJcbistLSstLSstLSsgXHJcbnwuLnwuLnwuLnwgXHJcbnwuLnwuLnwuLnwgXHJcbistLSstLSstLSsgXHJcbnwuLnwuLnwuLnwgXHJcbnwuLnwuLnwuLnwgXHJcbistLSstLSstLSsgXHJcbjxcL3ByZT5cclxuXHJcbjxwPlR3byBjb25zZWN1dGl2ZSAmIzM5Oy0mIzM5OyAobWludXMpIGNoYXJhY3RlcnMgcmVwcmVzZW50IGEgaG9yaXpvbnRhbCBtYXRjaCwgd2hlcmVhcyB0d28gY29uc2VjdXRpdmUgJiMzOTt8JiMzOTsgKHZlcnRpY2FsIGJhcikgY2hhcmFjdGVycyByZXByZXNlbnQgYSB2ZXJ0aWNhbCBtYXRjaC4gJiMzOTsrJiMzOTsgKHBsdXMpIGNoYXJhY3RlcnMgcmVwcmVzZW50IHBvc2l0aW9ucyB3aGVyZSB0d28gb3IgbW9yZSBtYXRjaGVzJiMzOTsgZW5kcyB0b3VjaC4gVGhlIGludGVyaW9yIG9mIHRoZSBib2FyZCBpcyBmaWxsZWQgd2l0aCAmIzM5Oy4mIzM5OyAoZG90KSBjaGFyYWN0ZXJzLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Xcml0ZSBhIHByb2dyYW0gdGhhdCwgZ2l2ZW4gaW50ZWdlcnMgTiBhbmQgSywgcmVtb3ZlcyBleGFjdGx5IE4gbWF0Y2hlcyBpbiBzdWNoIGEgd2F5IHRoYXQgdGhlIHJlbWFpbmluZyBtYXRjaGVzIGZvcm0gZXhhY3RseSBLIHNxdWFyZXMgYW5kIHRoYXQgZWFjaCByZW1haW5pbmcgbWF0Y2ggaXMgcGFydCBvZiBzb21lIHNxdWFyZS4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBhbmQgb25seSBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIHR3byBpbnRlZ2VycyBOIGFuZCBLLCAxICZsZTsgTiAmbHQ7IDI0LCAxICZsZTsgSyAmbHQ7IDE0LCB0aGUgbnVtYmVyIG9mIG1hdGNoZXMgdG8gYmUgcmVtb3ZlZCBhbmQgdGhlIG51bWJlciBvZiBzcXVhcmVzIHdhbnRlZC4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5PdXRwdXQgdGhlIHJlc3VsdGluZyBib2FyZCBpbiBhIGZvcm1hdCBpZGVudGljYWwgdG8gdGhlIGZpZ3VyZSBmcm9tIHRoZSB0YXNrIGRlc2NyaXB0aW9uLCB3aXRoIGRvdCBjaGFyYWN0ZXJzIGluIHBsYWNlIG9mIHRoZSByZW1vdmVkIG1hdGNoZXMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPk5vdGU6IHRoZSB0ZXN0IGRhdGEgd2lsbCBiZSBzdWNoIHRoYXQgYSBzb2x1dGlvbiwgYWx0aG91Z2ggbm90IG5lY2Vzc2FyaWx5IHVuaXF1ZSwgYWx3YXlzIGV4aXN0cy4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=