Fixing the Path

Seokpyo lives at $(0,0)$ on an ordinary coordinate plane where the $x$-coordinate increases to the right and the $y$-coordinate increases upward. He wants to go to Junho's house at $(X,Y)$. Every second Seokpyo moves 1 unit horizontally or vertically, and the string $S$ of length $N$ describes his movement plan. Depending on whether the $i$-th character of $S$ is L, R, D, U, Seokpyo moves 1 unit left, right, down, or up, respectively.

The movement plan made by the careless Seokpyo may not be correct. A movement plan is correct if Seokpyo is at $(X,Y)$ after completing all the moves. Even if he reaches $(X,Y)$ in the middle, the plan is not correct unless he is at $(X,Y)$ at the end.

Seokpyo repeatedly changes one character of $S$ to another character to turn it into a correct movement plan. He went through all $4^N$ cases the hard way and found the minimum number of changes needed. But sadly, news arrived that Junho has moved. Junho has moved to one of $Q$ locations. The $i$-th location is $(X_i,Y_i)$. Now Seokpyo must find the minimum number of changes needed for each of the $Q$ locations.

Seokpyo fainted on hearing that he must find the minimum number of changes $Q$ times. Let us find the answers for him.

The first line contains $N$ and $Q$ separated by a space. $(1 \leq N,Q \leq 300\,000)$

The next line contains $S$.

The following $Q$ lines contain $X_i$ and $Y_i$ separated by a space. $(|X_i|,|Y_i| \leq 300\,000)$

For each location, output -1 if it is impossible to turn the plan into a correct movement plan, or the minimum number of changes needed otherwise, each on its own line.