시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB21141372.222%

문제

다오와 디지니는 새로운 카트라이더 경주 트랙을 만들고 있다. 경주 트랙은 $H\times W$ 크기의 빈 직사각형 격자판에 $1\times 1$ 크기의 정사각형 타일을 놓는 방식으로 만들어진다. 타일은 길이 그려져 있는 방향에 따라 다음 6가지로 나뉘며, 각각의 타일은 회전해서 놓을 수 있다.

모든 격자칸을 타일로 채우면 경주 트랙이 완성된다. 한 격자판에 여러 개의 경주 트랙을 만들 수도 있기 때문에, 완성된 격자판에서 임의의 두 칸을 잇는 길이 존재하지 않아도 된다. 타일을 배치할 때는 길의 끝이 다른 길의 끝과 이어져 있도록 배치해야 한다. 즉, 길의 끝이 격자판 밖을 향하거나, 이웃한 타일의 길과 이어져 있지 않으면 안 된다.

다오와 디지니는 먼저 타일을 배치할 구역을 나누었다. 다오의 구역에는 다오만 타일을 놓을 수 있고, 디지니의 구역에는 디지니만 타일을 놓을 수 있다. 나머지 칸에는 둘 중 아무나 타일을 놓을 수 있다.

6가지 타일을 사용해서 격자판을 꾸미려는 디지니와 다르게, 다오는 구불구불한 경주 트랙을 좋아해서 ㄱ자 형태로 굽은 길 타일만 사용하기로 했다. 또, 다오는 욕심이 많아서 자기가 놓는 타일의 개수를 최대화하고 싶다. 다오는 자신만의 미적 감각에 따라 타일 몇 개를 먼저 배치했지만, 자기가 놓을 타일의 개수를 최대화하기 위해 나머지 칸을 어떻게 채워야 하는지는 알아낼 수 없었다. 다오가 놓을 수 있는 타일의 최대 개수를 계산해서 다오를 도와주자! (단, 다오가 먼저 배치한 타일도 세어야 한다.)

입력

첫 번째 줄에는 격자판의 세로를 나타내는 $H$와 가로를 나타내는 $W$가 주어진다. $(1 \leq H, W \leq 100)$

두 번째 줄부터 $H$개의 줄만큼 격자판의 정보가 주어진다. 각 줄은 $W$개의 문자로 이루어져 있으며, 각 문자가 나타내는 것은 다음과 같다.

  • 1 : 왼쪽 칸과 위 칸을 잇는 길 타일
  • 2 : 왼쪽 칸과 아래 칸을 잇는 길 타일
  • 3 : 오른쪽 칸과 위 칸을 잇는 길 타일
  • 4 : 오른쪽 칸과 아래 칸을 잇는 길 타일
  • o : 다오만 타일을 놓을 수 있는 칸
  • x : 디지니만 타일을 놓을 수 있는 칸
  • . : 둘 중 아무나 타일을 놓을 수 있는 칸

1234가 나타내는 타일은 다오가 놓은 타일이다.

출력

다오가 먼저 배치한 타일을 포함하여, 다오가 놓을 수 있는 타일의 최대 개수를 출력한다. 만약 조건을 만족하도록 격자판을 채울 수 없거나, 다오가 먼저 배치한 타일이 조건에 어긋나면 -1을 출력한다.

예제 입력 1

4 5
4...x
.2..2
.o1x.
3..3o

예제 출력 1

12

예제 1에 주어진 격자판은 다음과 같다. 파란색 칸은 다오의 구역, 노란색 칸은 디지니의 구역이다.

다음은 다오가 놓는 타일의 개수를 최대화하는 배치의 예시이다. 다오가 배치한 타일은 파란색, 디지니가 배치한 타일은 노란색으로 표시했다.

예제 입력 2

2 3
4o2
3x1

예제 출력 2

