Rabbit Movement

Time limit1sMemory limit128 MB

Summary

Simulate a rabbit walking on an N×N zigzag-diagonal numbered grid following given moves and sum all visited cell values.

Level: Medium4 of 10
Topics: Matrix, Simulation, Math
Solved: No attempts yet

Problem

The numbers from 1 to N^2 are written in an N×N matrix in zigzag diagonal order. The table below shows the matrix when N=6.


1	2	6	7	15	16
3	5	8	14	17	26
4	9	13	18	25	27
10	12	19	24	28	33
11	20	23	29	32	34
21	22	30	31	35	36

The rabbit starts on the cell containing 1, the upper-left cell. In one jump, it can move to an adjacent cell up, down, left, or right.

Given the rabbit's jump directions, compute the sum of the numbers written on every cell the rabbit visits, including the starting cell. If the rabbit visits the same cell more than once, add that cell's number every time it is visited. The given moves never take the rabbit outside the matrix.

Input

The first line contains N and K. (1 ≤ N ≤ 100,000, 1 ≤ K ≤ 300,000) N is the size of the matrix, and K is the number of jumps.

The second line contains a string of length K. Each character is one of U, D, L, and R, describing the direction of each jump.

Output

Print the sum of the numbers written on the cells visited by the rabbit, including the starting cell. This value may exceed the range of a 32-bit integer.

Examples3

Example 1
Input
```
6 8
DDRRUULL
```
Expected output
```
47
```
Example 2
Input
```
3 8
DDRRUULL
```
Expected output
```
41
```
Example 3
Input
```
6 10
RRRRRDDDDD
```
Expected output
```
203
```


1	2	6	7	15	16
3	5	8	14	17	26
4	9	13	18	25	27
10	12	19	24	28	33
11	20	23	29	32	34
21	22	30	31	35	36


1	2	6	7	15	16
3	5	8	14	17	26
4	9	13	18	25	27
10	12	19	24	28	33
11	20	23	29	32	34
21	22	30	31	35	36


1	2	6	7	15	16
3	5	8	14	17	26
4	9	13	18	25	27
10	12	19	24	28	33
11	20	23	29	32	34
21	22	30	31	35	36