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.util.*;

class Main {

	static int N;
	static int Q;
	static char[] d;
	static char[] t;
	static String s;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		Q = sc.nextInt();
		s = sc.next();
		t = new char[Q];
		d = new char[Q];
		for (int i=0;i<Q;i++) {
			t[i]=sc.next().charAt(0);
			d[i]=sc.next().charAt(0);
		}
		int left_edge=0;
		int right_edge=N-1;

		int left = 0;
		int right = N-1;
		do {
			if (test(N-1)=='A') {
				right_edge=N;
				break;
			}
			int center = (left + right) / 2;
			if (center==0) {
				if (test(center)=='R') {
					right_edge=center+1;
					break;
				} else if (test(center)=='A' || test(center)=='L'){
					left = center + 1;
				} else {
					right = center - 1;
				}
			}
			if (test(center)=='R' && (test(center-1)=='A' || test(center-1)=='L')) {
				right_edge=center;
				break;
			} else if (test(center)=='A' || test(center)=='L'){
				left = center + 1;
			} else {
				right = center - 1;
			}
		} while (left <= right);

		left = 0;
		right = N-1;
		do {
			if (test(0)=='A') {
				left_edge=-1;
				break;
			}
			int center = (left + right) / 2;
			if (center==N-1) {
				if (test(center)=='L') {
					left_edge=center-1;
					break;
				} else if (test(center)=='A' || test(center)=='R'){
					right = center - 1;
				} else {
					left = center + 1;
				}
			}
			if (test(center)=='L' && (test(center+1)=='A' || test(center+1)=='R')) {
				left_edge=center;
				break;
			} else if (test(center)=='A' || test(center)=='R'){
				right = center - 1;
			} else {
				left = center + 1;
			}
		} while (left <= right);
		System.out.println(right_edge-left_edge-1);
	}

	static char test(int n) {
		int tmp = n;
		for (int i=0;i<Q;i++) {
			if (s.charAt(tmp)==t[i]) {
				if (d[i]=='R') {
					tmp++;
				} else if (d[i]=='L') {
					tmp--;
				}
			}
			if (tmp<0) {
				return 'L';
			}else if(tmp>N-1) {
				return 'R';
			}
		}
		return 'A';
	}
}