题目描述

Konia 公司专门生产廉价移动设备，最近市场份额不断下滑。为了拯救公司，董事会又一次决定改造所有 Konia 设备上最著名的游戏——《贪吃蛇》。是的，又是它。

游戏发生在一个由 $H$ 行 $W$ 列组成的方格场地上。行从上到下编号为 $1$ 到 $H$，列从左到右编号为 $1$ 到 $W$。一个格子 $A$ 用 $(A_r,A_c)$ 表示。

两个格子 $A,B$ 若满足

则称它们相邻。此外，场地上下边界、左右边界相连：所有 $(1,i)$ 与 $(H,i)$ 相邻，所有 $(i,1)$ 与 $(i,W)$ 相邻。

场上有一条蛇，由格子序列 $A_1,A_2,\ldots,A_L$ 表示，其中 $L$ 为正整数，表示长度。每个格子在序列中最多出现一次，序列中相邻的两个格子必须是场地上的相邻格子。显然蛇的最大允许长度为 $H\cdot W$。格子 $A_1$ 称为蛇头。

玩家只控制蛇头移动，可以使用四种命令：

• L：蛇头左移一列。若原本在最左列，则移动到最右列，同一行不变。
• R：蛇头右移一列。若原本在最右列，则移动到最左列。
• U：蛇头上移一行。若原本在最上行，则移动到最下行，同一列不变。
• D：蛇头下移一行。若原本在最下行，则移动到最上行。

玩家执行命令后，蛇的所有格子同时移动：蛇头按命令移动，其他格子依次“跟随”前一节，即对所有 $i=2\ldots L$，格子 $A_i$ 变为原来的 $A_{i-1}$。例如第二节移动到原蛇头位置，第三节移动到原第二节位置，依此类推。

游戏在蛇撞到自己时结束，也就是某一步后蛇的所有格子不再互不相同。这可能是蛇头移动到身体某一节所在格子导致的。特别地，当蛇至少有三节时，让蛇头朝 $A_2$ 所在方向移动会导致碰撞，因为新状态中 $A_1$ 和 $A_3$ 会重合。

经典游戏中还可以吃苹果变长，但本题不考虑这一机制。

在 Konia 的新版本中，玩家不再需要定期按键，而是在开始时放置蛇，并编写一段长度为 $K$ 的动作程序，也就是给出 $K$ 个蛇头移动命令。游戏开始后，蛇会依次执行这些命令。如果成功执行完全部 $K$ 个命令，就从头开始重复执行同一段程序，如此循环，直到蛇撞到自己或者玩家厌倦观看。

现在给定两个不同的素数 $H,W$ 作为场地大小，以及给定的程序，请求出可以在场地中放置的、不论程序重复执行多久都不会撞到自己的蛇的最大长度。

一个数称为素数，当且仅当它恰好有两个不同的正整数因子。

输入格式

第一行包含三个整数 $H,W,K$，表示场地大小与程序长度。

保证 $H$ 和 $W$ 是不同的素数。

第二行包含一个长度为 $K$ 的字符串，表示命令序列。字符串中只包含 L、R、U、D。

输出格式

输出一个整数，表示一条能够按照该命令序列无限移动且永不撞到自身的蛇的最大长度。

数据范围

$2 \le H,W \le 10^9+9$，$H\ne W$。
$1 \le K \le \min(100000,H\cdot W)$。

样例

样例 1

5 7 4
LURD

4

样例 2

11 2 2
RD

21

样例 3

5 13 4
ULUD

2

样例解释

第一个样例中，执行完全部四条命令后蛇头回到起点，因此长度超过 $4$ 的蛇无法存活超过四步。

第二个样例中，合理放置的蛇几乎可以占满整个场地。

评分说明