AT_abc219_f [ABC219F] Cleaning Robot

# [ABC219F] 清扫机器人 ## **问题描述** 一个清扫机器人被放置在无限扩展的二维网格的方格 $(0, 0)$ 上。 给定了一个由四种类型的字符 `L`、`R`、`U`、`D` 组成的字符串程序。 机器人根据给定的程序，依次读取每个字符，并针对每个字符采取以下行动： 1. 将机器人的当前位置设为方格 $(x, y)$ 2. 根据读取的字符执行以下移动： - 当读取 `L` 时：向左移动到方格 $(x-1, y)$。 - 当读取 `R` 时：向右移动到方格 $(x+1, y)$。 - 当读取 `U` 时：向上移动到方格 $(x, y-1)$。 - 当读取 `D` 时：向下移动到方格 $(x, y+1)$。 给定一个由 `L`、`R`、`U`、`D` 组成的字符串 $S$ 和整数 $K$。机器人执行的程序是将字符串 $S$ 重复连接 $K$ 次。 一旦机器人访问过的方格（包括机器人的初始位置 $(0, 0)$）就会被清扫。 请输出在机器人执行程序结束后，被清扫的方格的数量。

输入通过标准输入给出。 > $S$ $K$

输出在机器人执行程序结束后，被清扫的方格的数量。 ## **样例 #1** **样例输入 #1** ``` RDRUL 2 ``` **样例输出 #1** ``` 7 ``` **样例 #2** **样例输入 #2** ``` LR 1000000000000 ``` **样例输出 #2** ``` 2 ``` **样例 #3** **样例输入 #3** ``` UUURRDDDRRRUUUURDLLUURRRDDDDDDLLLLLLU 31415926535 ``` **样例输出 #3** ``` 219911485785 ``` ## 约束 - $S$是长度介于$1$和$2 \times 10^5$之间（包括$1$和$2 \times 10^5$）的字符串，由“l”、“R”、“u”和“d”组成。 - $1 \leq K \leq 10^{12}$ ### 示例输出1 机器人将执行程序“rdrulrdrul”。它将从$(0, 0)$开始，按如下方式运行： $(0, 0) \rightarrow (1, 0) \rightarrow (1, 1) \rightarrow (2, 1) \rightarrow (2, 0) \rightarrow (1, 0) \rightarrow (2, 0) \rightarrow (2, 1) \rightarrow (3, 1) \rightarrow (3, 0) \rightarrow (2, 0)$. 最后，七个方块将被清理：$(0, 0), (1, 0), (1, 1), (2, 0), (2, 1), (3, 0), (3, 1)$。 ​

### 制約 - $ S $ は `L` 、`R` 、`U` 、`D` からなる長さ $ 1 $ 以上 $ 2\ \times\ 10^5 $ 以下の文字列 - $ 1\ \leq\ K\ \leq\ 10^{12} $ ### Sample Explanation 1 ロボットが実行するプログラムは `RDRULRDRUL` です。ロボットは初期位置であるマス $ (0,\ 0) $ からはじめ、 $ (0,\ 0)\ \rightarrow\ (1,\ 0)\ \rightarrow\ (1,\ 1)\ \rightarrow\ (2,\ 1)\ \rightarrow\ (2,\ 0)\ \rightarrow\ (1,\ 0)\ \rightarrow\ (2,\ 0)\ \rightarrow\ (2,\ 1)\ \rightarrow\ (3,\ 1)\ \rightarrow\ (3,\ 0)\ \rightarrow\ (2,\ 0) $ と移動します。 その後掃除されているマスは、$ (0,\ 0),\ (1,\ 0),\ (1,\ 1),\ (2,\ 0),\ (2,\ 1),\ (3,\ 0),\ (3,\ 1) $ の $ 7 $ 個です。