该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

风向森林

题目背景

Y 同学进入了一片会改变方向的风向森林。

森林中的每个位置都有不同的风向效果。机器人每到一个位置，都会先受到当前位置的风向影响，然后再尝试向当前方向前进一步。

机器人可能会在森林中反复进入相同的状态。这里的状态不仅包括它所在的位置，还包括它当前的朝向。

现在请你判断：机器人在行动过程中，第一次出现重复状态是在第几次行动之后。

题目描述

给定一个 $n$ 行 $m$ 列的地图。

地图中每个位置可能是以下字符之一：

• .：普通空地，不改变方向；
• L：左旋风，会让机器人向左转 $45^\circ$；
• R：右旋风，会让机器人向右转 $45^\circ$；
• B：反向风，会让机器人转向相反方向；
• x：障碍，机器人不能进入。

机器人有 $8$ 种朝向，用整数 $0\sim 7$ 表示：

机器人初始位于 $(x_0,y_0)$，初始朝向为 $d_0$。保证初始位置不是障碍。

接下来机器人会执行 $k$ 次行动。每次行动按照下面的规则进行：

1. 机器人先根据当前格子的字符调整朝向：
   • 若当前格子为 .，朝向不变；
   • 若当前格子为 L，朝向变为 $(d+7)\bmod 8$；
   • 若当前格子为 R，朝向变为 $(d+1)\bmod 8$；
   • 若当前格子为 B，朝向变为 $(d+4)\bmod 8$。
2. 然后机器人尝试向当前朝向前进一步。
3. 如果目标位置在地图内，并且不是障碍 x，机器人移动到目标位置。
4. 否则机器人保持原地不动，并且朝向变为 $(d+1)\bmod 8$。

如果某次行动结束后，机器人的完整状态 $(x,y,d)$ 曾经出现过，则称这次行动后出现了重复状态。

请你输出第一次出现重复状态的行动编号。若在 $k$ 次行动内都没有出现重复状态，则输出 -1。

注意：初始状态也算作已经出现过。

输入格式

第一行输入一个整数 $T$，表示测试数据组数。

对于每组数据：

第一行输入三个整数 $n,m,k$，表示地图的行数、列数和行动次数。

第二行输入三个整数 $x_0,y_0,d_0$，表示机器人的初始位置和初始朝向。

接下来 $n$ 行，每行输入一个长度为 $m$ 的字符串，表示地图。

输出格式

对于每组数据，输出一行一个整数。

若机器人第一次出现重复状态是在第 $t$ 次行动后，输出 $t$；否则输出 -1。

样例输入

1
3 4 12
2 1 0
....
.Rx.
..L.

样例输出

9

样例解释

初始时，机器人位于 $(2,1)$，朝向为东，也就是状态 $(2,1,0)$。

机器人前几次行动后的状态如下：

第 $9$ 次行动后的状态和第 $8$ 次行动后的状态完全相同，都是 $(3,3,4)$。

因此第一次出现重复状态的行动编号是 $9$。

数据范围

对于 $100\%$ 的数据，满足：

• $1\le T\le 5$；
• $1\le n,m\le 1000$；
• $1\le k\le 10^6$；
• $1\le x_0\le n$；
• $1\le y_0\le m$；
• $0\le d_0\le 7$；
• 地图字符只包含 .、L、R、B、x；
• 初始位置一定不是障碍。