Gennadiy 正在玩他最喜欢的游戏。

游戏关卡是一个由正方形单元格组成的网格地图。每个单元格要么是空的，要么填满了泥土。空单元格可以包含关卡的起点（入口）或终点（出口）。玩家可以在空单元格上行走，每次移动可以走到与其相邻且共享边的单元格。玩家不能移动到地图外。

有些关卡无法通过常规手段通过，在这种情况下，需要使用炸弹。炸弹可以附着在泥土上并爆炸，从而清除附近单元格中的泥土。在本题中，假设如果玩家当前所在的单元格与泥土单元格相邻，则玩家可以在其当前所在的单元格中放置炸弹。炸弹爆炸后，爆炸区域内的所有单元格都将变为空单元格，从而可以通行。玩家、关卡起点和关卡终点可以安全地处于爆炸区域内，它们不会受到爆炸的影响。

爆炸区域是一个以炸弹放置单元格为中心的八边形。爆炸区域有两个参数 $P$ 和 $R$，其精确形状定义如下：沿着其外围的边界单元格移动，你必须向上移动 $P$ 次，然后向右上（斜向）移动 $R$ 次，然后向右移动 $P$ 次，然后向右下（斜向）移动 $R$ 次，然后向下移动 $P$ 次，依此类推（即向左下移动 $R$ 次，向左移动 $P$ 次，向左上移动 $R$ 次），直到回到起点单元格。参数在某些取值下的爆炸区域形状如下图所示：

炸弹是有限且宝贵的资源，因此应当节省使用。请帮助 Gennadiy 用最少数量的炸弹通过关卡。

输入格式

输入的第一行包含两个整数 $N$ 和 $M$，分别表示地图的行数和列数（$1 \le N, M \le 1500$）。

第二行包含两个整数 $P$ 和 $R$，表示爆炸区域的参数（$0 \le P, R \le 1000$）。保证 $P$ 是偶数，且 $P + R > 0$。

接下来是关卡地图，共 $N$ 行，每行包含 $M$ 个字符。每个字符描述了对应单元格的内容：

• @ — 填满泥土的单元格。
• . — 空单元格。
• S — 包含关卡起点的空单元格。
• E — 包含关卡终点的空单元格。

保证地图中仅包含一个起点单元格和一个终点单元格。

输出格式

输出的第一行包含一个整数 $B$，表示通过关卡所需的最少炸弹数量（$B \ge 0$）。

在接下来的 $B$ 行中，按照引爆顺序输出必须放置炸弹的单元格。每行输出两个整数 $u$ 和 $v$，分别表示该单元格的行号和列号（$1 \le u \le N, 1 \le v \le M$）。

样例

输入样例 1

9 10
0 1
@@......@@
@@S@@@@...
@@@@@...@.
@@@@@@@@@@
@@@@@@@@@@
.........@
@@@.@@@@..
@...@@@E@.
@@@@@@@@@@

输出样例 1

3
3 7
4 7
8 10

输入样例 2

4 5
2 1
S@@@@
..@@@
@@@@E
@@@@@

输出样例 2

1
2 2

输入样例 3

7 5
4 0
@E@@@
@@.@@
@@@@@
@@@@@
@@...
@@...
@@..S

输出样例 3

2
5 5
2 3

说明

在第一个样例中，爆炸呈十字形，会影响与炸弹单元格共边的单元格。需要两颗炸弹来破坏第 4 行和第 5 行的墙，再需要一颗炸弹来显露终点。

在第二个样例中，爆炸威力足够大，只需一颗炸弹即可炸出一条通道。

在第三个样例中，需要两颗炸弹。注意，禁止将第一颗炸弹放置在单元格 $(6, 4)$，因为该单元格不与泥土相邻。