102195: [AtCoder]ABC219 F - Cleaning Robot

Problem Statement

There is a cleaning robot on the square $(0, 0)$ in an infinite two-dimensional grid.

The robot will be given a program represented as a string consisting of four kind of characters L, R, U, D.
It will read the characters in the program from left to right and perform the following action for each character read.

1. Let $(x, y)$ be the square where the robot is currently on.
2. Make the following move according to the character read:
   • if L is read: go to $(x-1, y)$.
   • if R is read: go to $(x+1, y)$.
   • if U is read: go to $(x, y-1)$.
   • if D is read: go to $(x, y+1)$.

You are given a string $S$ consisting of L, R, U, D. The program that will be executed by the robot is the concatenation of $K$ copies of $S$.

Squares visited by the robot at least once, including the initial position $(0, 0)$, will be cleaned.
Print the number of squares that will be cleaned at the end of the execution of the program.

Constraints

• $S$ is a string of length between $1$ and $2 \times 10^5$ (inclusive) consisting of L, R, U, D.
• $1 \leq K \leq 10^{12}$

Input

Input is given from Standard Input in the following format:

$S$
$K$

Output

Print the number of squares that will be cleaned at the end of the execution of the program.

Sample Input 1

RDRUL
2

Sample Output 1

7

The robot will execute the program RDRULRDRUL. It will start on $(0, 0)$ and travel as follows:
$(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)$.
In the end, seven squares will get cleaned: $(0, 0), (1, 0), (1, 1), (2, 0), (2, 1), (3, 0), (3, 1)$.

Sample Input 2

LR
1000000000000

Sample Output 2

2

Sample Input 3

UUURRDDDRRRUUUURDLLUURRRDDDDDDLLLLLLU
31415926535

Sample Output 3

219911485785

问题描述

在一个无限的二维网格中，广场$(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$拼接而成的程序。

包括初始位置$(0, 0)$在内的机器人至少访问过一次的广场将被清洁。 在程序执行结束后，输出将被清洁的广场数量。

约束条件

• $S$是一个由L、R、U、D组成的长度在$1$到$2 \times 10^5$（含）之间的字符串。
• $1 \leq K \leq 10^{12}$

输入

输入通过标准输入给出，格式如下：

$S$
$K$

输出

输出程序执行结束后将被清洁的广场数量。

样例输入1

RDRUL
2

样例输出1

7

机器人将执行程序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)$。
最后，将有7个广场被清洁：$(0, 0), (1, 0), (1, 1), (2, 0), (2, 1), (3, 0), (3, 1)$。

样例输入2

LR
1000000000000

样例输出2

2

样例输入3

UUURRDDDRRRUUUURDLLUURRRDDDDDDLLLLLLU
31415926535

样例输出3

219911485785