There are N squares numbered 1 to N from left to right. Each square has a character written on it, and Square i has a letter s_i. Besides, there is initially one golem on each square.

Snuke cast Q spells to move the golems.

The i-th spell consisted of two characters t_i and d_i, where d_i is `L` or `R`. When Snuke cast this spell, for each square with the character t_i, all golems on that square moved to the square adjacent to the left if d_i is `L`, and moved to the square adjacent to the right if d_i is `R`.

However, when a golem tried to move left from Square 1 or move right from Square N, it disappeared.

Find the number of golems remaining after Snuke cast the Q spells.

Constraints

* 1 \leq N,Q \leq 2 \times 10^{5}
* |s| = N
* s_i and t_i are uppercase English letters.
* d_i is `L` or `R`.

Input

Input is given from Standard Input in the following format:


N Q
s
t_1 d_1
\vdots
t_{Q} d_Q


Output

Print the answer.

Examples

Input

3 4
ABC
A L
B L
B R
A R


Output

2


Input

8 3
AABCBDBA
A L
B R
A R


Output

5


Input

10 15
SNCZWRCEWB
B R
R R
E R
W R
Z L
S R
Q L
W L
B R
C L
A L
N L
E R
Z L
S L


Output

3
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
 
public class Main {
    static int[] query;
    static boolean[] isl;
    static String s;
    static int N;
    public static void main(String args[]) throws Exception{
        BufferedReader stdR = new BufferedReader(new InputStreamReader(System.in));
        String[] tmps = stdR.readLine().split(" ");
        N = Integer.parseInt(tmps[0]);
        int Q = Integer.parseInt(tmps[1]);
        s = stdR.readLine();
        query = new int[Q];
        isl = new boolean[Q];
        for(int i = 0 ; i < Q ; i++) {
            tmps = stdR.readLine().split(" ");
            int place = (int)(tmps[0].toCharArray()[0] - 65);
            query[i] = place;
            if(tmps[1].toCharArray()[0] == 'L') {
                isl[i] = true;
            }else {
                isl[i] = false;
            }
        }
        String[] kouho  = binaryLeftSearch().split(",");
        int[] left = new int[2];
        boolean[] leftbroken = new boolean[2];
        left[0] = Integer.parseInt(kouho[0]);
        left[1] = Integer.parseInt(kouho[1]);
        Arrays.sort(left);
        kouho  = binaryRightSearch().split(",");
        int[] right = new int[2];
        boolean[] rightbroken = new boolean[2];
        right[0] = Integer.parseInt(kouho[0]);
        right[1] = Integer.parseInt(kouho[1]);
        Arrays.sort(right);
        for(int i = 0 ; i < 2 ; i++) {
            if(left[i] >= 0 && left[i] < N && isbroken(left[i], true))leftbroken[i] = true;
            if(right[i] >= 0 && right[i] < N && isbroken(right[i], false))rightbroken[i] = true;
        }
        int leftmost = -1;
        if(leftbroken[1]) {
            leftmost = left[1];
        }else if(leftbroken[0]) {
            leftmost = left[0];
        }
        
        int rightmost = N;
        if(rightbroken[0]) {
            rightmost = right[0];
        }else if(rightbroken[1]) {
            rightmost = right[1];
        }
        
        if(leftmost >= rightmost) {
            System.out.println(0);
        }else {
            System.out.println(N - ((leftmost + 1) + (N - rightmost)));
        }
    }
    
    public static boolean isbroken(int index, boolean leftbroken) {
        for(int i = 0 ; i < query.length ; i++) {
            //System.out.println(i+","+index);
            //System.out.println(query[i]+","+(int)(s.charAt(index) - 65));
            if(query[i] == (int)(s.charAt(index) - 65)) {
                if(isl[i]) {
                    index--;
                    if(index < 0) {
                        if(leftbroken)return true;
                        return false;
                    }
                }else {
                    index++;
                    if(index == s.length()) {
                        if(!leftbroken)return true;
                        return false;
                    }
                }
            }
        }
        return false;
    }
    
    public static String binaryLeftSearch() {
        int lower = 0; // 下限
        int upper = N - 1; // 上限
        while (lower <= upper) {
            int mid = (lower + upper) / 2;
            //System.out.println(lower+","+upper+","+mid);
            if (isbroken(mid, true)) {
                lower = mid + 1;
            } else {
                upper = mid - 1;
            }
        }
        return lower+","+upper;
    }
    
    public static String binaryRightSearch() {
        int lower = 0; // 下限
        int upper = N - 1; // 上限
        while (lower <= upper) {
            int mid = (lower + upper) / 2;
            if (isbroken(mid, false)) {
                upper = mid - 1;
            } else {
                lower = mid + 1;
            }
        }
        return lower+","+upper;
    }
}