휴가철 숙소 예약

'다섯 번째 계절' 리조트에는 여러 채의 콘도미니엄이 있습니다. 콘도는 대부분 소유주가 직접 사용하지만, 비어 있는 기간에는 휴가용 숙소로 대여됩니다. 리조트의 콘도는 최대 $26$채이므로, 각 콘도는 알파벳 대문자 하나로 구분합니다.

손님이 도착 날짜와 출발 날짜로 예약을 요청합니다. 기존 예약은 대부분 소유주 본인의 예약이므로 다른 방으로 옮길 수 없습니다. 다만 손님을 밤마다 다른 방으로 이동시키는 것은 가능합니다. 예를 들어 처음 세 밤은 B호에 묵고, 남은 기간은 F호로 옮겨 묵을 수 있습니다.

예약은 밤(night) 단위로 셉니다. 도착 날짜가 $a$, 출발 날짜가 $d$인 요청은 $a, a+1, \dots, d-1$일의 밤에 방을 사용하며, 손님은 $d$일에 떠납니다. 즉 1박 예약은 도착 다음 날 떠납니다.

기존 예약을 바꾸지 않으면서 이 요청을 처리하되, 요청 기간 동안 방을 옮기는 이동 횟수를 최소로 하는 것이 목표입니다.

입력은 여러 개의 테스트 케이스로 이루어집니다.

각 테스트 케이스의 첫 줄에는 두 양의 정수 $M$과 $N$이 주어집니다. $M$은 예약표가 다루는 연속된 날의 수, $N$은 리조트의 방 수입니다. 날은 최대 $100$일이고 방은 최소 $3$개입니다. 날은 $1, 2, \dots, M$로 번호를 매기고, 방은 $A$부터 시작하는 연속된 대문자로 표시합니다.

이어서 $M$개의 줄이 예약표를 나타냅니다. $i$번째 줄은 $i$일에 해당하고, 그 줄의 $j$번째 문자는 $j$번째 방($A, B, C, \dots$)에 해당합니다. 문자 X는 그날 그 방이 이미 예약되어 있음을, O는 사용 가능함을 뜻합니다.

예약표 다음 줄에는 새 요청의 도착 날짜와 출발 날짜, 두 정수가 주어집니다. 도착 날짜는 $1 \dots M$ 범위이고, 출발 날짜는 도착 날짜보다 크며 $M+1$ 이하입니다.

입력의 끝은 $M = N = 0$인 줄로 표시되며, 이 줄은 처리하지 않습니다.

각 테스트 케이스마다 먼저 케이스 번호와 콜론을 출력하고, 그다음 빈 줄 하나를 출력합니다.

요청을 처리할 수 있으면, 이동 횟수가 최소인 일정을 출력합니다. 일정의 각 줄은 한 방에서의 연속된 숙박 하나를 나타내며 다음 형식을 따릅니다.

<방>: <시작일>-<종료일>

여기서 <방>은 방의 문자, <시작일>은 그 방에 들어가는 날, <종료일>은 그 방에서 나오는 날입니다. 줄은 시작일이 커지는 순서로 정렬합니다.

동점 처리. 이동 횟수가 최소인 일정이 여러 개일 수 있습니다. 그중에서 방 문자를 날짜순으로 사전식으로 가장 작게 만드는 일정을 고릅니다. 즉 첫 밤에 가장 작은 방 문자를 우선하고($B$보다 $A$ 우선), 그래도 같으면 둘째 밤의 방 문자를 더 작게, 이런 식으로 정합니다. 이 규칙으로 답은 유일해집니다.

요청을 처리할 수 없으면 다음 한 줄만 출력합니다.

Not available

연속된 테스트 케이스의 출력은 빈 줄 하나로 구분합니다.