행 열의 격자 가 주어진다. 각 칸에는 또는 이 적혀 있다.
에서 으로 가는 최단 경로는 매 이동마다 오른쪽 또는 아래쪽으로 한 칸 이동한다. 경로가 방문하는 칸의 문자를 시작 칸부터 도착 칸까지 순서대로 읽어 길이 의 이진 문자열을 만든다.
서로 다른 두 최단 경로가 같은 이진 문자열을 만들 수 있으면 이 격자를 멋있는 격자라고 한다. 그렇지 않으면, 즉 모든 최단 경로가 서로 다른 이진 문자열을 만들면 이 격자는 멋있는 격자가 아니다.
서로 다른 정확히 개의 칸을 골라 각 칸의 값을 한 번씩 반전시키려고 한다. 은 로, 은 으로 바뀐다.
정확히 개의 칸을 반전시킨 뒤 멋있는 격자가 아닌 격자를 하나 만들어 출력하여라. 그런 격자를 만들 수 없다면 불가능함을 출력하여라.
입력은 다음과 같은 형식으로 주어진다.
각 테스트 케이스마다 답을 출력한다.
조건을 만족하는 격자를 만들 수 없다면 한 줄에 -1을 출력한다.
만들 수 있다면 개의 줄에 길이 의 이진 문자열을 출력한다. 출력한 격자는 원래 격자와 정확히 개의 칸에서 달라야 하며, 멋있는 격자가 아니어야 한다.
가능한 답이 여러 가지라면 아무거나 출력해도 된다.
두 번째 테스트 케이스에서는 의 값을 반전시키면 정확히 한 칸이 바뀐다. 세 번째 테스트 케이스는 최단 경로가 하나뿐이므로 출력한 격자도 조건을 만족한다.
각 케이스는 다음과 같은 형식으로 주어진다.
는 길이 의 이진 문자열이며, 번째 문자는 칸의 값을 나타낸다.
| 3 | 18 |
|
| 4 | 15 | . |
| 5 | 45 | 추가적인 제약이 없다. |
