34938번 - 루프

문제

주어진 명령어 시퀀스를 무한히 반복하는 로봇이 있다. 명령어 시퀀스의 각 문자는 세 종류로, L이면 방향을 왼쪽으로 90도 회전, R이면 방향을 오른쪽으로 90도 회전, U면 앞으로 한 칸 이동한다.

길이 $N$의 초기 명령어 시퀀스와, 시퀀스에서 $i$번째 문자를 $x$로 바꾸는 업데이트 $Q$개가 주어진다. 로봇의 명령어 중 최소 몇 개를 수정해야 로봇이 제자리에서 멈춰 있거나 무한히 같은 경로를 반복하여 이동하도록 만들 수 있는지 출력하라.

입력

첫 번째 줄에 정수 $N,ドル $Q$가 차례대로 주어진다. (1ドル \le N \le 3000; 1 \le Q \le 100,000円$)

두 번째 줄에 길이 $N$의 명령어 시퀀스 문자열이 주어진다. (각 문자는 L, R, U 중 하나)

세 번째 줄부터 $Q$개의 줄에 걸쳐 각 줄마다 업데이트를 의미하는 정수 $i$와 명령어 문자 $x$가 순서대로 주어진다. (1ドル \le i \le N;$ $x$는 L, R, U 중 하나)

출력

$i$번째 줄에 1ドル$번째 업데이트부터 $i$번째 업데이트까지 적용된 명령어 시퀀스에 대한 답을 총 $Q$개의 줄에 걸쳐 출력한다. 불가능한 경우에 대해서는 답 대신 $-1$을 출력한다.

제한

노트