## ZIGZAG - Zig-Zag rabbit

A N×N matrix is filled with numbers 1 to N2, diagonally in a zig-zag fashion.

The table below shows numbers in the matrix for 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

There is a rabbit in the cell containing number 1. A rabbit can jump to a neighboring cell (up, down, left or right) if that cell exists.

Given K valid rabbit jumps, write a program that will calculate the sum of numbers of all cells that rabbit visited (add the number to the sum each time rabbit visits the same cell).

### Input

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

The second line contains a sequence of K characters 'U', 'D', 'L' and 'R', describing the direction of each jump. The sequence of jumps will not leave the matrix at any moment.

### Output

Output one integer, the sum of numbers on visited cells.

Note: This number doesn't always fit in 32-bit integer type.

### Example

 ```Input: 6 8 DDRRUULL Output: 47``` ```Input: 3 8 DDRRUULL Output: 41``` ```Input: 6 10 RRRRRDDDDD Output: 203```

Clarification for the first sample: The rabbit visits cells 1, 3, 4, 9, 13, 8, 6, 2 and 1. Clarification for the second sample: The rabbit visits cells 1, 3, 4, 8, 9, 7, 6, 2 and 1. Clarification for the third sample: The rabbit visits cells 1, 2, 6, 7, 15, 16, 26, 27, 33, 34 and 36.