405479: GYM101972 E Stupid Submissions

Abed is so motivated this year, his goal is qualifying for the 2019 ACM International Collegiate Programming Contest (ACM ICPC). Therefore, he always trains using Codeforces online judge. If you do not know Codeforces, the following rules can help you to understand how it works:

• Each problem has a set of n tests numbered from 1 to n. The first k tests are called sample tests. These tests are visible in the problem statement and a user can see them all.
• When Abed gets a wrong answer on test x (x ≤ n), he can see all the tests up to test number x. If Abed gets accepted, he can see all the tests.
• Each test can be either small or big. Abed can see the entire test only if it is small. If the test is big, Abed can see it partially. All the sample tests are small.

For example, let us consider a problem contains 6 tests, in which the first two tests are the sample tests. If Abed got a wrong answer on test 4, a wrong answer on test 3, and a wrong answer on test 5, he can see all tests from 1 to 5. If test 3 is small and the tests from 4 to 6 are big, Abed can see the first three tests fully, but he cannot fully see the remaining tests.

Unfortunately, Abed usually gets a lot of wrong answers. A submission made by Abed is called stupid if he got a wrong answer on a small test that he can see it fully. You are given a list of submissions made be Abed, your task is to count how many stupid submission Abed has made. Can you?

The first line contains an integer T (1 ≤ T ≤ 100) specifying the number of test cases.

The first line of each test case contains three integers n, m, and k (1 ≤ k ≤ n ≤ 10⁴, 1 ≤ m ≤ 10⁴), in which n is the number of tests in the problem, m is the number of submissions Abed has made, and k is the number of sample tests. Then a line follow contains n characters t₁, ..., t_n, in which t_i is 'S' if the i^th test is small, and 'B' if it is big.

Then m lines follow, giving the list of submissions Abed has made, such that the i^th line will either contain a single character 'A' if Abed got accepted on the i^th submission, or contain a character 'W' and an integer x (1 ≤ x ≤ n) giving that Abed got a wrong answer on test case x.

For each test case, print a single line containing the number of stupid submissions Abed has made.

2
5 4 2
S S B S B
W 3
W 4
W 4
A
4 3 2
S S B B
W 1
W 2
W 3

1
2