랜덤 다전제

문제

Alice와 Bert는 다양한 보드 게임을 순서대로 플레이하는 다전제 (이를테면 5판 3선승 혹은 7판 4선승) 게임을 즐겨하는데, 너무 자주해서 이제는 조금 특이한 "랜덤 다전제" 놀이를 하기로 했다. 우선, 두 사람은 $N$ 개의 보드 게임을 준비하는데 (편의상 $1$ 부터 $N$ 까지 번호가 붙어있다), 각자 상대방보다 잘하는 보드게임이 있어서, $i$ 번째 보드 게임의 승자는 항상 $W_i$ 로 정해져 있다고 가정하자 ($W_i$는 문자열 $W$의 $i$번째 문자이며, $W_i = $A 이면 Alice의 승리, $W_i = $B 이면 Bert의 승리가 예상된다고 한다).

이를테면 $N = 13$, $W = $ABABAABBABAAB 라 하면 $W_1 = $A 이므로 1번 보드 게임을 하면 Alice가 이길 것이 예상된다.

다음으로 두 사람은 $M$개의 랜덤 다전제를 정하는데 $j$ 번째 다전제는 두 개의 정수 $(s_j, g_j)$ 로 표현한다 (이 때 $g_j$는 언제나 홀수이다):

이 다전제는 최대 $g_j$판의 게임이며, $s_j$ 번 보드게임부터 $(s_j + g_j-1)$ 번 보드게임까지 순서대로 플레이하여 먼저 $(g_j + 1)/2$ 승을 올리는 사람이 다전제의 승자가 된다.
이 때 $N$ 번째 보드게임을 플레이 한 후 더 게임을 진행해야 하면 $1$ 번째 보드게임부터 순서대로 플레이하면 된다.
$g_j$번째 게임을 하기 전에 승자가 가려질 경우 나머지 게임은 플레이 하지 않기로 하며, 따라서 승자가 가려지기까지 최소 $(g_j + 1)/2$번 최대 $g_j$ 번의 게임을 플레이하게 된다. $j$ 번째 다전제에서 두 사람이 플레이 하는 게임의 수를 $A_j$ 라 하자.

예를 들어 $M = 5$ 이고 $s = [1, 3, 11, 12, 13]$ 그리고 $g = [5, 7, 5, 5, 5]$ 라 하자.

첫 번째 다전제는 $(s, g) = (1, 5)$ 이므로 5판 3선승인데, $W_1 = W_3 = W_5 = $A 이므로 5번째 게임을 마친 후 Alice가 최종 승자가 된다. 이 때 $A_1 = 5$ 이다.
두 번째 다전제는 $(s, g) = (3, 7)$ 이므로 7판 4선승인데, Alice가 3번, 5번, 6번, 9번 보드 게임을 이기며 승자가 된다. 이 때 $A_2 = 7$ 이다.
세 번째 다전제는 $(s, g) = (11, 5)$ 이므로 5판 3선승인데, Alice가 11번, 12번 보드 게임을 먼저 이겨 2승을 챙기고, 13번 보드 게임은 Bert가 이긴다. 이후 14번 보드 게임이 없으므로 1번부터 다시 시작하며, Alice가 3번째 승을 챙기며 승자가 된다. 이 때 총 4개의 보드 게임을 플레이 하므로 $A_3 = 4$ 이다.
네 번째 다전제는 $(s, g) = (12, 5)$ 이므로 5판 3선승인데, Alice가 12번, 1번, 3번 보드 게임을 승리하여 3승을 챙긴다. $A_4 = 5$ 이다.
다섯 번째 다전제는 $(s, g) = (13, 5)$ 이므로 5판 3선승인데, Bert 가 13번, 2번 4번 게임을 승리하여 3승을 챙긴다. $A_5 = 5$ 이다.

입력으로 $N, M, W$ 그리고 $s, g$ 배열이 주어졌을 때 $\sum_{j=1}^{M} A_j$ 의 값을 구해보자. 위 예제의 경우 $A = [5, 7, 4, 5, 5]$ 임을 알 수 있으며 따라서 이 경우 정답은 26이다.

입력

입력 첫 줄에 테스트 케이스의 수 $T$ 가 주어진다.

각 테스트 케이스의 첫 줄에는 $N, M$ 이 공백으로 구분되어 주어진다. 둘째 줄에는 A 와 B로만 구성된 길이 $N$인 문자열 $W$가 공백없이 주어진다. 다음 $M$ 줄에 걸쳐서 순서대로 $j$ 번째 랜덤 다전제를 표현하는 두 정수 $(s_j, g_j)$ 가 공백으로 구분되어 주어진다 ($1 \le j \le M$).

출력

각 테스트 케이스의 정답인 $\sum_{j=1}^{M} A_j$ 를 각 줄에 출력한다.

제한

$1 \le T \le 10$
$1 \le N, M \le 250\,000$
$1 \le i \le N$ 인 $i$에 대하여: $W_i = $A 혹은 $W_i = $B
$1 \le j \le M$ 인 $j$에 대하여:
- $1 \le s_j \le N$
- $1 \le g_j \le N$ 이며 $g_j$ 는 언제나 홀수이다