P5486 [JLOI2010] 世界杯租房

南非世界杯组委会指定了在此期间可提供的一些旅馆供球迷租赁，名为阿凡达的即是其中一所。因为阿凡达旅馆房子的数目不超过 $26$，所以它们可以用 $26$ 个大写字母表示。 有一天，刘经理的电话响了，他接到了一个租赁房屋的请求，要求从 $6$ 月 $12$ 日晚起租到 $6$ 月 $19$ 日中午。于是他查看了预定表，但是并没有发现一间房屋能够直接满足要求。比如房主可能因为一些私人原因需要留在自己的房子中，所以这个游客不得不在其中的一间先住上几天再搬到另一间住上几天。他详细检查了预定表后，对旅客说：“我将你先在 $B$ 安置 $3$ 天，再将你安排到 $F$ 去度过剩余的旅途。” 你的目标是使得游客从一间房屋搬到另一间房屋的次数最少。 注意在旅馆的计费中，总是将某一天的晚上到第二天的中午视作一天。

输入文件包括多组数据。每组数据输入文件第一行包括两个整数 $M$ 和 $N$。$M$ 表示日程表上的天数，$N$ 表示公寓的数目。天数不超过 $100$ 天，从 $1$ 开始计数，公寓不超过 $26$ 个，从 $A$ 开始计数。 接下来 $M$ 行，每行包括 $N$ 个字母，表示从第i天晚到次日中午，该公寓是否已经被出租，$X$ 代表被出租，$O$ 代表未被出租。 最后一行包括两个整数 $s,t$，代表旅客从第 $s$ 天晚入住到第 $ (t+1) $ 天中午结束旅行。$1\leq s

对于每一组数据，首先打印测试数据的编号，冒号和一个空行。接下来输出换房次数最少的方案，每一行使用如下格式： `: -` 其中 `` 为房屋编号，`` 和 `` 分别为该旅客入住和离开该房屋时间。 注意，如果存在多种方案满足换房次数最少，输出其中字典序最小的方案。 如不存在这样的方案，输出一行“$\texttt{Not available}$”。 每两组输出之间以一个空行隔开。输出文件的末尾不要加空行。