轰炸
题号:NC203037
时间限制:C/C++/Rust/Pascal 4秒,其他语言8秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
Special Judge, 64bit IO Format: %lld

题目描述

    二战美国空军英雄李梅在1945年对东京实施了大轰炸,将东京炸成一片焦土,军工设施损失殆尽,强力地震慑了日本帝国主义,挫败了军国政府“一亿玉碎”的妄想。如果没有李梅的东京轰炸和曼哈顿计划的两枚原子弹,美国军队将不得不像强攻塞班岛,硫磺岛,冲绳岛那样,付出巨大伤亡进攻日本本土。可以说,李梅的东京轰炸和奥本海默的核弹救下了100万美军的生命。

    现在,让我们一起A掉这道题来对伟大的反法西斯战争致以崇高的敬意。

    假想你是李梅,通过空中侦察得到了日军重要军事设施的位置及其周围环境,军事设施的周边有可以让火势蔓延的建筑和空旷的防火带(这些防火带的一部分是日军有意地炸毁民房而制造的),由于投掷燃烧弹需要考虑风向,你还获得了轰炸地点近期的天气预报。

    当你投下燃烧弹后,投弹位置即燃烧起来。每一时刻,已经燃烧的位置会继续燃烧着,然后风力会使得火场向刮风的方向延伸一格,当然不会延伸到防火带上。如果轰炸目标着火,此目标即告毁灭。

    你只有一枚燃烧弹,请你设计燃烧弹的投掷位置来在规定时间内毁掉所有轰炸目标。

输入描述:

第一行输入三个整数,分别代表时间限制,以及地图的行数和列数。

第二行输入一个长度等同于的字符串,仅包含’L’,’R’,’U’,’D’,代表每一时刻的风向。

从第三行开始输入一个列的矩阵,代表轰炸目标附近的地图,’X’代表轰炸目标,’H’代表易燃物,’O’代表防火带。

为了讨论方便,假想地图最外围都是防火带,即火势不会延烧到地图外。

输出描述:

如果可以找到一种投弹方案消灭所有轰炸目标,则按如下方式输出任意一个答案:

输出个整数,代表投下燃烧弹的行数和列数。

如果找不到这样的方案,则输出字符串“We wait for nuclear bomb!”(不含引号)

示例1

输入

复制
5 4 5
RRRUU
HHHXO
OHOHO
HXHHO
OHOOH

输出

复制
3 2

说明

备注:

保证

轰炸的总目标数不会超过