output_description: Print the answer.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      N Q
      s
      t_1 d_1
      \vdots
      t_{Q} d_Q
attempt: #!/usr/bin/python3
  N, Q = [int(x) for x in input().split()]
  S = input()
  
  qs = []
  for _ in range(Q):
      t, d = [x for x in input().split()]
      # print(t, d)
      qs.append((t, -1 if d == "L" else 1))
  
  memo = [None] * N
  memo.append(N)
  
  
  def move(i):
      org = i
      if memo[i]:
          return memo[i]
      for t, d in qs:
          if S[i] == t:
              i += d
          if i == -1:
              break
          elif i == N:
              break
      memo[org] = i
      return i
  
  
  def search_right(lo, hi, x):
      while lo < hi:
          mid = lo + (hi - lo) // 2
          if x < move(mid):
              hi = mid
          else:  # e <= t
              lo = mid + 1
      return lo
  
  
  def search_left(lo, hi, x):
      while lo < hi:
          mid = lo + (hi - lo) // 2
          if move(mid) < x:
              lo = mid + 1
          else:  # e <= t
              hi = mid
      return lo
  
  
  # l = search(0, N-1, -1)
  # assert move(l) == 2, "%d" % move(l)
  # print("search(-1)=", l)
  
  l = search_right(0, N - 1, -1)
  r = search_left(0, N, N)
  
  if 1 == 0:
      print(S)
      for t, d in qs:
          print(t, {-1: "L", 1: "R"}[d])
      m = [move(i) for i in range(N + 1)]
      print(" ".join("%2d" % i for i in range(N + 1)))
      print(" ".join("%+d" % x for x in m))
      print(" ".join(" *" if l == i else "  " for i in range(N + 1)))
      print(" ".join(" *" if r == i else "  " for i in range(N + 1)))
  
  print(r - l)
  
problem_description: Statement
  
  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.
samples: [{"input": "3 4\n    ABC\n    A L\n    B L\n    B R\n    A R", "output": "2\n    \n\n  * Initially, there is one golem on each square.\n  * In the first spell, the golem on Square 1 tries to move left and disappears.\n  * In the second spell, the golem on Square 2 moves left.\n  * In the third spell, no golem moves.\n  * In the fourth spell, the golem on Square 1 moves right.\n  * After the four spells are cast, there is one golem on Square 2 and one golem on Square 3, for a total of two golems remaining.\n\n* * *"}, {"input": "8 3\n    AABCBDBA\n    A L\n    B R\n    A R", "output": "5\n    \n\n  * After the three spells are cast, there is one golem on Square 2, two golems on Square 4 and two golems on Square 6, for a total of five golems remaining.\n  * Note that a single spell may move multiple golems.\n\n* * *"}, {"input": "10 15\n    SNCZWRCEWB\n    B R\n    R R\n    E R\n    W R\n    Z L\n    S R\n    Q L\n    W L\n    B R\n    C L\n    A L\n    N L\n    E R\n    Z L\n    S L", "output": "3"}]