题目描述

给定一个由方格组成的赛车场。每个格子是道路、障碍、起点或终点之一。赛车始终位于某个格子的中心，并具有整数速度向量 $(v_r,v_c)$。

每一回合按以下顺序进行：

1. 调整速度。速度的两个分量都可以独立增加 $1$、减少 $1$ 或保持不变；
2. 按调整后的速度移动。若当前位于 $(r,c)$，速度为 $(v_r,v_c)$，则目标位置为 $(r+v_r,c+v_c)$，赛车沿两个格子中心之间的线段运动。

字符含义如下：

• .：普通道路；
• X：障碍；
• S：起点；
• F：终点。

赛车的运动线段如果进入障碍格的内部，则发生碰撞，该次移动非法；仅仅擦到障碍格的边界或角点不会碰撞。若运动线段在途中接触到终点格，则立即视为到达终点，不要求最终停在 F 的中心。驶出整个地图同样视为碰撞。

赛车初始位于 S 格中心，初速度由输入给出。求到达 F 所需的最少回合数；若永远无法安全到达，输出 -1。

输入格式

第一行四个整数 $H,W,v_r,v_c$，分别表示地图行数、列数以及初始速度的两个分量。

接下来 $H$ 行，每行一个长度为 $W$ 的字符串，表示赛车场。

输出格式

输出一个整数：最少回合数；若无法到达则输出 -1。

数据范围

• $1\le H,W\le 50$；
• $-50\le v_r,v_c\le 50$；
• 地图只包含 .X、S、F 四种字符；
• S 和 F 各恰好出现一次。

样例 1

1 19 0 0
S.................F

6

样例 2

1 19 0 8
S.................F

2

样例 3

2 10 0 4
S...X....F
..........

3