Given a string of length n s = s1, s2,…, sn and m queries. Each query qk (1 ≤ k ≤ m) is one of four types, "L ++", "L-", "R ++", "R-", and l [for the kth query qk. k] and r [k] are defined below.

* L ++: l [k] = l [k-1] + 1, r [k] = r [k-1]

* L-: l [k] = l [k-1] -1, r [k] = r [k-1]

* R ++: l [k] = l [k-1], r [k] = r [k-1] +1

* R-: l [k] = l [k-1], r [k] = r [k-1] -1




However, l [0] = r [0] = 1.

At this time, how many kinds of character strings are created for m substrings sl [k], sl [k] + 1,…, sr [k] -1, sr [k] (1 ≤ k ≤ m). Answer if you can.

Constraints

* The string s consists of a lowercase alphabet

* 1 ≤ n ≤ 3 x 105

* 1 ≤ m ≤ 3 × 105

* qk (1 ≤ k ≤ m) is one of "L ++", "L-", "R ++", "R-"

* 1 ≤ l [k] ≤ r [k] ≤ n (1 ≤ k ≤ m)

Input

Input is given in the following format

> n m
> s
> q1
> q2
>…
> qm
>

Output

Output the solution of the problem on one line

Examples

Input

5 4
abcde
R++
R++
L++
L--


Output

3


Input

4 6
abab
R++
L++
R++
L++
R++
L++


Output

4


Input

10 13
aacacbabac
R++
R++
L++
R++
R++
L++
L++
R++
R++
L--
L--
R--
R--


Output

11

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
def main():
	(n, m) = map(int, input().split())
	s = input()
	mem = set()
	base = ord('a') - 1
	mod1 = 1000000007
	mod2 = 2147483647
	h1 = [0]
	h2 = [0]
	for c in s:
		h1.append((h1[-1] * 27 + ord(c) - base) % mod1)
		h2.append((h2[-1] * 27 + ord(c) - base) % mod2)
	pow_mem1 = {0: 1}
	pow_mem2 = {0: 1}

	def my_pow1(x):
		if x in pow_mem1:
			return pow_mem1[x]
		pow_mem1[x] = my_pow1(x - 1) * 27 % mod1
		return pow_mem1[x]

	def my_pow2(x):
		if x in pow_mem2:
			return pow_mem2[x]
		pow_mem2[x] = my_pow2(x - 1) * 27 % mod2
		return pow_mem2[x]
	left = right = 1
	for _ in range(m):
		com = input()
		if com == 'L++':
			left += 1
		if com == 'L--':
			left -= 1
		if com == 'R++':
			right += 1
		if com == 'R--':
			right -= 1
		x = (h1[right] - h1[left - 1] * my_pow1(right - left + 1)) % mod1
		y = (h2[right] - h2[left - 1] * my_pow2(right - left + 1)) % mod2
		mem.add((x, y))
	print(len(mem))
main()


import math, string, itertools, fractions, heapq, collections, re, array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20
eps = 1.0 / 10 ** 13
mod = 10 ** 9 + 7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]

def LI():
	return [int(x) for x in sys.stdin.readline().split()]

def LI_():
	return [int(x) - 1 for x in sys.stdin.readline().split()]

def LF():
	return [float(x) for x in sys.stdin.readline().split()]

def LS():
	return sys.stdin.readline().split()

def I():
	return int(sys.stdin.readline())

def F():
	return float(sys.stdin.readline())

def S():
	return input()

def pf(s):
	return print(s, flush=True)

class ModInt:

	def __init__(self, n):
		self.n = n

	def __add__(self, x):
		x = ModInt.xn(x)
		return ModInt((self.n + x) % mod)

	def __sub__(self, x):
		x = ModInt.xn(x)
		return ModInt((self.n - x) % mod)

	def __mul__(self, x):
		x = ModInt.xn(x)
		return ModInt(self.n * x % mod)

	def __truediv__(self, x):
		x = ModInt.xn(x)
		return ModInt(self.n * pow(x, mod - 2, mod) % mod)

	@classmethod
	def xn(cls, x):
		if isinstance(x, ModInt):
			return x.n
		return x

	def __str__(self):
		return str(self.n)

