题目描述

实验场地中会临时出现禁入格或禁入矩形区域。给定原始栅格地图、临时禁入操作、机器人起点和多个候选目标，请选择一个当前可达且优先级最高的目标。

禁入操作会把对应格子改为障碍。操作 G r c 禁用单个格子；操作 R r1 c1 r2 c2 禁用矩形区域。坐标均为 1-based，越界部分忽略。更新地图后，从起点做四方向 BFS。

在所有可达目标中，优先选择优先级 pri 更大的；若优先级相同，选择距离更短的；仍相同则选择编号更小的。

输入格式

第一行输入地图尺寸 H W。

接下来 H 行，每行一个长度为 W 的字符串，. 表示空地，# 表示障碍。

下一行输入临时禁入操作数 M。

接下来 M 行，每行为 G r c 或 R r1 c1 r2 c2。

下一行输入起点 sr sc。

下一行输入目标数量 T。

接下来 T 行，每行输入 id pri r c。

输出格式

若没有可选目标，输出 NO_TARGET。

否则输出：

id distance SELECTED

判定规则

使用标准输出比较。起点越界或起点为障碍时直接 NO_TARGET。目标必须在地图内、不是障碍且可由起点四方向到达。

数据范围与测试提示

• 正式测试会覆盖样例没有出现的边界输入，请不要依赖样例规模或样例顺序写特判。
• 输出只包含题目要求的字段，不要输出调试信息；浮点结果按题面要求保留 6 位小数。
• 临时禁入区可能使原本最短的通路失效，目标通路可能全部不可达。
• 预算、距离和安全余量的等号情况会被测试；输出应严格遵守无解与最优通路分支。
• 禁入矩形端点包含；起点越界或被封时直接 NO_TARGET，目标并列按优先级、距离、编号。

样例

输入样例 1

3 4
....
.#..
....
1
G 1 2
1 1
2
1 5 3 4
2 10 1 4

输出样例 1

2 7 SELECTED

输入样例 2

2 2
..
..
1
R 1 1 2 2
1 1
1
1 1 2 2

输出样例 2

NO_TARGET