After exams, Shiv decides to retire from school and become a professional Snake Game player.

A snake of length ~N~ lies horizontally in an infinite ~2~-dimensional plane. It has its head at coordinates ~(0, 0)~ and its tail at ~(N-1, 0)~. For example, if the snake is of length ~4~, it would look like the following:

    0  3
  ........
  ........
0 ..HBBT..
  ........
  ........

In the above diagram, the snake's head (cell marked with H) is at coordinates ~(0, 0)~, its head (cell marked with T) is at coordinates ~(3, 0)~, and its body parts (all cells marked with B) lies horizontally in a line between its head and tail. All body parts are connected.

The snake can move in four directions, up, down, left, and right, represented by the characters UDLR respectively.

Specifically, if the snake's head is currently at coordinates ~(x, y)~, a U instruction will bring the head to ~(x, y+1)~, a D instruction will bring the head to ~(x, y-1)~, a L instruction will bring the head to ~(x-1, y)~, and a R instruction will bring the head to ~(x+1, y)~.

For each instruction, the snake will move its head in the direction specified, and all other body parts will take the place of the old coordinates of the body part that is connected (closer to the head, or the head itself) to it. For example, the following would occur if the snake in the above diagram went up (U):

    0 23
  ........
1 ..H.....
0 ..BBT...
  ........
  ........

The head is now at ~(0, 1)~, and the body part connected to the head is now at ~(0, 0)~, which takes the place of the old coordinates of the head. The other body part and the tail follow in the same manner. Note that the movement occurs for all body parts simultaneously.

Shiv has a string of length ~M~ consisting of only the characters UDLR, instructions for the snake's movement. You are to simulate the snake's movement and determine the earliest instruction in which the snake hits any part of its body with its head within the movement instructions, including the head and tail. If this never occurs, output -1. Note that if the snake turns in a directly opposite direction (ex. UD), it is considered a hit.

Constraints

For all subtasks,

~3 \le N \le 100~

~1 \le M \le 10^5~

Subtask 1 [50%]

~1 \le M \le 100~

Subtask 2 [50%]

No additional constraints.

Input Specification

The first line of input will contain the integers ~N~ and ~M~, space-separated.

The next line will contain a string of length ~M~ consisting of only the characters UDLR.

Output Specification

If the snake hits any part of its body with its head within the movement instructions, output the index of the earliest instruction (The index of the first instruction/character of the string is ~1~). If this never occurs, output -1.

Sample Input 1

6 5
URDRU

Sample Output 1

3

Explanation for Sample Output 1

The snake's trajectory for each instruction is as follows:

Initial:

..........
..........
..HBBBBT..
..........
..........

1: U

..........
..........
..H.......
..BBBBT...
..........
..........

2: R

..........
..........
..BH......
..BBBT....
..........
..........

3: D

..........
..........
..BB......
..BCT.....
..........
..........

At this point, the snake's head has hit a body part of itself (at cell marked C). Thus, the output is 3.

Sample Input 2

4 4
URDL

Sample Output 2

-1

Sample Input 3

3 11
URDLURDLUDR

Sample Output 3

10