시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 8 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+XHJcblxyXG48cD5cdWJhM2NcdWM4MDAsIDI0XHVhYzFjXHVjNzU4IFx1YzEzMVx1YjBlNVx1YWMxY1x1YmU0NFx1Yjk3YyBcdWM1NDRcdWI3OTggXHVhZGY4XHViOWJjXHVjYzk4XHViN2ZjIFx1YjE5M1x1YjI5NFx1YjJlNC48XC9wPlxyXG5cclxuPHByZT5cclxuKy0tKy0tKy0tK1xyXG58Li58Li58Li58XHJcbnwuLnwuLnwuLnxcclxuKy0tKy0tKy0tK1xyXG58Li58Li58Li58XHJcbnwuLnwuLnwuLnxcclxuKy0tKy0tKy0tK1xyXG58Li58Li58Li58XHJcbnwuLnwuLnwuLnxcclxuKy0tKy0tKy0tKzxcL3ByZT5cclxuXHJcbjxwPlx1YjQ1MCBcdWFjMWNcdWM3NTggXHVjNWYwXHVjMThkXHViNDFjJm5ic3A7JiMzOTstJiMzOTtcdWIyOTQgXHVhYzAwXHViODVjXHViODVjIFx1YjE5M1x1Yzc3OCBcdWMxMzFcdWIwZTVcdWFjMWNcdWJlNDRcdWI5N2MsIFx1YjQ1MCBcdWFjMWNcdWM3NTggXHVjNWYwXHVjMThkXHViNDFjICYjMzk7fCYjMzk7XHViMjk0IFx1YzEzOFx1Yjg1Y1x1Yjg1YyBcdWIxOTNcdWM3NzggXHVjMTMxXHViMGU1XHVhYzFjXHViZTQ0XHViOTdjIFx1Yzc1OFx1YmJmOFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViNjEwXHVkNTVjLCAmIzM5OysmIzM5OyBcdWQ0NWNcdWMyZGNcdWIyOTQgXHVjMTMxXHViMGU1XHVhYzFjXHViZTQ0IFx1YjQ1MCBcdWFjMWMgXHVjNzc0XHVjMGMxXHVjNzU4IFx1YjA1ZFx1YzgxMFx1Yzc3NCBcdWI5Y2NcdWIwYTAgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWM3MDRcdWNlNThcdWI5N2MgXHVjNzU4XHViYmY4XHVkNTU4XHViYTcwLCAmIzM5Oy4mIzM5OyBcdWM3NDAgXHViZTQ4IFx1YWNmNVx1YWMwNFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzc0XHVjODFjIFx1YzcwNFx1Yzc1OCBcdWFkZjhcdWI5YWNcdWI0ZGNcdWM1ZDBcdWIyOTQgXHVjZDFkIDE0XHVhYzFjXHVjNzU4IFx1YzgxNVx1YzBhY1x1YWMwMVx1ZDYxNVx1Yzc3NCBcdWM3ODhcdWIyZTQuICgxKjEgXHVjODE1XHVjMGFjXHVhYzAxXHVkNjE1IDlcdWFjMWMsIDIqMiBcdWM4MTVcdWMwYWNcdWFjMDFcdWQ2MTUgNFx1YWMxYywgMyozIFx1YzgxNVx1YzBhY1x1YWMwMVx1ZDYxNSAxXHVhYzFjKTxcL3A+XHJcblxyXG48cD5cdWMxMzFcdWIwZTVcdWFjMWNcdWJlNDRcdWI5N2MgXHViMmU0IFx1YjE5M1x1Yzc0MCBcdWM3NzRcdWQ2YzQsIFx1YzgwMVx1YjJmOVx1ZDU1YyBcdWM4MTVcdWMyMTggTlx1YWNmYyBLXHViOTdjIFx1YWNlMFx1Yjk3OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzc0XHVjODFjIFx1YzU0NFx1Yjc5OCBcdWM4NzBcdWFjNzRcdWM3NDQgXHViOWNjXHVjODcxXHVkNTU4XHViM2M0XHViODVkIFx1YWRmOFx1YjlhY1x1YjRkY1x1YzVkMFx1YzExYyBcdWMxMzFcdWIwZTVcdWFjMWNcdWJlNDRcdWI5N2MgXHVjODFjXHVhYzcwXHVkNTU4XHViYTc0IFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5cdWFkZjhcdWI5YWNcdWI0ZGNcdWM1ZDBcdWMxMWMgXHVjODFjXHVhYzcwXHVkNTU4XHViMjk0IFx1YzEzMVx1YjBlNVx1YWMxY1x1YmU0NFx1Yzc1OCBcdWFjMWNcdWMyMThcdWIyOTQgXHVjODE1XHVkNjU1XHVkNzg4IE5cdWFjMWNcdWM3NzRcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YjBhOFx1Yzc0MCBcdWFkZjhcdWI5YWNcdWI0ZGNcdWM1ZDBcdWMxMWMmbmJzcDtcdWNjM2VcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWM4MTVcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3NTggXHVjMjE4XHViMjk0IFx1YzgxNVx1ZDY1NVx1ZDc4OCBLXHVhYzFjXHVjNzc0XHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWIwYThcdWM1NDQgXHVjNzg4XHViMjk0IFx1YmFhOFx1YjRlMCBcdWMxMzFcdWIwZTVcdWFjMWNcdWJlNDRcdWIyOTQgXHVjZDVjXHVjMThjXHVkNTVjIFx1ZDU1OFx1YjA5OFx1Yzc1OCBcdWM4MTVcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3NDQgXHVjNzc0XHViOGU4XHViMjk0IFx1YjM3MCBcdWM0ZjBcdWM1ZWNcdWM1N2MgXHVkNTVjXHViMmU0LjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlx1YzdhY1x1ZDYwMVx1Yzc3NFx1YjI5NCBcdWM5YzBcdWIwOWMgMVx1YjE0NFx1YWMwNCBcdWI5ZTRcdWM3N2MgXHViM2Q5XHVjNTQ0XHViOWFjXHViYzI5XHVjNWQwXHVjMTFjIFx1ZDYzY1x1Yzc5MCZuYnNwO1x1YzEzMVx1YjBlNVx1YWMxY1x1YmU0NCBcdWQzN2NcdWM5OTBcdWM3NDQgXHVhYzAwXHVjOWMwXHVhY2UwIFx1YjE4MFx1YzU1OFx1YzljMFx1YjljYyZuYnNwO1x1YzEzMVx1YjBlNVx1YWMxY1x1YmU0NCBcdWQzN2NcdWM5OTBcdWM1ZDAgXHVjMTMxXHVhY2Y1XHVkNTVjJm5ic3A7XHVhY2JkXHVjNmIwXHVhYzAwIFx1YzVjNlx1YzVjOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjN2FjXHVkNjAxXHVjNzc0XHViMjk0IFx1Yzc3NFx1YWM4M1x1Yzc3NCBcdWM3OTBcdWMyZTBcdWM3NTggXHVjMmU0XHVjMjE4XHVhYzAwIFx1YzU0NFx1YjJjOFx1Yjc3YyZuYnNwO05cdWFjZmMgS1x1Yzc1OCBcdWFjMTJcdWM3NDQgXHVjNzk4XHViYWJiIFx1YWNlOFx1Yjc3YyBcdWQzN2NcdWM5OTBcdWM3NTggXHVjODE1XHViMmY1XHVjNzc0IFx1Yzg3NFx1YzdhY1x1ZDU1OFx1YzljMCBcdWM1NGFcdWIyOTQmbmJzcDtcdWFjODNcdWM3NzQgXHVjNmQwXHVjNzc4XHVjNzc0XHViNzdjIFx1YzBkZFx1YWMwMVx1ZDU4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViMGE4XHVhZGRjXHViMjk0IFx1Yzc3NFx1YjdmMCBcdWM3YWNcdWQ2MDFcdWM3NzRcdWM3NTggXHVkNTUxXHVhY2M0XHViOTdjIFx1YWU2OFx1YmQ4MFx1YzIxOFx1YWUzMCBcdWM3MDRcdWQ1NzQsIE5cdWFjZmMgS1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWJhNzQgXHVkNTc0XHViMmY5IFx1ZDM3Y1x1Yzk5MFx1Yzc1OCBcdWM4MTVcdWIyZjVcdWM3NDQgXHVjYzNlXHVjNTQ0XHVjOGZjXHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWI4MjQgXHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiIFx1YzkwNFx1YzVkMCBcdWM4MTVcdWMyMTggTlx1YWNmYyBLXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEmbmJzcDsmbGU7IE4gJmx0OyAyNCwgMSZuYnNwOyZsZTsgSyZuYnNwOyZsdDsgMTQpPFwvcD5cclxuXHJcbjxwPk5cdWM3NDAgXHVjODFjXHVhYzcwXHVkNTYwIFx1YzEzMVx1YjBlNVx1YWMxY1x1YmU0NFx1Yzc1OCBcdWMyMTgsIEtcdWIyOTQgXHViMGE4XHVjNTQ0IFx1Yzc4OFx1YzViNFx1YzU3YyBcdWQ1NjAgXHVjODE1XHVjMGFjXHVhYzAxXHVkNjE1XHVjNzU4IFx1YzIxOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWJiMzhcdWM4MWNcdWM3NTggXHVjODcwXHVhYzc0XHVjNzQ0IFx1YjljY1x1Yzg3MVx1ZDU1OFx1YjI5NCBcdWFkZjhcdWI5YWNcdWI0ZGNcdWI5N2MgXHVjNTQ0XHViNzk4XHVjNjQwIFx1YWMxOVx1Yzc3NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxvbD5cclxuXHQ8bGk+XHVjMTMxXHViMGU1XHVhYzFjXHViZTQ0IFx1YjQ1MCBcdWFjMWNcdWFjMDAgXHViOWNjXHViMGEwIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHViYWE4XHViNGUwIFx1YzgxMCZuYnNwOzombmJzcDsmIzM5OysmIzM5OyAoXHVjMTMxXHViMGU1XHVhYzFjXHViZTQ0XHVhYzAwIFx1ZDU3NFx1YjJmOSBcdWM3MDRcdWNlNThcdWM3NTggXHVjMGMxLFx1ZDU1OCxcdWM4OGMsXHVjNmIwXHVjNWQwJm5ic3A7XHViMTkzXHVjNzc0XHVjOWMwIFx1YzU0YVx1YzU0NFx1YjNjNCAmIzM5OysmIzM5O1x1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0KS48XC9saT5cclxuXHQ8bGk+XHVjMTMxXHViMGU1XHVhYzFjXHViZTQ0XHVhYzAwIFx1YjE5M1x1YzVlYyBcdWM3ODhcdWM5YzAgXHVjNTRhXHVjNzQwIFx1YmFhOFx1YjRlMCBcdWM4MTAgOiAmIzM5Oy4mIzM5OzxcL2xpPlxyXG5cdDxsaT5cdWFjMDBcdWI4NWNcdWI4NWMgXHViMTkzXHVjNzc4IFx1YzEzMVx1YjBlNVx1YWMxY1x1YmU0NCA6Jm5ic3A7XHVjNWYwXHVjMThkXHViNDFjIFx1YjQ1MCBcdWFjMWNcdWM3NTggJiMzOTstJiMzOTs8XC9saT5cclxuXHQ8bGk+XHVjMTM4XHViODVjXHViODVjIFx1YjE5M1x1Yzc3OCBcdWMxMzFcdWIwZTVcdWFjMWNcdWJlNDQgOiZuYnNwO1x1YzVmMFx1YzE4ZFx1YjQxYyBcdWI0NTAgXHVhYzFjXHVjNzU4ICYjMzk7fCYjMzk7PFwvbGk+XHJcbjxcL29sPlxyXG5cclxuPHA+XHVkNTZkXHVjMGMxIFx1YzgxNVx1YjJmNVx1Yzc3NCBcdWM4NzRcdWM3YWNcdWQ1NThcdWIyOTQgXHVjNzg1XHViODI1XHViOWNjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViOWNjXHVjNTdkIFx1YmIzOFx1YzgxY1x1Yzc1OCBcdWM4NzBcdWFjNzRcdWM3NDQgXHViOWNjXHVjODcxXHVkNTU4XHViMjk0IFx1YWRmOFx1YjlhY1x1YjRkY1x1YWMwMCBcdWM1ZWNcdWI3ZWMgXHVhYzAwXHVjOWMwXHViNzdjXHViYTc0LCBcdWM3ODRcdWM3NThcdWM3NTggXHVkNTU4XHViMDk4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIzMTYwIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoic2liaWNlIiwiZGVzY3JpcHRpb24iOiI8cD4yNCBtYXRjaGVzIGFyZSBhcnJhbmdlZCB0byBmb3JtIGEgM3gzIGdyaWQgYXMgaWxsdXN0cmF0ZWQgaW4gdGhlIGZpZ3VyZSBiZWxvdy4mbmJzcDs8XC9wPlxyXG5cclxuPHByZT5cclxuKy0tKy0tKy0tKyBcclxufC4ufC4ufC4ufCBcclxufC4ufC4ufC4ufCBcclxuKy0tKy0tKy0tKyBcclxufC4ufC4ufC4ufCBcclxufC4ufC4ufC4ufCBcclxuKy0tKy0tKy0tKyBcclxufC4ufC4ufC4ufCBcclxufC4ufC4ufC4ufCBcclxuKy0tKy0tKy0tKyBcclxuPFwvcHJlPlxyXG5cclxuPHA+VHdvIGNvbnNlY3V0aXZlICYjMzk7LSYjMzk7IChtaW51cykgY2hhcmFjdGVycyByZXByZXNlbnQgYSBob3Jpem9udGFsIG1hdGNoLCB3aGVyZWFzIHR3byBjb25zZWN1dGl2ZSAmIzM5O3wmIzM5OyAodmVydGljYWwgYmFyKSBjaGFyYWN0ZXJzIHJlcHJlc2VudCBhIHZlcnRpY2FsIG1hdGNoLiAmIzM5OysmIzM5OyAocGx1cykgY2hhcmFjdGVycyByZXByZXNlbnQgcG9zaXRpb25zIHdoZXJlIHR3byBvciBtb3JlIG1hdGNoZXMmIzM5OyBlbmRzIHRvdWNoLiBUaGUgaW50ZXJpb3Igb2YgdGhlIGJvYXJkIGlzIGZpbGxlZCB3aXRoICYjMzk7LiYjMzk7IChkb3QpIGNoYXJhY3RlcnMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPldyaXRlIGEgcHJvZ3JhbSB0aGF0LCBnaXZlbiBpbnRlZ2VycyBOIGFuZCBLLCByZW1vdmVzIGV4YWN0bHkgTiBtYXRjaGVzIGluIHN1Y2ggYSB3YXkgdGhhdCB0aGUgcmVtYWluaW5nIG1hdGNoZXMgZm9ybSBleGFjdGx5IEsgc3F1YXJlcyBhbmQgdGhhdCBlYWNoIHJlbWFpbmluZyBtYXRjaCBpcyBwYXJ0IG9mIHNvbWUgc3F1YXJlLiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGFuZCBvbmx5IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgdHdvIGludGVnZXJzIE4gYW5kIEssIDEgJmxlOyBOICZsdDsgMjQsIDEgJmxlOyBLICZsdDsgMTQsIHRoZSBudW1iZXIgb2YgbWF0Y2hlcyB0byBiZSByZW1vdmVkIGFuZCB0aGUgbnVtYmVyIG9mIHNxdWFyZXMgd2FudGVkLiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPk91dHB1dCB0aGUgcmVzdWx0aW5nIGJvYXJkIGluIGEgZm9ybWF0IGlkZW50aWNhbCB0byB0aGUgZmlndXJlIGZyb20gdGhlIHRhc2sgZGVzY3JpcHRpb24sIHdpdGggZG90IGNoYXJhY3RlcnMgaW4gcGxhY2Ugb2YgdGhlIHJlbW92ZWQgbWF0Y2hlcy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+Tm90ZTogdGhlIHRlc3QgZGF0YSB3aWxsIGJlIHN1Y2ggdGhhdCBhIHNvbHV0aW9uLCBhbHRob3VnaCBub3QgbmVjZXNzYXJpbHkgdW5pcXVlLCBhbHdheXMgZXhpc3RzLiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=