원을 따라 달리기

Ada는 올해 자신의 도시에서 열리는 연례 마라톤에 참가하기로 했다. 이렇게 긴 거리를 달리는 것은 처음이므로, 집 근처에 있는 길이 $\mathbf{L}$단위의 원형 트랙에서 달리며 연습을 시작하기로 했다.

Ada는 달리기에만 집중하고 싶어서, 자신이 달린 바퀴 수를 기계로 세기로 한다. 기계는 원형 트랙의 출발선에 설치되어 있으며 $0$부터 세기 시작한다. Ada가 마지막으로 출발선에서 출발했을 때와 같은 방향으로 달리면서 출발선에 도착할 때마다 기계는 Ada가 달린 바퀴 수를 $1$만큼 늘린다. Ada가 출발선을 통과하거나 출발선에서 방향을 바꾸면, 기계는 새로운 방향을 Ada가 마지막으로 출발선에 닿은 방향으로 간주한다. 기계는 Ada가 출발선에 닿은 마지막 방향만 기억한다. 한 바퀴를 도는 동안 Ada는 몇 번이든 방향을 바꿀 수 있지만, 결국 마지막으로 출발선에 닿았던 방향과 같은 방향으로 출발선에 닿기만 하면 기계의 바퀴 수가 $1$만큼 증가한다.

Ada가 장거리를 달리는 연습을 하는 것은 처음이므로 계속해서 달릴 수는 없다. 어느 정도 거리를 달린 뒤에는 기력을 회복하기 위해 휴식을 취한다. 하지만 휴식을 마치고 다시 달리기 시작할 때는 이전에 어느 방향으로 달리고 있었는지 기억하지 못한다. 따라서 시계 방향 또는 반시계 방향 중 하나를 선택하고 멈췄던 바로 그 위치에서 달리기 시작한다.

Ada는 출발선에서 시작하며 처음에는 첫 달리기의 방향을 바라보고 있다. 중간중간 휴식하면서 총 $\mathbf{N}$번 달린다. $1, \dots, \mathbf{N}$부터의 모든 $i$에 대해, Ada가 $i$번째로 달렸을 때 달린 거리 $\mathbf{D_i}$단위와 선택한 방향 $\mathbf{C_i}$(시계 방향 또는 반시계 방향)에 대한 정보가 주어질 때, 마지막에 기계가 보고할 바퀴 수를 구한다.

제한

메모리 제한: 1 GB. $1 \le \mathbf{T} \le 100$. $1 \le \mathbf{L} \le 10^9$. $1 \le \mathbf{N} \le 10^4$. 모든 $1 \le i \le \mathbf{N}$에 대해 $1 \le \mathbf{D_i} \le 10^9$.

테스트 세트 1

시간 제한: 20초. 모든 $1 \le i \le \mathbf{N}$에 대해 $\mathbf{C_i}$는 항상 'C'이다.

테스트 세트 2

시간 제한: 40초. 모든 $1 \le i \le \mathbf{N}$에 대해 $\mathbf{C_i}$는 'C' 또는 'A'일 수 있다.

입력의 첫째 줄에 테스트 케이스의 수 $\mathbf{T}$가 주어진다. 이어서 $\mathbf{T}$개의 테스트 케이스가 주어진다. 각 테스트 케이스의 첫째 줄에는 원형 트랙의 길이(단위)와 Ada가 달린 횟수를 각각 나타내는 두 양의 정수 $\mathbf{L}$과 $\mathbf{N}$이 주어진다. 다음 $\mathbf{N}$개 줄에는 Ada의 달리기에 대한 정보가 주어진다. $i$번째 줄에는 양의 정수 $\mathbf{D_i}$와 문자 $\mathbf{C_i}$가 주어지며, 각각 $i$번째 달리기에서 Ada가 달린 거리(단위)와 선택한 방향(시계 방향 또는 반시계 방향)을 나타낸다. $\mathbf{C_i}$는 항상 시계 방향을 나타내는 'C' 또는 반시계 방향을 나타내는 'A' 중 하나이다.

각 테스트 케이스마다 Case #$x$: $y$를 포함하는 한 줄을 출력한다. 여기서 $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 마지막에 기계가 보고하는 바퀴 수를 나타내는 음이 아닌 정수이다.

예제 케이스 #1에서 원형 트랙의 길이는 $5$단위이다. 처음에 Ada는 시계 방향을 바라보고 있다.

• 먼저 Ada는 시계 방향으로 $8$단위를 달리며 그 과정에서 출발선에 닿고, 기계의 바퀴 수는 $1$만큼 증가한다. 이제 기계는 $1$바퀴를 보고한다. 이제 Ada는 시계 방향으로 출발선에서 $3$단위 떨어져 있다.

• 다음으로 시계 방향으로 $3$단위를 달린다. 이번에도 출발선에 닿고 기계의 바퀴 수는 $1$만큼 증가한다. 이제 기계는 $2$바퀴를 보고한다. 그 후에는 시계 방향으로 출발선에서 $1$단위 떨어져 있다.

• 마지막으로 시계 방향으로 $6$단위를 달리고 다시 출발선에 닿아 기계의 바퀴 수가 $1$만큼 증가한다. 마지막에 기계는 $3$바퀴를 보고한다.

