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.


hide comments
Shaily Mittal: 2012-06-04 21:25:25

Got AC in 11th time.... :O :O

Aditya Pande: 2012-05-18 07:41:45

getting wa

Edit:
Wrote the function again from scratch and got ac

Last edit: 2012-11-28 14:04:33
Sourabh Jain: 2011-07-24 17:26:29

@K i am getting WA
is there any special case
please help me..

Last edit: 2011-07-24 17:38:09
K: 2011-06-29 21:10:39

I am using long long everywhere, I have manually checked matrix till 10*10 and my code is generating all the elements correctly. But still I am getting WA. Can you please give a hint on why this one is failing ( sub-id 5309881 ). I am not able to think of a case where this should fail.

<edit> Got AC </edit>

Last edit: 2011-07-02 21:04:32
Santiago Palacio: 2011-06-25 06:00:53

@ ganu: You're welcome!

ganu: 2011-06-20 20:11:57

@Santiago : Thanks

Last edit: 2011-06-21 04:39:09
Santiago Palacio: 2011-06-20 00:02:06

@ganu, it is not the same, you can see that here, the square is limited, while in CANTON the matrix is infinite...

ganu: 2011-06-19 16:19:17

ZIGZAG is the same problem as http://www.spoj.pl/problems/CANTON/ but with different i/o formats..

Got AC on the other one but WA here !!!..is there I may be missing?

Santiago Palacio: 2011-06-17 05:04:10

If it doesnt fit in 32-bit, it will in a 64-bit integer?

Anuj Arora: 2011-06-13 11:52:32

Any special test case, mine is giving wrong answer. I tried with various boundary cases, but nothing is helping much.

Any help would be appreciated.


Added by:Luka Kalinovcic
Date:2010-08-05
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS OBJC PERL6 VB.NET