랜덤 다전제

Alice와 Bert는 다양한 보드 게임을 순서대로 플레이하는 다전제 (이를테면 5판 3선승 혹은 7판 4선승) 게임을 자주 한다. 너무 자주 하다 보니 이제는 조금 특이한 "랜덤 다전제" 놀이를 하기로 했다. 먼저 두 사람은 $N$개의 보드 게임을 준비하고, 편의상 1번부터 $N$번까지 번호를 붙인다. 두 사람은 각자 상대보다 잘하는 보드 게임이 있어서, $i$번째 보드 게임의 승자는 항상 $W_i$로 정해져 있다고 가정한다. ($W_i$는 문자열 $W$의 $i$번째 문자이며, $W_i$가 A이면 Alice의 승리, 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 또는 B이다.
• $1 \le j \le M$인 모든 $j$에 대하여:
  • $1 \le s_j \le N$
  • $1 \le g_j \le N$이며, $g_j$는 항상 홀수이다.