J. Journey of the Balloon Runner
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

One ICPC tradition never dies: every solved problem earns the team a balloon. Elisa is the one who delivers them.

The floor of the contest hall is covered with square tiles, and the organizers describe it as an infinite grid of cells. Elisa hands out the balloons. She starts at the cell $$$(0,0)$$$, where the balloon table stands, and the volunteer coordinator has already written her whole route for this round as one non-empty string of orders. Elisa follows the orders from left to right, and each order takes her to one of the four cells next to the current one:

  • U: walk one cell up;
  • D: walk one cell down;
  • L: walk one cell left;
  • R: walk one cell right.

The hall is large enough that she never reaches a wall, and her route may cross itself as many times as the coordinator wants.

After the round, the cleaning crew wants to know how much of the floor was used. Find the number of distinct cells Elisa steps on, including the cell $$$(0,0)$$$ where she starts.

Input

The only line contains a non-empty string $$$s$$$ ($$$1 \le |s| \le 2 \cdot 10^5$$$) — the route of the balloon runner. Every character of $$$s$$$ is one of U, D, L, or R.

Output

Print one integer — the number of distinct cells visited by the runner, including cell $$$(0,0)$$$.

Examples
Input
URDL
Output
4
Input
RRUULLDD
Output
8
Input
UUUDDD
Output
4
Note

In the first example, the runner visits $$$(0,0)$$$, $$$(0,1)$$$, $$$(1,1)$$$, and $$$(1,0)$$$. The last order returns her to $$$(0,0)$$$, which was already counted.

In the second example, the runner follows the boundary of a $$$2\times 2$$$ square. She returns to the initial cell after visiting eight distinct cells.