Một ma trận vuông kích thước N x N được điền đầy bởi các số nguyên từ 1 đến ~N^2~ theo đường zig-zag. Ví dụ, với N=6 ta có ma trận dưới đây:

Có một robot đứng tại ô chứa số 1. Robot này có thể chuyển động theo 4 hướng (trên, dưới, trái, phải) đến ô khác chung cạnh nếu như ô này tồn tại.

Yêu cầu:

Cho dãy K lần chuyển động của robot. Viết chương trình xác định tổng của các số trong các ô mà robot đi qua (nếu một ô đi qua nhiều lần thì số trong ô này được cộng nhiều lần vào tổng)

Dữ liệu: File MATRIX.INP

• Dòng đầu tiên chứa hai số ngyên dương N và K (1≤N≤100000, 1≤K≤ 300000) lần lượt là kích thước của ma trận và số bước chuyển động của robot.

• Dòng thứ hai là dãy K ký tự 'U', 'D','L',R' mô tả các bước chuyển động ('U' - lên trên, 'D' - xuống dưới,'L' -sang trái,'R'-sang phải). Biết rằng với các hướng chuyển động này, robot không ra khỏi ma trận tại bất kỳ một bước nào.

Dữ liệu: File MATRIX.OUT

Một số nguyên dương là tổng các số trong các ô mà robot đi qua. Kết quả đảm bảo luôn là số nguyên 32 bit.

Sample Input 1

6 8
DDRRUULL

Sample Output 1

47

Sample Input 2

3 8
DDRRUULL

Sample Output 2

41

Sample Input 3

6 10
RRRRRDDDDD

Sample Output 3

203