예제 케이스 #2에서 원형 트랙의 길이는 $8$단위이다. 처음에 Ada는 시계 방향을 바라보고 있다.

• 먼저 Ada는 시계 방향으로 $5$단위를 달린다. 이제 Ada는 시계 방향으로 출발선에서 $5$단위 떨어져 있다.

• 다음으로 시계 방향으로 $9$단위를 달리며 출발선에 닿는다. 기계의 바퀴 수는 $1$만큼 증가한다. 이제 기계는 $1$바퀴를 보고한다. 그 후에는 시계 방향으로 출발선에서 $6$단위 떨어져 있다.

• 다음으로 시계 방향으로 $8$단위를 달린다. 다시 출발선에 닿아 기계의 바퀴 수가 $1$만큼 증가한다. 이제 기계는 $2$바퀴를 보고한다. 그 후에는 시계 방향으로 출발선에서 $6$단위 떨어져 있다.

• 마지막으로 시계 방향으로 $20$단위를 달린다. 이번에는 출발선에 총 $3$번 닿아 기계의 바퀴 수가 $3$만큼 증가한다. 마지막에 기계는 $5$바퀴를 보고한다.

추가 예제 - 테스트 세트 2

예제 케이스 #1에서 원형 트랙의 길이는 $5$단위이다. 처음에 Ada는 시계 방향을 바라보고 있다.

• 먼저 Ada는 시계 방향으로 $8$단위를 달리며 그 과정에서 출발선에 닿고, 기계의 바퀴 수는 $1$만큼 증가한다. 이제 기계는 $1$바퀴를 보고한다. 이제 Ada는 시계 방향으로 출발선에서 $3$단위 떨어져 있다.

• 다음으로 반시계 방향으로 $4$단위를 달린다. 출발선에 닿지만 이전에 달리던 방향과 반대 방향으로 달리며 닿았으므로 기계의 바퀴 수는 증가하지 않는다. 이제 반시계 방향으로 출발선에서 $1$단위 떨어져 있다.

• 마지막으로 시계 방향으로 $5$단위를 달린다. 이번에도 출발선에 닿지만 마지막으로 출발선에 닿은 방향이 반시계 방향이었으므로 기계는 이를 세지 않는다. 이후 다시 출발선에 닿지 않으며, 마지막에 기계는 $1$바퀴를 보고한다.

예제 케이스 #2에서 원형 트랙의 길이는 $4$단위이다. 처음에 Ada는 시계 방향을 바라보고 있다.

• 먼저 Ada는 시계 방향으로 $2$단위를 달린다. 이제 Ada는 시계 방향으로 출발선에서 $2$단위 떨어져 있다.

• 다음으로 반시계 방향으로 $8$단위를 달린다. 출발선에 닿지만 이전에 달리던 방향과 반대 방향으로 달리며 닿았으므로 기계의 바퀴 수는 증가하지 않는다. 이어서 계속 달려 결국 다시 출발선에 닿는다. 이번에는 기계가 보고하는 바퀴 수가 $1$만큼 증가한다. 이제 기계는 $1$바퀴를 보고한다. 이 달리기가 끝난 뒤에는 반시계 방향으로 출발선에서 $2$단위 떨어져 있다.

• 다음으로 반시계 방향으로 $3$단위를 달린다. 출발선에 닿고 기계의 바퀴 수가 $1$만큼 증가한다. 이제 기계는 $2$바퀴를 보고한다. 이 달리기가 끝난 뒤에는 반시계 방향으로 출발선에서 $1$단위 떨어져 있다.

• 다음으로 시계 방향으로 $5$단위를 달린다. 출발선에 닿지만 기계는 이를 세지 않는다. 계속 달린 뒤 달리기가 끝날 때 출발선에 닿아 기계의 바퀴 수가 $1$만큼 증가한다. 이제 기계는 $3$바퀴를 보고한다. 이 달리기가 끝난 뒤에는 출발선에서 시계 방향을 바라보고 있다.

• 마지막으로 반시계 방향으로 $8$단위를 달린다. 이 달리기를 시작할 때 출발선에서 방향을 바꾸므로, 이제 기계는 새로운 방향인 반시계 방향을 마지막으로 출발선에 닿은 방향으로 간주한다. 계속 달리며 반시계 방향으로 출발선에 두 번 닿아 기계의 바퀴 수가 $2$만큼 증가한다. 마지막에 기계는 $5$바퀴를 보고한다.

예제 케이스 #3에서 원형 트랙의 길이는 $4$단위이다. 처음에 Ada는 시계 방향을 바라보고 있다.

• 먼저 Ada는 시계 방향으로 $3$단위를 달린다. 그 후에는 시계 방향으로 출발선에서 $3$단위 떨어져 있다.

• 다음으로 반시계 방향으로 $2$단위를 달린다. 이 달리기 중에는 출발선에 닿지 않으므로 기계는 여전히 시계 방향을 마지막 방향으로 간주한다. 이 달리기가 끝난 뒤에는 시계 방향으로 출발선에서 $1$단위 떨어져 있다.

• 마지막으로 시계 방향으로 $5$단위를 달린다. 마지막으로 출발선에서 출발했을 때와 같은 시계 방향으로 달리며 출발선을 한 번 통과하고, 기계의 바퀴 수가 $1$만큼 증가한다. 마지막에 기계는 $1$바퀴를 보고한다.