Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

BCZIGZAG - Ma trận zig-zag

Một ma trận N×N được đánh số từ 1 tới N2, theo các đường chéo hình zig-zag. Xem ví dụ dưới để hiểu rõ hơn cách đánh số: Với 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

Con thỏ ở trong ô số 1. Nó có thể nhảy sang các ô kề cạnh (trên, dưới, trái, phải) nếu ô đó tồn tại.

Cho K bước nhảy hợp lệ, viết chương trình tính tổng tất cả các số trên tất cả các ô mà thỏ ghé thăm (tức là mỗi bước đi qua 1 ô thì cộng số ở ô đó vào tổng).

Input

Dòng 1: 2 số nguyên cách nhau bởi dấu cách N và K  (1 ≤N ≤ 100 000 , 1 ≤ K ≤ 300 000) lần lượt là kích thước của ma trận và số bước nhảy của con thỏ.

Dòng 2: Chứa dãy có K kí tự có thể là "U","D","L","R" tương ứng với các bước nhảy "lên","xuống","trái","phải". Các bước nhảy đảm bảo rằng sẽ không nhảy ra khỏi ma trận bất cứ lúc nào.

Output

Một số nguyên duy nhất là tổng của các ô mà con thỏ ghé thăm. 

Lưu ý:

50% số test có N ≤ 1000

Example

Input:
6 8
DDRRUULL

Output:
47
Giải thích: Con thỏ ghé thăm các ô: 1, 3, 4, 9, 13, 8, 6, 2 và 1
Input:
3 8
DDRRUULL
Output:
41
Giải thích: Con thỏ ghé thăm các ô: 1, 3, 4, 8, 9, 7, 6, 2 và 1
Input:
6 10
RRRRRDDDDD
Output:
203
Giải thích: Con thỏ ghé thăm các ô: 1, 2, 6, 7, 15, 16, 26, 27, 33, 34 và 36.

ID RESULT TIME
code...



Được gửi lên bởi:adm
Ngày:2011-11-11
Thời gian chạy:0.200s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:ASM32-GCC ASM32 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL6 PERL PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.