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.List;
import java.util.Scanner;
import java.util.function.Function;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class Main {
    public static void main(String[] args) {
        final Scanner scanner = new Scanner(System.in);
        final int n = scanner.nextInt();
        final int q = scanner.nextInt();
        final String s = scanner.next();

        final List<Query> queries = IntStream.range(0, q)
            .mapToObj(i -> new Query(scanner.next().charAt(0), scanner.next().charAt(0) == 'L' ? -1 : 1))
            .collect(Collectors.toList());

        final Function<Integer, SimulationResult> simulate = current -> {
            for (final Query query : queries) {
                if (s.charAt(current) != query.symbol) {
                    continue;
                }

                if (current == 0 && query.direction == -1) {
                    return SimulationResult.LEFT_FALL;
                } else if (current == s.length() - 1 && query.direction == 1) {
                    return SimulationResult.RIGHT_FALL;
                }

                current += query.direction;
            }

            return SimulationResult.REMAIN;
        };

        if (simulate.apply(n - 1) == SimulationResult.LEFT_FALL || simulate.apply(0) == SimulationResult.RIGHT_FALL) {
            System.out.println(0);
            return;
        }

        final int mostLeft = simulate.apply(0) == SimulationResult.LEFT_FALL ? binarySearchLeft(0, n - 1, simulate) : 0;
        final int mostRight = simulate.apply(n - 1) == SimulationResult.RIGHT_FALL ? binarySearchRight(0, n - 1, simulate) : n;
        if (mostLeft >= mostRight) {
            System.out.println(0);
        } else {
            System.out.println(mostRight - mostLeft);
        }
    }

    private static int binarySearchLeft(final int begin, final int end, final Function<Integer, SimulationResult> simulate) {
        if (end - begin <= 1) {
            return end;
        }
        final int mid = (begin + end) / 2;
        final SimulationResult result = simulate.apply(mid);
        if (result == SimulationResult.LEFT_FALL) {
            return binarySearchLeft(mid, end, simulate);
        } else {
            return binarySearchLeft(begin, mid, simulate);
        }
    }

    private static int binarySearchRight(final int begin, final int end, final Function<Integer, SimulationResult> simulate) {
        if (end - begin <= 1) {
            return end;
        }
        final int mid = (begin + end) / 2;
        final SimulationResult result = simulate.apply(mid);
        if (result == SimulationResult.RIGHT_FALL) {
            return binarySearchRight(begin, mid, simulate);
        } else {
            return binarySearchRight(mid, end, simulate);
        }
    }

    private enum SimulationResult {
        LEFT_FALL, RIGHT_FALL, REMAIN
    }

    private static class Query {
        final char symbol;
        final int direction;

        Query(final char symbol, final int direction) {
            this.symbol = symbol;
            this.direction = direction;
        }
    }
}