def M(n):
	return ModInt(n)

class RollingHash:

	def __init__(self, s):
		self.N = n = len(s)
		a = [ord(c) for c in s]
		self.A1 = a1 = [M(a[0])]
		self.A2 = a2 = [M(a[0])]
		for c in a[1:]:
			a1.append(a1[-1] * 997 + c)
			a2.append(a2[-1] * 991 + c)

	def get(self, l, r):
		if l == 0:
			return (self.A1[r].n, self.A2[r].n)
		t1 = (self.A1[r] - self.A1[l - 1] * pow(997, r - l + 1, mod)).n
		t2 = (self.A2[r] - self.A2[l - 1] * pow(991, r - l + 1, mod)).n
		return (t1, t2)

def main():
	rr = []

	def f(n, m):
		rs = set()
		s = S()
		qa = [S() for _ in range(m)]
		l = 0
		r = 0
		rh = RollingHash(s)
		for q in qa:
			if q == 'L++':
				l += 1
			elif q == 'L--':
				l -= 1
			elif q == 'R++':
				r += 1
			else:
				r -= 1
			rs.add((l, r))
		rrs = set()
		for (l, r) in rs:
			rrs.add(rh.get(l, r))
		return len(rrs)
	while 1:
		(n, m) = LI()
		if n == 0:
			break
		rr.append(f(n, m))
		break
	return '\n'.join(map(str, rr))
print(main())


import random
(n, m) = map(int, input().split())
s = input()
base1 = 1007
mod1 = 10 ** 9 + 7
base2 = 2009
mod2 = 10 ** 9 + 9
modTank1 = [3000012541, 3000012553, 3000012563, 3000012649, 3000012683, 3000012709]
mod1 = modTank1[random.randint(0, 5)]
modTank2 = [3000014753, 3000014783, 3000014833, 3000014839, 3000014891, 3000015433]
mod2 = modTank2[random.randint(0, 5)]
hash1 = [0] * (n + 1)
power1 = [1] * (n + 1)
hash2 = [0] * (n + 1)
power2 = [1] * (n + 1)
for (i, e) in enumerate(s):
	hash1[i + 1] = (hash1[i] * base1 + ord(e)) % mod1
	power1[i + 1] = power1[i] * base1 % mod1
	hash2[i + 1] = (hash2[i] * base2 + ord(e)) % mod2
	power2[i + 1] = power2[i] * base2 % mod2
res = 0
tank1 = set()
L = 0
R = 1
for _ in range(m):
	q = input()
	if q == 'L++':
		L += 1
	elif q == 'L--':
		L -= 1
	elif q == 'R++':
		R += 1
	else:
		R -= 1
	hashData1 = (hash1[R] - hash1[L] * power1[R - L] % mod1) % mod1 * 10 ** 10 + (hash2[R] - hash2[L] * power2[R - L] % mod2) % mod2
	if hashData1 in tank1:
		res += 1
	tank1.add(hashData1)
print(len(tank1))


INF = float('inf')
MOD = 10 ** 9 + 7

def inpl():
	return list(map(int, input().split()))

class RollingHash:

	def __init__(self, s, base, mod):
		self.s = s
		self.length = length = len(s)
		self.base = base
		self.mod = mod
		self.h = h = [0] * (length + 1)
		for i in range(length):
			h[i + 1] = (h[i] * base + ord(s[i])) % mod
		self.p = p = [1] * (length + 1)
		for i in range(length):
			p[i + 1] = pow(base, i + 1, mod)

	def get(self, l, r):
		mod = self.mod
		return (self.h[r] - self.h[l] * self.p[r - l] + mod) % mod

def solve():
	(N, M) = inpl()
	S = input()
	h1 = RollingHash(S, 13, MOD)
	h2 = RollingHash(S, 17, MOD)
	(left, right) = (0, 1)
	vs = set()
	ans = 0
	for i in range(M):
		q = input()
		if q == 'R++':
			right += 1
		elif q == 'R--':
			right -= 1
		elif q == 'L++':
			left += 1
		else:
			left -= 1
		v = (h1.get(left, right), h2.get(left, right))
		if v not in vs:
			ans += 1
			vs.add(v)
	return ans
print(solve())