BROJEVI

문제

A N×N matrix is filled with numbers 1 to N², diagonally in a zig-zag fashion. The illustration below shows numbers in the matrix for N = 6.

[이미지 1]

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). 

입력

The first line contains two integers N and K (1 ≤ N ≤ 100000, 1 ≤ K ≤ 300000), 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 one integer, the sum of numbers on visited cells. 

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

힌트

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.