题目描述

炸弹人是一款经典的游戏。

游戏规则是：在一张 $m$ 行 $n$ 列的地图上，. 代表空地，G 代表敌方军队，# 代表墙体。现在给出你的起始位置坐标，请你去安放一枚炸弹，使得远程引爆后能够消灭的敌人数最多。你的炸弹只能安放在空地上。假定炸弹的威力很大，只要不碰到墙体（遇到墙体威力就立减为零），它可以在爆炸点的行列上威力尽显，杀死本行本列上所有的人。从你的起始位置到你安放炸弹的地方，必须有一条可行的路（没有敌人，也没有墙体阻挡）。行列坐标都从 $0$ 开始。

输入格式

第一行包含四个自然数 $m, n, i, j$，表示地图有 $m$ 行 $n$ 列，安放炸弹的人的起始坐标是 $(i, j)$。

接下来是一张由 G、#、. 所构成的 $m$ 行 $n$ 列的地图。

输出格式

第一行包含两个整数，表示炸弹安放地的横纵坐标，两数间用一个空格分隔。

第二行仅一个整数，表示最多可以消灭的敌人数。

样例

13 13 3 3
#############
#GG.GGG#GGG.#
###.#G#G#G#G#
#.......#..G#
#G#.###.#G#G#
#GG.GGG.#.GG#
#G#.#G#.#.#.#
##G...G.....#
#G#.#G###.#G#
#...G#GGG.GG#
#G#.#G#G#.#G#
#GG.GGG#G.GG#
#############

7 11
10

数据范围与提示

• $m, n$ 均为正整数，且不大于 $26$。
• 起始位置保证在空地 . 上。
• 地图中至少存在一个可以安放炸弹的空地，且至少存在一个敌人。