A novel inventor of the twenty-first century, Helen, has recently developed a device that tracks her position.
However, this device is simply a prototype and may not work as intended.

Helen has invited you to help her test this prototype on a cartesian plane.
She gives you a string $S$ of length $N$ consisting of characters U, L, D, R, indiciating up, left, down and right respectively.

• Moving up moves you from $(x, y)$ to $(x, y+1)$.
• Moving left moves you from $(x, y)$ to $(x-1, y)$.
• Moving down moves you from $(x, y)$ to $(x, y-1)$.
• Moving right moves you from $(x, y)$ to $(x+1, y)$.

Initially, you are on the position $(x_0, y_0)=(0, 0)$.
Everytime you follow the $i$-th character of the string $(1\le i\le N)$, you reach the position $(x_i, y_i$).
After doing the $i$-th move, the prototype displays a set of coordinates $(x_d, y_d)$.
After an initial round of testing, she realizes that the prototype has a fatal flaw!
In fact, the coordinates $(x_d, y_d)=(x_j, y_j)$ for any $j$ where $0\le j\le i$.

With this realization, she decides to test the device $Q$ more times to figure out the source of the bug.
On the $i$-th test, she changes one character of the string $S_j$ to any direction U, L, D, R and asks you to walk according to the string of directions.
Changes on the string carry to future tests.
The delay of the prototype is the maximum possible Manhattan distance between $(x_d, y_d)$ and your actual position $(x_i, y_i)$.
She would like to figure out this delay and asks you to do so.

As a contestant about to take the TFT, you think this is absolutely stupid and a waste of your time.
Instead of walking, you would like to provide the answers of her $Q$ tests without doing so.

Input

The first line contains two integers $N$ and $Q$.
The next line contains a string $S$ of length $N$ denoting the string of directions.
The next $Q$ lines have an integer $A_i$ and a character $c$, updating $S_{A_i}$ to be $c$.

Output

Output $Q$ lines with one integer each, the answer to her test.

Constraints

For all subtasks:
$1\leq N, Q \leq 10^5$
$1\leq A_i \leq N$
$S_i, c$ is one of U, L, D, R

Subtask 1 (11%): $1\leq N, Q\leq 100$
Subtask 2 (24%): $1\leq N, Q\leq 2000$, $S_i, c$ is one of L, R
Subtask 3 (25%): $S_i, c$ is one of L, R
Subtask 4 (22%): $1\leq N, Q\leq 2000$
Subtask 5 (18%): No additional constraints