时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
Special Judge, 64bit IO Format: %lld
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
Special Judge, 64bit IO Format: %lld
题目描述
SuperSodaSea 在玩一个走迷宫的游戏。迷宫是一个大小为 
的矩阵，从上到下依次给行编号为 
，从左到右依次给列编号为 
。
游戏规则很简单：从起点出发，每步操作可以移动到上、下、左、右四个方向的空地上，直到终点。
为了增加游戏的难度，在这个游戏中，从起点到终点并不一定会有直接的通路。当然，相对应地，玩家可以使用名为“穿越”的技能：从一块空地移动到距离至多为 d 另一片空地上（起点和终点也视为空地），无论中间是否有障碍。
在使用技能时的距离是指“切比雪夫距离”，即如果从)
穿越到 )
需要满足 
。“穿越”只能最多使用一次，使用时算一步操作。
现在你需要帮 SuperSodaSea 计算出给定的迷宫，他最少需要多少步才能到达终点，并给出一个方案。
游戏规则很简单：从起点出发，每步操作可以移动到上、下、左、右四个方向的空地上，直到终点。
为了增加游戏的难度，在这个游戏中，从起点到终点并不一定会有直接的通路。当然，相对应地，玩家可以使用名为“穿越”的技能：从一块空地移动到距离至多为 d 另一片空地上（起点和终点也视为空地），无论中间是否有障碍。
在使用技能时的距离是指“切比雪夫距离”，即如果从
现在你需要帮 SuperSodaSea 计算出给定的迷宫，他最少需要多少步才能到达终点，并给出一个方案。
输入描述:
第一行包含 3 个整数 n, m, d (,
)，中间以空格分隔，分别表示地图的行数、列数和穿越的最大距离。
接下来 n 行，每行包含一个长度为 m 的字符串，表示地图。
其中，. 表示空地，X 表示障碍，S 表示起点，T表示终点。
输入保证有且仅有一个起点和一个终点。
输出描述:
第一行输出一个整数 t 表示最少所需要的步骤。
接下来 t + 1 行，每行输出两个整数，中间以空格分隔， 表示每一步所经过的坐标。其中，第一行和最后一行应分别对应起点和终点。
特别地，如果没有可以走到终点的方案，则在一行输出 -1。
答案不唯一，任何符合要求的答案都会被判为正确。
示例1