크로스넘버

신문에 실린 CrossNumber(크로스넘버) 퍼즐을 친구가 손으로 푸는 것보다 빠르게 풀 수 있는 프로그램을 짤 수 있다고 친구와 내기를 했습니다.

이 퍼즐은 크로스워드와 비슷하지만, 각 칸에 글자 대신 $0$부터 $9$까지의 숫자가 들어갑니다. 각 단서(clue)는 대응하는 '단어'에 들어간 숫자들의 합을 알려 줍니다. 독자를 곤란하게 만들지 않도록, 이 퍼즐은 푸는 과정 내내 항상 '아직 채워지지 않은 칸이 정확히 하나 남은 단어'가 존재하도록 만들어져 있습니다.

입력은 여러 개의 테스트 케이스로 이루어집니다. 각 테스트 케이스는 정사각형 퍼즐의 행과 열의 수를 나타내는 정수 $N$ ($2 \le N \le 100$)이 한 줄에 주어지는 것으로 시작합니다.

각 테스트 케이스는 다음과 같이 구성됩니다.

• 퍼즐 격자를 나타내는, 각각 $N$개의 문자로 이루어진 $N$개의 행. 문자 .은 아직 채워지지 않은 칸, 문자 #은 검은 칸을 뜻하며, 숫자 0부터 9까지는 그 칸에 이미 배정된 값을 뜻합니다.
• Across라고 적힌 한 줄.
• 이어서 각 가로 단서마다 한 줄씩, 세 정수 x y sum이 주어집니다. x와 y는 각각 열과 행 번호이며 $1 \le x, y \le N$입니다. sum은 해당 가로(또는 세로) 단어에 들어간 숫자들의 합입니다.
• Down이라고 적힌 한 줄.
• 이어서 각 세로 단서마다 한 줄씩, 가로 단서와 같은 형식으로 주어집니다.

검은 칸이 아닌 칸들이 가로 또는 세로로 이어진 극대 구간 중 길이가 $2$ 이상인 것은, 그 구간의 가장 왼쪽 위 칸에 정확히 하나의 단서가 대응됩니다. 이는 그 구간의 모든 칸이 이미 힌트로 채워져 있어도 마찬가지입니다.

한 줄에 0만 주어지면 입력의 끝을 의미하며, 처리하지 않습니다.

각 테스트 케이스에 대해 완성된 퍼즐 격자를 입력과 같은 형식($N$개의 문자로 이루어진 $N$개의 행)으로 출력합니다. 서로 다른 퍼즐의 출력 사이에는 빈 줄을 하나 넣어 구분합니다.

이 퍼즐은 유일한 해를 가지도록 구성되어 있습니다.