20554번 - 경로 수정하기

문제

오른쪽으로 갈수록 $x$좌표가 증가하고, 위쪽으로 갈수록 $y$좌표가 증가하는 일반적인 좌표평면 상의 $(0,0)$에 사는 석표는 $(X,Y)$에 있는 준호의 집으로 가려고 한다. 석표는 1초마다 수평 또는 수직 방향으로 1만큼 이동하는데, 석표의 이동 계획을 정리한 길이 $N$의 문자열을 $S$라고 한다. $S$의 $i$번째 문자가 L, R, D, U인지에 따라 석표는 각각 왼쪽, 오른쪽, 아래쪽, 위쪽으로 1만큼 이동한다.

덜렁이인 석표가 세운 이동 계획은 정확하지 않을 수 있다. 이동 계획이 정확하다는 것은 모든 이동을 완료한 후 석표가 $(X,Y)$에 있다는 것을 의미한다. 중간에 $(X,Y)$를 도달했어도 마지막에 $(X,Y)$에 있지 않는다면 정확한 이동 계획이 아니다.

석표는 $S$의 한 문자를 다른 문자로 수정하는 것을 반복해, 정확한 이동 계획으로 바꾸려고 한다. 석표는 힘들게 4ドル^N$가지 경우를 모두 따져서 필요한 최소 수정 횟수를 구했다. 그런데 슬프게도 준호가 이사를 갔다는 소식이 전해졌다. 준호는 $Q$개의 위치 중 하나로 이동했다고 한다. $i$번째 위치는 $(X_i,Y_i)$이다. 이제 석표는 $Q$개의 위치 각각에 대해 필요한 최소 수정 횟수를 구해야 한다.

석표는 $Q$번 최소 수정 횟수를 구해야 한다는 사실에 그만 정신을 잃고 말았다. 석표를 위해 대신 답을 구해주자.

입력

첫 줄에 $N$과 $Q$가 공백으로 구분되어 주어진다. $(1 \leq N,Q \leq 300,000円)$

다음 줄에 $S$가 주어진다.

이후 $Q$개의 줄에 걸쳐 $X_i$와 $Y_i$가 공백으로 구분되어 주어진다. $(|X_i|,|Y_i| \leq 300,000円)$

출력

각 위치에 대해 정확한 이동 계획으로 바꾸는 것이 불가능하다면 -1을, 그렇지 않다면 필요한 최소 수정 횟수를 줄바꿈으로 구분하여 출력한다.

제한

힌트