\begin{problem}{Аренда}{input.txt}{output.txt}{1 секунда}

Курорт \emph{Пятый сезон} состоит из ряда домов, которые довольно часто занимают их основные владельцы. 
Однако, в остальное время, они выполняют функцию домов под аренду. 
Поскольку на курорте не больше 26 домов, они идентифицируются прописными латинскими буквами.

Однажды звонит телефон менеджера курорта. Она принимает запрос на аренду дома на отпуск с датой прибытия 2 декабря и датой отъезда 9 декабря. 
Она смотрит на таблицу заказов, но не находит свободный дом на указанный период. 
Большая часть существующих заказов была сделана владельцами соответствующих домов (тех, кто хочет остаться в своих собственных помещениях), 
поэтому нежелательно перемещать существующую бронь из одного помещения в другое. 
Продолжая рассматривать таблицу заказов, менеджер, однако, находит выход и говорит: 
\emph{Я могу поселить Вас в здание B на первые 3 ночи, а потом переселить в здание F на остальное время отдыха. Вас это устроит?} 
Человек соглашается, заказ готов. Заметьте, что заказы делаются на ночь, так что заказ на одну ночь означает, что гость уедет на следующий день после прибытия.

Ваша задача - принять новый заказ на бронирование (не трогая существующие) с минимальным количеством переселений из дома в дом.

\InputFile

В первой строке входного файла находятся 2 положительных целых числа M и N. M - количество последовательных дней, на которые менеждер курорта ведет таблицу заказов, 
а N - количество домов на курорте. Помещения обозначаются заглавными латинскими буквами, начиная с A. Всего может быть не более 100 дней и не менее 3 помещений в таблице заказов. 
Дни обозначаются 1,2,3 ... M.

В следующих M строках находится таблица заказов. Каждая строка таблицы относится к определенному дню (в порядке 1, 2, 3, и т.д.), 
а каждый столбец таблицы - к определенному помещению курорта (в порядке A, B, C и т.д.) Символ \emph{X} (заглавная буква \emph{икс}) означает, что рассматриваемое помещение зарезервировано на этот день, 
тогда как \emph{O} (заглавная буква \emph{о}) означает, что помещение свободно.

За таблицей заказов следует строка запроса на аренду дома, состоящая из двух целых величин: даты заезда и даты отъезда. 
Дата заезда находится в пределе от 1 до M. Дата отъезда больше даты заезда и меньше или равна M+1.

\OutputFile

Если запрос на аренду может быть удовлетворен, то выходной файл должен содержать расписание (график) заказа с минимальным количеством переносов (из одного помещения в другое) 
на протяжении пребывания на курорте. Каждая строка расписания соответствует заселению в одно помещение и выглядит следующим образом:
\emph{<помещение>: <начальная дата> - <конечная дата>},
где <помещение> - это помещение, <начальная дата> - дата заезда гостя в помещение, а <конечная дата> - дата выезда гостя из помещения. 
Строки в расписании должны быть расположены в возрастающем порядке с даты заезда.

При наличии нескольких графиков с минимальным количеством переносов выберите график, который использует наименьшее \emph{наименование помещения} в первый день 
(так, помещение А имеет приоритет к помещению В). Если это сделать невозможно, выберите график с наименьшим номером помещения во второй день и так далее. 

Если запрос не может быть удовлетворен, напечатайте строку \emph{Not available} вместо расписания.

\Examples

\begin{example}%
\exmp{
10 7
XXXXXXX
XOXXXXO
XOXXXXO
XOXXXOX
OXXOXOX
XOXOXOX
OXXOXOX
OXXXXOX
XXXXXXX
XXXXXXX
2 9
}{
B: 2-5
F: 5-9
}%
\end{example}

\end{problem}
