You have a robot moving on an infinite plane, starting at $(0,0)$.

You send it a sequence of instructions, each being one of L, R, U, D. If the robot's current position is $(x,y)$, these four instructions move it to $(x-1,y)$, $(x+1,y)$, $(x,y+1)$, and $(x,y-1)$, respectively.

There may be several obstacles on the plane, but you do not know their exact locations. When the robot attempts to move, it first checks if the target position contains an obstacle; if an obstacle exists, it ignores the instruction.

Given an instruction sequence of length $n$, determine all possible positions where the robot could be after executing these $n$ instructions.

Input

The first line contains a positive integer $n$.

The second line contains a string of length $n$ consisting of L, U, R, D, representing the sequence of operations.

Output

The first line contains a positive integer $k$, representing the number of possible positions.

The next $k$ lines each contain two integers $x_i, y_i$, representing a possible position. You must output all positions sorted in ascending order, using $x$ as the primary key and $y$ as the secondary key.

Examples

Input 1

2
RU

Output 1

4
0 0
0 1
1 0
1 1

Note 1

One possible scenario is that there is an obstacle at $(1,0)$ but not at $(0,1)$. In this case, the robot ignores the first instruction and then executes the second instruction, arriving at $(0,1)$.

Input 2

4
LRUD

Output 2

4
0 -1
0 0
1 -1
1 0

Constraints

For $20\%$ of the data, $1\le n\le 2$.

For $40\%$ of the data, $1\le n\le 4$.

For all data, $1\le n\le 20$.