세워야 하는 핀

마리오는 컴퓨터 게임 개발자 협회의 특별 발표를 위해, 연도별·장르별로 출시된 게임 타이틀 수를 나타내는 2차원 히스토그램을 만들었다. 스프레드시트로 보니 꽤 보기 좋았다.

마리오는 실물 모형이 더 낫겠다고 생각해 철사와 판지로 하나를 만들었다(아래 왼쪽 그림). 학회로 옮기려고 포장하자 아래 오른쪽 그림처럼 되었다. 각 철사는 밑동을 원래의 칸에 둔 채로, 무작위로 왼쪽이나 오른쪽으로 눕혀졌다.

모형을 다시 꺼내 세우려 할 때에야 문제가 있음을 깨달았다. 각 철사를 왼쪽으로 눕혔는지 오른쪽으로 눕혔는지 기록해 두지 않았던 것이다. 게다가 조수가 포장 지침을 제대로 따르지 않아, 모든 철사가 좌우로만 눕혀진 것이 아니라 일부는 판지 위에서 앞이나 뒤로 눕혀져 있었다. 원래 데이터는 남아 있지 않다. 철사들을 어떻게 다시 세울지 알아내는 프로그램을 작성하고, 같은 일이 또 생길 때를 대비해 일반적으로 동작하도록 만들어야 한다.

해가 있는 입력도 있다. 예를 들어 오른쪽 그림에는 길이가 각각 1, 1, 3, 2인 핀 네 개가 있다. 이들은 길이 1인 두 핀을 1열에, 길이 2와 길이 3인 핀을 2열(각각 1행과 2행)에 두는 방법으로만 세울 수 있다.

해가 유일하지 않은 입력도 있다. 예를 들어 두 번째 그림을 보자. 세 핀은 길이 2인 핀을 오른쪽에 두든 왼쪽에 두든 세울 수 있다. 이처럼 여러 배치가 가능하면 어느 것이 맞는지 알 수 없으므로 해가 없다고 보고해야 한다. 다만 길이 2인 핀이 길이 1이었다면 문제가 되지 않았을 것이다. 각 핀이 원래 어느 칸에 있었는지는 확신할 수 없어도, 모든 칸이 높이 1인 핀으로 시작했다는 것은 확실하기 때문이다. 그런 경우는 괜찮다.

입력은 여러 개의 문제로 이루어진다. 각 문제는 격자의 행 수와 열 수를 나타내는 두 정수 $R$, $C$가 담긴 줄로 시작한다($1 \le R, C \le 100$). 그 뒤로 철사마다 한 줄씩 $R \times C$개의 줄이 이어진다. 각 줄에는 철사 한 개의 두 끝점의 격자 좌표가 네 정수 $r_1; c_1; r_2; c_2$로 주어진다. 한 끝점은 원래의 격자 칸(밑동)에 있고, 다른 끝점은 철사가 가로 또는 세로로 눕혀진 결과 그 길이만큼 떨어진 곳에 있다. 이 다른 끝점의 좌표는 격자 밖일 수도 있다. 철사는 곧게 뻗어 있으므로 두 끝점 사이의 거리가 곧 그 길이이며, 모든 길이는 $1$ 이상 $9$ 이하의 정수이다. 입력은 두 개의 0이 담긴 줄로 끝나며, 이 줄은 처리하지 않는다.

연달아 나오는 문제의 답 사이에는 빈 줄 하나를 넣어 구분한다(첫 번째 답 앞에는 빈 줄이 없다). 어떤 문제의 높이가 유일하게 결정되지 않으면 — 유효한 배치가 없거나, 서로 다른 높이를 주는 유효한 배치가 둘 이상이면 — No solution을 출력한다. 그렇지 않으면 $R$개의 줄을 출력하며, $i$번째 줄에는 $i$행에 세워진 철사들의 높이 $C$개를 한 자리 숫자로, 사이에 공백 없이 이어 붙여 출력한다.