-1
W3sicHJvYmxlbV9pZCI6IjI0Mjc0IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVhZDZjXHViZDg4XHVhZDZjXHViZDg4IFx1YWNiZFx1YzhmYyBcdWQyYjhcdWI3OTkiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YjJlNFx1YzYyNFx1YzY0MCBcdWI1MTRcdWM5YzBcdWIyYzhcdWIyOTQgXHVjMGM4XHViODVjXHVjNmI0IFx1Y2U3NFx1ZDJiOFx1Yjc3Y1x1Yzc3NFx1YjM1NCBcdWFjYmRcdWM4ZmMgXHVkMmI4XHViNzk5XHVjNzQ0IFx1YjljY1x1YjRlNFx1YWNlMCBcdWM3ODhcdWIyZTQuIFx1YWNiZFx1YzhmYyBcdWQyYjhcdWI3OTlcdWM3NDAgJEhcXHRpbWVzIFckIFx1ZDA2Y1x1YWUzMFx1Yzc1OCBcdWJlNDggXHVjOWMxXHVjMGFjXHVhYzAxXHVkNjE1IFx1YWNhOVx1Yzc5MFx1ZDMxMFx1YzVkMCAkMVxcdGltZXMgMSQgXHVkMDZjXHVhZTMwXHVjNzU4IFx1YzgxNVx1YzBhY1x1YWMwMVx1ZDYxNSBcdWQwYzBcdWM3N2NcdWM3NDQgXHViMTkzXHViMjk0IFx1YmMyOVx1YzJkZFx1YzczY1x1Yjg1YyBcdWI5Y2NcdWI0ZTRcdWM1YjRcdWM5YzRcdWIyZTQuIFx1ZDBjMFx1Yzc3Y1x1Yzc0MCBcdWFlMzhcdWM3NzQgXHVhZGY4XHViODI0XHVjODM4IFx1Yzc4OFx1YjI5NCBcdWJjMjlcdWQ1YTVcdWM1ZDAgXHViNTMwXHViNzdjIFx1YjJlNFx1Yzc0YyA2XHVhYzAwXHVjOWMwXHViODVjIFx1YjA5OFx1YjI1OFx1YmE3MCwgXHVhYzAxXHVhYzAxXHVjNzU4IFx1ZDBjMFx1Yzc3Y1x1Yzc0MCBcdWQ2OGNcdWM4MDRcdWQ1NzRcdWMxMWMgXHViMTkzXHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPjxpbWcgYWx0PVwiXCIgc3JjPVwiaHR0cHM6XC9cL3VwbG9hZC5hY21pY3BjLm5ldFwvNWM3MGZhYWItMjVjZi00YzMwLTkzMzktYWU2M2FmODUzZDRhXC8tXC9wcmV2aWV3XC9cIiBzdHlsZT1cIndpZHRoOiA1NDBweDsgaGVpZ2h0OiA1ODJweDtcIiBcLz48XC9wPlxyXG5cclxuPHA+XHViYWE4XHViNGUwIFx1YWNhOVx1Yzc5MFx1Y2U3OFx1Yzc0NCBcdWQwYzBcdWM3N2NcdWI4NWMgXHVjYzQ0XHVjNmIwXHViYTc0IFx1YWNiZFx1YzhmYyBcdWQyYjhcdWI3OTlcdWM3NzQgXHVjNjQ0XHVjMTMxXHViNDFjXHViMmU0LiBcdWQ1NWMgXHVhY2E5XHVjNzkwXHVkMzEwXHVjNWQwIFx1YzVlY1x1YjdlYyBcdWFjMWNcdWM3NTggXHVhY2JkXHVjOGZjIFx1ZDJiOFx1Yjc5OVx1Yzc0NCBcdWI5Y2NcdWI0ZTQgXHVjMjE4XHViM2M0IFx1Yzc4OFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAsIFx1YzY0NFx1YzEzMVx1YjQxYyBcdWFjYTlcdWM3OTBcdWQzMTBcdWM1ZDBcdWMxMWMgXHVjNzg0XHVjNzU4XHVjNzU4IFx1YjQ1MCBcdWNlNzhcdWM3NDQgXHVjNzg3XHViMjk0IFx1YWUzOFx1Yzc3NCBcdWM4NzRcdWM3YWNcdWQ1NThcdWM5YzAgXHVjNTRhXHVjNTQ0XHViM2M0IFx1YjQxY1x1YjJlNC4gXHVkMGMwXHVjNzdjXHVjNzQ0IFx1YmMzMFx1Y2U1OFx1ZDU2MCBcdWI1NGNcdWIyOTQgXHVhZTM4XHVjNzU4IFx1YjA1ZFx1Yzc3NCBcdWIyZTRcdWI5NzggXHVhZTM4XHVjNzU4IFx1YjA1ZFx1YWNmYyBcdWM3NzRcdWM1YjRcdWM4MzggXHVjNzg4XHViM2M0XHViODVkIFx1YmMzMFx1Y2U1OFx1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1Yzk4OSwgXHVhZTM4XHVjNzU4IFx1YjA1ZFx1Yzc3NCBcdWFjYTlcdWM3OTBcdWQzMTAgXHViYzE2XHVjNzQ0IFx1ZDVhNVx1ZDU1OFx1YWM3MFx1YjA5OCwgXHVjNzc0XHVjNmMzXHVkNTVjIFx1ZDBjMFx1Yzc3Y1x1Yzc1OCBcdWFlMzhcdWFjZmMgXHVjNzc0XHVjNWI0XHVjODM4IFx1Yzc4OFx1YzljMCBcdWM1NGFcdWM3M2NcdWJhNzQgXHVjNTQ4IFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNjI0XHVjNjQwIFx1YjUxNFx1YzljMFx1YjJjOFx1YjI5NCBcdWJhM2NcdWM4MDAgXHVkMGMwXHVjNzdjXHVjNzQ0IFx1YmMzMFx1Y2U1OFx1ZDU2MCBcdWFkNmNcdWM1ZWRcdWM3NDQgXHViMDk4XHViMjA0XHVjNWM4XHViMmU0LiBcdWIyZTRcdWM2MjRcdWM3NTggXHVhZDZjXHVjNWVkXHVjNWQwXHViMjk0IFx1YjJlNFx1YzYyNFx1YjljYyBcdWQwYzBcdWM3N2NcdWM3NDQgXHViMTkzXHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWFjZTAsIFx1YjUxNFx1YzljMFx1YjJjOFx1Yzc1OCBcdWFkNmNcdWM1ZWRcdWM1ZDBcdWIyOTQgXHViNTE0XHVjOWMwXHViMmM4XHViOWNjIFx1ZDBjMFx1Yzc3Y1x1Yzc0NCBcdWIxOTNcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHViMDk4XHViYTM4XHVjOWMwIFx1Y2U3OFx1YzVkMFx1YjI5NCBcdWI0NTggXHVjOTExIFx1YzU0NFx1YmIzNFx1YjA5OCBcdWQwYzBcdWM3N2NcdWM3NDQgXHViMTkzXHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPjZcdWFjMDBcdWM5YzAgXHVkMGMwXHVjNzdjXHVjNzQ0IFx1YzBhY1x1YzZhOVx1ZDU3NFx1YzExYyBcdWFjYTlcdWM3OTBcdWQzMTBcdWM3NDQgXHVhZmI4XHViYmY4XHViODI0XHViMjk0IFx1YjUxNFx1YzljMFx1YjJjOFx1YzY0MCBcdWIyZTRcdWI5NzRcdWFjOGMsJm5ic3A7XHViMmU0XHVjNjI0XHViMjk0IFx1YWQ2Y1x1YmQ4OFx1YWQ2Y1x1YmQ4OFx1ZDU1YyBcdWFjYmRcdWM4ZmMgXHVkMmI4XHViNzk5XHVjNzQ0IFx1Yzg4Ylx1YzU0NFx1ZDU3NFx1YzExYyBcdTMxMzFcdWM3OTAgXHVkNjE1XHVkMGRjXHViODVjIFx1YWQ3ZFx1Yzc0MCBcdWFlMzggXHVkMGMwXHVjNzdjXHViOWNjIFx1YzBhY1x1YzZhOVx1ZDU1OFx1YWUzMFx1Yjg1YyBcdWQ1ODhcdWIyZTQuIFx1YjYxMCwgXHViMmU0XHVjNjI0XHViMjk0IFx1YzY5NVx1YzJlY1x1Yzc3NCBcdWI5Y2VcdWM1NDRcdWMxMWMgXHVjNzkwXHVhZTMwXHVhYzAwIFx1YjE5M1x1YjI5NCBcdWQwYzBcdWM3N2NcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1Y2Q1Y1x1YjMwMFx1ZDY1NFx1ZDU1OFx1YWNlMCBcdWMyZjZcdWIyZTQuIFx1YjJlNFx1YzYyNFx1YjI5NCBcdWM3OTBcdWMyZTBcdWI5Y2NcdWM3NTggXHViYmY4XHVjODAxIFx1YWMxMFx1YWMwMVx1YzVkMCBcdWI1MzBcdWI3N2MgXHVkMGMwXHVjNzdjIFx1YmE4NyBcdWFjMWNcdWI5N2MgXHViYTNjXHVjODAwIFx1YmMzMFx1Y2U1OFx1ZDU4OFx1YzljMFx1YjljYywgXHVjNzkwXHVhZTMwXHVhYzAwIFx1YjE5M1x1Yzc0NCBcdWQwYzBcdWM3N2NcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1Y2Q1Y1x1YjMwMFx1ZDY1NFx1ZDU1OFx1YWUzMCBcdWM3MDRcdWQ1NzQgXHViMDk4XHViYTM4XHVjOWMwIFx1Y2U3OFx1Yzc0NCBcdWM1YjRcdWI1YmJcdWFjOGMgXHVjYzQ0XHVjNmNjXHVjNTdjIFx1ZDU1OFx1YjI5NFx1YzljMFx1YjI5NCBcdWM1NGNcdWM1NDRcdWIwYmMgXHVjMjE4IFx1YzVjNlx1YzVjOFx1YjJlNC4gXHViMmU0XHVjNjI0XHVhYzAwIFx1YjE5M1x1Yzc0NCBcdWMyMTggXHVjNzg4XHViMjk0IFx1ZDBjMFx1Yzc3Y1x1Yzc1OCBcdWNkNWNcdWIzMDAgXHVhYzFjXHVjMjE4XHViOTdjIFx1YWNjNFx1YzBiMFx1ZDU3NFx1YzExYyBcdWIyZTRcdWM2MjRcdWI5N2MgXHViM2M0XHVjNjQwXHVjOGZjXHVjNzkwISZuYnNwOyhcdWIyZTgsIFx1YjJlNFx1YzYyNFx1YWMwMCBcdWJhM2NcdWM4MDAgXHViYzMwXHVjZTU4XHVkNTVjIFx1ZDBjMFx1Yzc3Y1x1YjNjNCBcdWMxMzhcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0Lik8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YWNhOVx1Yzc5MFx1ZDMxMFx1Yzc1OCBcdWMxMzhcdWI4NWNcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0ICRIJFx1YzY0MCBcdWFjMDBcdWI4NWNcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0ICRXJFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICQoMSBcXGxlcSBILCBXIFxcbGVxIDEwMCkkPFwvcD5cclxuXHJcbjxwPlx1YjQ1MCBcdWJjODhcdWM5ZjggXHVjOTA0XHViZDgwXHVkMTMwICRIJFx1YWMxY1x1Yzc1OCBcdWM5MDRcdWI5Y2NcdWQwN2MgXHVhY2E5XHVjNzkwXHVkMzEwXHVjNzU4IFx1YzgxNVx1YmNmNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMSBcdWM5MDRcdWM3NDAgJFckXHVhYzFjXHVjNzU4IFx1YmIzOFx1Yzc5MFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHVjNzNjXHViYTcwLCBcdWFjMDEgXHViYjM4XHVjNzkwXHVhYzAwIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCBcdWFjODNcdWM3NDAgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1YjJlNC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT48c3BhbiBzdHlsZT1cImNvbG9yOiNlNzRjM2M7XCI+PGNvZGU+MTxcL2NvZGU+PFwvc3Bhbj4gOiBcdWM2N2NcdWNhYmQgXHVjZTc4XHVhY2ZjIFx1YzcwNCBcdWNlNzhcdWM3NDQgXHVjNzg3XHViMjk0IFx1YWUzOCBcdWQwYzBcdWM3N2M8XC9saT5cclxuXHQ8bGk+PHNwYW4gc3R5bGU9XCJjb2xvcjojZTc0YzNjO1wiPjxjb2RlPjI8XC9jb2RlPjxcL3NwYW4+Jm5ic3A7OiBcdWM2N2NcdWNhYmQgXHVjZTc4XHVhY2ZjIFx1YzU0NFx1Yjc5OCBcdWNlNzhcdWM3NDQgXHVjNzg3XHViMjk0IFx1YWUzOCBcdWQwYzBcdWM3N2M8XC9saT5cclxuXHQ8bGk+PHNwYW4gc3R5bGU9XCJjb2xvcjojZTc0YzNjO1wiPjxjb2RlPjM8XC9jb2RlPjxcL3NwYW4+Jm5ic3A7OiBcdWM2MjRcdWI5NzhcdWNhYmQgXHVjZTc4XHVhY2ZjIFx1YzcwNCBcdWNlNzhcdWM3NDQgXHVjNzg3XHViMjk0IFx1YWUzOCBcdWQwYzBcdWM3N2M8XC9saT5cclxuXHQ8bGk+PHNwYW4gc3R5bGU9XCJjb2xvcjojZTc0YzNjO1wiPjxjb2RlPjQ8XC9jb2RlPjxcL3NwYW4+Jm5ic3A7OiBcdWM2MjRcdWI5NzhcdWNhYmQgXHVjZTc4XHVhY2ZjIFx1YzU0NFx1Yjc5OCBcdWNlNzhcdWM3NDQgXHVjNzg3XHViMjk0IFx1YWUzOCBcdWQwYzBcdWM3N2M8XC9saT5cclxuXHQ8bGk+PHNwYW4gc3R5bGU9XCJjb2xvcjojZTc0YzNjO1wiPjxjb2RlPm88XC9jb2RlPjxcL3NwYW4+Jm5ic3A7OiBcdWIyZTRcdWM2MjRcdWI5Y2MgXHVkMGMwXHVjNzdjXHVjNzQ0IFx1YjE5M1x1Yzc0NCBcdWMyMTggXHVjNzg4XHViMjk0IFx1Y2U3ODxcL2xpPlxyXG5cdDxsaT48c3BhbiBzdHlsZT1cImNvbG9yOiNlNzRjM2M7XCI+PGNvZGU+eDxcL2NvZGU+PFwvc3Bhbj4mbmJzcDs6IFx1YjUxNFx1YzljMFx1YjJjOFx1YjljYyBcdWQwYzBcdWM3N2NcdWM3NDQgXHViMTkzXHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjZTc4PFwvbGk+XHJcblx0PGxpPjxzcGFuIHN0eWxlPVwiY29sb3I6I2U3NGMzYztcIj48Y29kZT4uPFwvY29kZT48XC9zcGFuPiZuYnNwOzogXHViNDU4IFx1YzkxMSBcdWM1NDRcdWJiMzRcdWIwOTggXHVkMGMwXHVjNzdjXHVjNzQ0IFx1YjE5M1x1Yzc0NCBcdWMyMTggXHVjNzg4XHViMjk0IFx1Y2U3ODxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPjxzcGFuIHN0eWxlPVwiY29sb3I6I2U3NGMzYztcIj48Y29kZT4xPFwvY29kZT48XC9zcGFuPiwmbmJzcDs8c3BhbiBzdHlsZT1cImNvbG9yOiNlNzRjM2M7XCI+PGNvZGU+MjxcL2NvZGU+PFwvc3Bhbj4sJm5ic3A7PHNwYW4gc3R5bGU9XCJjb2xvcjojZTc0YzNjO1wiPjxjb2RlPjM8XC9jb2RlPjxcL3NwYW4+LCZuYnNwOzxzcGFuIHN0eWxlPVwiY29sb3I6I2U3NGMzYztcIj48Y29kZT40PFwvY29kZT48XC9zcGFuPlx1YWMwMCBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgXHVkMGMwXHVjNzdjXHVjNzQwIFx1YjJlNFx1YzYyNFx1YWMwMCBcdWIxOTNcdWM3NDAgXHVkMGMwXHVjNzdjXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj48aW1nIGFsdD1cIlwiIHNyYz1cImh0dHBzOlwvXC91cGxvYWQuYWNtaWNwYy5uZXRcL2UwNWQ2MWU1LTdkYjQtNGM2Yi05Mzc3LTk2NTU4NzYwZGVhMFwvLVwvcHJldmlld1wvXCIgc3R5bGU9XCJ3aWR0aDogNTQwcHg7IGhlaWdodDogMTcycHg7XCIgXC8+PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHViMmU0XHVjNjI0XHVhYzAwIFx1YmEzY1x1YzgwMCBcdWJjMzBcdWNlNThcdWQ1NWMgXHVkMGMwXHVjNzdjXHVjNzQ0IFx1ZDNlY1x1ZDU2OFx1ZDU1OFx1YzVlYywgXHViMmU0XHVjNjI0XHVhYzAwIFx1YjE5M1x1Yzc0NCBcdWMyMTggXHVjNzg4XHViMjk0IFx1ZDBjMFx1Yzc3Y1x1Yzc1OCBcdWNkNWNcdWIzMDAgXHVhYzFjXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHViOWNjXHVjNTdkIFx1Yzg3MFx1YWM3NFx1Yzc0NCBcdWI5Y2NcdWM4NzFcdWQ1NThcdWIzYzRcdWI4NWQgXHVhY2E5XHVjNzkwXHVkMzEwXHVjNzQ0IFx1Y2M0NFx1YzZiOCBcdWMyMTggXHVjNWM2XHVhYzcwXHViMDk4LCBcdWIyZTRcdWM2MjRcdWFjMDAgXHViYTNjXHVjODAwIFx1YmMzMFx1Y2U1OFx1ZDU1YyBcdWQwYzBcdWM3N2NcdWM3NzQgXHVjODcwXHVhYzc0XHVjNWQwIFx1YzViNFx1YWUwYlx1YjA5OFx1YmE3NCA8c3BhbiBzdHlsZT1cImNvbG9yOiNlNzRjM2M7XCI+PGNvZGU+LTE8XC9jb2RlPjxcL3NwYW4+XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4iLCJzYW1wbGVfZXhwbGFpbl8xIjoiPHA+XHVjNjA4XHVjODFjIDFcdWM1ZDAgXHVjOGZjXHVjNWI0XHVjOWM0IFx1YWNhOVx1Yzc5MFx1ZDMxMFx1Yzc0MCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHViMmU0LiBcdWQzMGNcdWI3ODBcdWMwYzkgXHVjZTc4XHVjNzQwIFx1YjJlNFx1YzYyNFx1Yzc1OCBcdWFkNmNcdWM1ZWQsIFx1YjE3OFx1Yjc4MFx1YzBjOSBcdWNlNzhcdWM3NDAgXHViNTE0XHVjOWMwXHViMmM4XHVjNzU4IFx1YWQ2Y1x1YzVlZFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJodHRwczpcL1wvdXBsb2FkLmFjbWljcGMubmV0XC8zODA2ZDc0OC0zMmE1LTRkNzItYmVkMi1kOWFkNWYxZTRiNGZcLy1cL3ByZXZpZXdcL1wiIHN0eWxlPVwid2lkdGg6IDU0MHB4OyBoZWlnaHQ6IDQzNHB4O1wiIFwvPjxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGNcdWM3NDAgXHViMmU0XHVjNjI0XHVhYzAwIFx1YjE5M1x1YjI5NCZuYnNwO1x1ZDBjMFx1Yzc3Y1x1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVjZDVjXHViMzAwXHVkNjU0XHVkNTU4XHViMjk0IFx1YmMzMFx1Y2U1OFx1Yzc1OCBcdWM2MDhcdWMyZGNcdWM3NzRcdWIyZTQuIFx1YjJlNFx1YzYyNFx1YWMwMCBcdWJjMzBcdWNlNThcdWQ1NWMgXHVkMGMwXHVjNzdjXHVjNzQwIFx1ZDMwY1x1Yjc4MFx1YzBjOSwgXHViNTE0XHVjOWMwXHViMmM4XHVhYzAwIFx1YmMzMFx1Y2U1OFx1ZDU1YyBcdWQwYzBcdWM3N2NcdWM3NDAgXHViMTc4XHViNzgwXHVjMGM5XHVjNzNjXHViODVjIFx1ZDQ1Y1x1YzJkY1x1ZDU4OFx1YjJlNC48XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJodHRwczpcL1wvdXBsb2FkLmFjbWljcGMubmV0XC9kNTg3ZDI0NC1jMzdiLTRlZjUtYjY3My05N2Y0NmE0ZmNkNDJcLy1cL3ByZXZpZXdcL1wiIHN0eWxlPVwid2lkdGg6IDU0MHB4OyBoZWlnaHQ6IDQzNHB4O1wiIFwvPjxcL3A+XHJcbiJ9LHsicHJvYmxlbV9pZCI6IjI0Mjc0IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQ3VybHkgUmFjZXRyYWNrIiwiZGVzY3JpcHRpb24iOiI8cD5Zb3UgYXJlIGNyZWF0aW5nIGEgbmV3IDxlbT5LYXJ0UmlkZXI8XC9lbT4mbmJzcDtyYWNldHJhY2suIFRoZSByYWNldHJhY2sgaXMgYSAkSCBcXHRpbWVzIFckIHJlY3Rhbmd1bGFyIGJvYXJkLiBFYWNoIGNlbGwgb2YgdGhlIGJvYXJkIGlzIGVpdGhlciBlbXB0eSwgb3IgY29udGFpbnMgYSB0aWxlIHdoaWNoIGlzIGRlc2NyaWJlZCBpbiB0aGUgcGljdHVyZSBiZWxvdy48XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJodHRwczpcL1wvdXBsb2FkLmFjbWljcGMubmV0XC81YzcwZmFhYi0yNWNmLTRjMzAtOTMzOS1hZTYzYWY4NTNkNGFcLy1cL3ByZXZpZXdcL1wiIHN0eWxlPVwid2lkdGg6IDU0MHB4OyBoZWlnaHQ6IDU4MnB4O1wiIFwvPjxcL3A+XHJcblxyXG48cD5Ob3RlIHRoYXQgZWFjaCBvZiB0aGUgdGlsZXMgY2FuIGJlIHJvdGF0ZWQsIGFuZCBhbGwgZXhjZXB0IG9uZSBoYXZlIHJvYWRzIGdvaW5nIG91dCBvZiB0aGUgdGlsZS4gV2UgZGVub3RlIHRoZSBmb3VydGggdHlwZSBvZiB0aWxlIChoaWdobGlnaHRlZCBpbiBibHVlIGNvbG9yKSBhcyBhIDxlbT5jdXJseTxcL2VtPiZuYnNwO3RpbGUuPFwvcD5cclxuXHJcbjxwPkluIGEgdmFsaWQgPGVtPkthcnRSaWRlcjxcL2VtPiZuYnNwO3JhY2V0cmFjaywgZXZlcnkgY2VsbCBzaG91bGQgY29udGFpbiBhIHRpbGUsIGFuZCB0aGVyZSBzaG91bGQgYmUgbm8gZGVhZC1lbmRzIG92ZXIgdGhlIHJvYWRzIGluIHRoZSB0aWxlLiBJbiBvdGhlciB3b3JkcywgZWFjaCByb2FkIGdvaW5nIG91dCBvZiB0aGUgdGlsZSBzaG91bGQgYmUgY29ubmVjdGVkIHRvIGEgcm9hZCBvbiB0aGUgbmVpZ2hib3JpbmcgdGlsZS4gQWxzbywgdGhlIHJvYWQgc2hvdWxkIG5vdCBmYWNlIG91dHNpZGUgdGhlIGJvYXJkLjxcL3A+XHJcblxyXG48cD5DdXJyZW50bHksIHRoZXJlIGFyZSBzb21lIGN1cmx5IHRpbGVzIGFscmVhZHkgcGxhY2VkIG9uIHRoZSBib2FyZC4gWW91IGNhbiBwbGFjZSB6ZXJvIG9yIG1vcmUgPHN0cm9uZz5jdXJseTxcL3N0cm9uZz4mbmJzcDt0aWxlcyBvbiB0aGUgYm9hcmQgYW5kIHN1Ym1pdCB0aGUgcmFjZXRyYWNrLiBUaGVuLCB0aGUgYWRtaW5pc3RyYXRvciB3aWxsIHRyeSB0byBmaWxsIGFsbCBlbXB0eSBjZWxscyB3aXRoIHRpbGVzIChub3QgbmVjZXNzYXJpbHkgY3VybHkpIHdpdGggdGhlaXIgYmVzdCBlZmZvcnQsIHNvIHRoYXQgaXQgYmVjb21lcyBhIHZhbGlkIDxlbT5LYXJ0UmlkZXI8XC9lbT4mbmJzcDtyYWNldHJhY2suIE5vdGUgdGhhdCB5b3UgY2FuIG9ubHkgcGxhY2UgdGhlIGN1cmx5IHRpbGVzLCBhbmQgeW91IHNob3VsZCBub3QgcmVtb3ZlLCByZXBsYWNlLCBvciByb3RhdGUgdGhlIGN1cmx5IHRpbGVzIGFscmVhZHkgcGxhY2VkIGluIHRoZSBib2FyZC48XC9wPlxyXG5cclxuPHA+QWRkaXRpb25hbGx5LCBmb3Igc29tZSBjZWxscywgeW91IGNhbiBub3QgcGxhY2UgdGhlIHRpbGVzLCBhbmQgZm9yIHNvbWUgY2VsbHMsIHlvdSBtdXN0IHBsYWNlIHRoZSBjdXJseSB0aWxlcy48XC9wPlxyXG5cclxuPHA+UGxlYXNlIGZpbmQgdGhlIG1heGltdW0gcG9zc2libGUgbnVtYmVyIG9mIGN1cmx5IHRpbGVzIHlvdSBjYW4gcGxhY2UgaW4gdGhlIHJhY2V0cmFjayBzbyB0aGF0IHRoZSBhZG1pbmlzdHJhdG9yIGNhbiBmaWxsIHRoZSByZW1haW5pbmcgY2VsbHMgdG8gY3JlYXRlIGEgdmFsaWQgPGVtPkthcnRSaWRlcjxcL2VtPiZuYnNwO3JhY2V0cmFjay4gWW91IHNob3VsZCByZXBvcnQgdGhlIHRvdGFsIG51bWJlciBvZiBjdXJseSB0aWxlcyBpbiB0aGUgcmFjZXRyYWNrLCBub3QgdGhlIG51bWJlciBvZiBjdXJseSB0aWxlcyB5b3UgaGF2ZSBuZXdseSBhZGRlZC4gSWYgdGhlcmUgaXMgbm8gd2F5IHRvIGNyZWF0ZSBhIHZhbGlkIDxlbT5LYXJ0UmlkZXI8XC9lbT4mbmJzcDtyYWNldHJhY2ssIHByaW50ICQtMSQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBjb250YWlucyB0d28gaW50ZWdlcnMgJEgkIGFuZCAkVyQgZGVub3RpbmcgdGhlIHNpemUgb2YgdGhlIGJvYXJkLiAoJDEgXFxsZSBILCBXIFxcbGUgMTAwJCk8XC9wPlxyXG5cclxuPHA+VGhlIG5leHQgJEgkIGxpbmVzIGNvbnRhaW4gdGhlIGluZm9ybWF0aW9uIGFib3V0IHRoZSBib2FyZC4gRWFjaCBsaW5lIGNvbnNpc3RzIG9mICRXJCBjaGFyYWN0ZXJzLCBkZW5vdGluZyB0aGUgZm9sbG93aW5nOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPiZxdW90Ozxjb2RlPjE8XC9jb2RlPiZxdW90OzogQ3VybHkgdGlsZSBjb250YWluaW5nIHJvYWQgY29ubmVjdGluZyB1cHBlciBhbmQgbGVmdCBjZWxscyw8XC9saT5cclxuXHQ8bGk+JnF1b3Q7PGNvZGU+MjxcL2NvZGU+JnF1b3Q7OiBDdXJseSB0aWxlIGNvbnRhaW5pbmcgcm9hZCBjb25uZWN0aW5nIGxvd2VyIGFuZCBsZWZ0IGNlbGxzLDxcL2xpPlxyXG5cdDxsaT4mcXVvdDs8Y29kZT4zPFwvY29kZT4mcXVvdDs6IEN1cmx5IHRpbGUgY29udGFpbmluZyByb2FkIGNvbm5lY3RpbmcgdXBwZXIgYW5kIHJpZ2h0IGNlbGxzLDxcL2xpPlxyXG5cdDxsaT4mcXVvdDs8Y29kZT40PFwvY29kZT4mcXVvdDs6IEN1cmx5IHRpbGUgY29udGFpbmluZyByb2FkIGNvbm5lY3RpbmcgbG93ZXIgYW5kIHJpZ2h0IGNlbGxzLDxcL2xpPlxyXG5cdDxsaT4mcXVvdDs8Y29kZT5vPFwvY29kZT4mcXVvdDs6IEVtcHR5IGNlbGwgd2hlcmUgY3VybHkgdGlsZSBtdXN0IGJlIHBsYWNlZCw8XC9saT5cclxuXHQ8bGk+JnF1b3Q7PGNvZGU+eDxcL2NvZGU+JnF1b3Q7OiBFbXB0eSBjZWxsIHdoZXJlIHlvdSBjYW4gbm90IHBsYWNlIHRoZSB0aWxlLDxcL2xpPlxyXG5cdDxsaT4mcXVvdDs8Y29kZT4uPFwvY29kZT4mcXVvdDs6IEVtcHR5IGNlbGwgd2hpY2ggaGFzIG5vIHJlc3RyaWN0aW9ucy48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj48aW1nIGFsdD1cIlwiIHNyYz1cImh0dHBzOlwvXC91cGxvYWQuYWNtaWNwYy5uZXRcL2UwNWQ2MWU1LTdkYjQtNGM2Yi05Mzc3LTk2NTU4NzYwZGVhMFwvLVwvcHJldmlld1wvXCIgc3R5bGU9XCJ3aWR0aDogNTQwcHg7IGhlaWdodDogMTcycHg7XCIgXC8+PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+T3V0cHV0IHRoZSBtYXhpbXVtIHBvc3NpYmxlIG51bWJlciBvZiBjdXJseSB0aWxlcyB5b3UgY2FuIHBsYWNlIG9uIHRoZSByYWNldHJhY2sgc28gdGhhdCB0aGUgYWRtaW5pc3RyYXRvciBjYW4gZmlsbCB0aGUgcmVtYWluaW5nIGNlbGxzIHRvIGNyZWF0ZSBhIHZhbGlkIDxlbT5LYXJ0UmlkZXI8XC9lbT4mbmJzcDtyYWNldHJhY2suIFlvdSBzaG91bGQgcmVwb3J0IHRoZSB0b3RhbCBudW1iZXIgb2YgY3VybHkgdGlsZXMgb24gdGhlIHJhY2V0cmFjaywgbm90IHRoZSBudW1iZXIgb2YgY3VybHkgdGlsZXMgeW91IGhhdmUgbmV3bHkgYWRkZWQuIElmIHRoZXJlIGlzIG5vIHdheSB0byBjcmVhdGUgYSB2YWxpZCA8ZW0+S2FydFJpZGVyPFwvZW0+Jm5ic3A7cmFjZXRyYWNrLCBwcmludCAkLTEkLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2giLCJzYW1wbGVfZXhwbGFpbl8xIjoiPHA+VGhlIGZvbGxvd2luZyBpbWFnZSBpbGx1c3RyYXRlcyB0aGUgb3JpZ2luYWwgc3RhdGUgb2YgdGhlIGJvYXJkIGluIHRoZSBmaXJzdCBzYW1wbGUgaW5wdXQuPFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPjxpbWcgYWx0PVwiXCIgc3JjPVwiaHR0cHM6XC9cL3VwbG9hZC5hY21pY3BjLm5ldFwvMzgwNmQ3NDgtMzJhNS00ZDcyLWJlZDItZDlhZDVmMWU0YjRmXC8tXC9wcmV2aWV3XC9cIiBzdHlsZT1cIndpZHRoOiA1NDBweDsgaGVpZ2h0OiA0MzRweDtcIiBcLz48XC9wPlxyXG5cclxuPHA+VGhlIGZvbGxvd2luZyBpbWFnZSBpbGx1c3RyYXRlcyB0aGUgZmluYWwgc3RhdGUgb2YgdGhlIGJvYXJkIGluIHRoZSBvcHRpbWFsIHNvbHV0aW9uLiBUaWxlcyBwbGFjZWQgYnkgdGhlIGFkbWluaXN0cmF0b3JzIGFyZSBoaWdobGlnaHRlZCBpbiB5ZWxsb3cuPFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPjxpbWcgYWx0PVwiXCIgc3JjPVwiaHR0cHM6XC9cL3VwbG9hZC5hY21pY3BjLm5ldFwvZDU4N2QyNDQtYzM3Yi00ZWY1LWI2NzMtOTdmNDZhNGZjZDQyXC8tXC9wcmV2aWV3XC9cIiBzdHlsZT1cIndpZHRoOiA1NDBweDsgaGVpZ2h0OiA0MzRweDtcIiBcLz48XC9wPlxyXG4ifV0=

출처

Contest > Good Bye, BOJ > Hello, BOJ 2022! G번

Camp > Petrozavodsk Programming Camp > Winter 2022 > Day 2: Grand Prix of Daejeon L번