You're given a string $\mbox{S}$ of $N$ characters. It's known that the string consists of lowercase Latin letters. The string is generated randomly. That means that every symbol is chosen randomly and independently from others from the set {'a', 'b', ..., 'z'}. All the letters have equal probability to appear.

You're given $\mbox{Q}$ queries on this string. Each query is of the form P C, where $\mbox{P}$ is an integer between $1$ and $N$ (both inclusive) and $\mbox{C}$ is a character from the set {'a', 'b', ..., 'z'}. Both $\mbox{P}$ and $\mbox{C}$ were chosen at random and independently from other queries. 

When you have a query of the form P C you have to change the  $P^{th}$ symbol of $\mbox{S}$ to $\mbox{C}$. After every change we ask you to output the number of distinct nonempty sub-strings of $\mbox{S}$.

Input Format

The first line of input consists of two single space-separated integers $N$ and $\mbox{Q}$, the length of the string $\mbox{S}$ and the number of queries, respectively.

The second line contains string $\mbox{S}$.

The following $\mbox{Q}$ lines describe the queries in the form P C, where $\mbox{P}$ and $\mbox{C}$ are also separated with a single space.

Constraints 

$4\leq N\leq75000$ 

$4\leq Q\leq75000$ 

Output Format

Output $\mbox{Q}$ lines. Output the number of distinct substrings of $\mbox{S}$ after the $i^{th}$ query on the $i^{th}$  line of the output.

Sample Input
4 4 
aaab
1 a
2 b
3 c
4 d

Sample Output
7
7
9
10

Explanation

After replacing the character at the first index with a, we still have the original string aaab. The total non empty substrings of aaab are 

a b aa ab aaa aab aaab

hence 7. 

After replacing the character at the second index with b, we have the string abab. The non-empty substrings of abab are 

a b ab ba aba bab abab

hence 7. 

After replacing the character at the third index with c, we have the string abcb. The total non empty substrings of abcb are

a b c ab bc cb abc bcb abcb

hence 9.   

After replacing the character at the fourth index with d, we have the string abcd. The total non empty substrings of abcd are 

a b c d ab bc cd abc bcd abcd

hence 10. 

Scoring

There are 12 test cases.  

The first four test cases N = 100 and Q = 500 

The next four test cases N = 75000 and Q = 10 

The last four test cases N = 75000 and Q = 75000

Source: hackerrank | Difficulty: HARD
Tags: Probability


Solutions:
alphabet = [chr(_) for _ in range(ord('a'), ord('z') + 1)]
keys_1 = [c for c in alphabet]
keys_2 = [c1 + c2 for c1 in alphabet for c2 in keys_1]
keys_3 = [c1 + c2 for c1 in alphabet for c2 in keys_2]
keys_4 = [c1 + c2 for c1 in alphabet for c2 in keys_3]
keys_all = keys_1 + keys_2 + keys_3 + keys_4

def get_dict(depth=0):
	my_dict = {key: {'count': 0, 'all': set()} for key in keys_all}
	return my_dict

def get_map(string):
	string_len = len(string)
	char_map = get_dict()
	for i in range(string_len - 3):
		char_map[string[i]]['count'] += 1
		char_map[string[i]]['all'].add(i)
		char_map[string[i:i + 2]]['count'] += 1
		char_map[string[i:i + 2]]['all'].add(i + 1)
		char_map[string[i:i + 3]]['count'] += 1
		char_map[string[i:i + 3]]['all'].add(i + 2)
		char_map[string[i:i + 4]]['count'] += 1
		char_map[string[i:i + 4]]['all'].add(i + 3)
	char_map[string[-3]]['count'] += 1
	char_map[string[-3]]['all'].add(string_len - 3)
	char_map[string[-3:-1]]['count'] += 1
	char_map[string[-3:-1]]['all'].add(string_len - 2)
	char_map[string[-3:]]['count'] += 1
	char_map[string[-3:]]['all'].add(string_len - 1)
	char_map[string[-2]]['count'] += 1
	char_map[string[-2]]['all'].add(string_len - 2)
	char_map[string[-2:]]['count'] += 1
	char_map[string[-2:]]['all'].add(string_len - 1)
	char_map[string[-1]]['count'] += 1
	char_map[string[-1]]['all'].add(string_len - 1)
	return char_map

def update_queue_tree(queue, c, indices, s_map, s_len):
	count = 0
	followers = set((i + 1 for i in indices))
	for next_c in alphabet:
		c2 = c + next_c
		next_candidates = s_map[c2]['all'].intersection(followers)
		if len(next_candidates) == 1:
			unique_wd_cnt = s_len - next_candidates.pop()
			count += unique_wd_cnt
		elif next_candidates:
			count += 1
			queue.append((next_c, next_candidates))
	return count

def efficient_count(string, char_map):
	string_len = len(string)
	count = 0
	for c in alphabet:
		if char_map[c]['count']:
			queue = []
			if char_map[c]['count'] == 1:
				unique_wd_cnt = string_len - list(char_map[c]['all'])[0]
				count += unique_wd_cnt
				continue
			count += 1
			for next_c in alphabet:
				c2 = c + next_c
				if char_map[c2]['count'] == 1:
					unique_wd_cnt = string_len - list(char_map[c2]['all'])[0]
					count += unique_wd_cnt
				elif char_map[c2]['all']:
					count += 1
					for next_next_c in alphabet:
						c3 = c2 + next_next_c
						if char_map[c3]['count'] == 1:
							unique_wd_cnt = string_len - list(char_map[c3]['all'])[0]
							count += unique_wd_cnt
						elif char_map[c3]['all']:
							count += 1
							for next_next_next_c in alphabet:
								c4 = c3 + next_next_next_c
								if char_map[c4]['count'] == 1:
									unique_wd_cnt = string_len - list(char_map[c4]['all'])[0]
									count += unique_wd_cnt
								elif char_map[c4]['all']:
									count += 1
									queue.append((next_next_next_c, char_map[c4]['all']))
			while queue:
				(qc, c_indices) = queue.pop()
				count_inc = update_queue_tree(queue, qc, c_indices, char_map, string_len)
				count += count_inc
	return count

def count_mutation(string, string_len, char_map, char_loc):
	mutation_count = 0
	for start in range(char_loc, -1, -1):
		dup_last_char = get_longest_duplicate(string, string_len, start, char_map, char_loc)
		if dup_last_char == char_loc:
			mutation_count += (start + 1) * (len(string) - dup_last_char)
			break
		mutation_count += len(string) - dup_last_char
	return mutation_count

def get_longest_duplicate(string, string_len, start, char_map, char_loc):
	if start == string_len - 1:
		return char_loc + int(char_map[string[char_loc]]['count'] > 1)
	if char_map[string[start]]['count'] == 1:
		return char_loc
	candidates = char_map[string[start:start + 2]]['all']
	candidates_len = char_map[string[start:start + 2]]['count']
	if candidates_len == 1 or (start == char_loc and char_loc in candidates and (candidates_len == 2)):
		return max(char_loc, start + 1)
	if start + 1 == string_len - 1:
		return string_len
	candidates = char_map[string[start:start + 3]]['all']
	candidates_len = char_map[string[start:start + 3]]['count']
	if candidates_len == 1:
		return max(char_loc, start + 2)
	else:
		candidate_decr = 0
		if start == char_loc - 1:
			candidate_decr = int(char_loc in candidates)
		if start == char_loc:
			candidate_decr = int(char_loc in candidates) + int(char_loc + 1 in candidates)
		if candidates_len == 1 + candidate_decr:
			return max(char_loc, start + 2)
	if start + 2 == string_len - 1:
		return string_len
	candidates = char_map[string[start:start + 4]]['all']
	copied = False
	if start + 3 > char_loc and char_loc in candidates:
		candidates = candidates.copy()
		copied = True
		candidates.remove(char_loc)
	if start + 3 > char_loc + 1 and char_loc + 1 in candidates:
		if not copied:
			candidates = candidates.copy()
		candidates.remove(char_loc + 1)
	if start + 3 > char_loc + 2 and char_loc + 2 in candidates:
		if not copied:
			candidates = candidates.copy()
		candidates.remove(char_loc + 2)
	current_pos = start + 3
	while len(candidates) > 1:
		current_pos += 1
		if current_pos == string_len:
			break
		candidates = set((x + 1 for x in candidates))
		candidates = char_map[string[current_pos - 3:current_pos + 1]]['all'].intersection(candidates)
		if current_pos > char_loc:
			candidates.discard(char_loc)
	return char_loc if char_loc > current_pos else current_pos

def char_sub(string, s_map, pos, old_char, new_char):
	s_map[old_char]['count'] -= 1
	s_map[old_char]['all'].remove(pos)
	s_map[new_char]['count'] += 1
	s_map[new_char]['all'].add(pos)
	if pos > 0:
		p_char = string[pos - 1]
		p_char_old_1 = p_char + old_char
		p_char_new_1 = p_char + new_char
		s_map[p_char_old_1]['count'] -= 1
		s_map[p_char_old_1]['all'].remove(pos)
		s_map[p_char_new_1]['count'] += 1
		s_map[p_char_new_1]['all'].add(pos)
		if pos > 1:
			p_p_char = string[pos - 2]
			p_char_old_2 = p_p_char + p_char_old_1
			p_char_new_2 = p_p_char + p_char_new_1
			s_map[p_char_old_2]['count'] -= 1
			s_map[p_char_old_2]['all'].remove(pos)
			s_map[p_char_new_2]['count'] += 1
			s_map[p_char_new_2]['all'].add(pos)
			if pos > 2:
				p_p_p_char = string[pos - 3]
				p_char_old_3 = p_p_p_char + p_char_old_2
				p_char_new_3 = p_p_p_char + p_char_new_2
				s_map[p_char_old_3]['count'] -= 1
				s_map[p_char_old_3]['all'].remove(pos)
				s_map[p_char_new_3]['count'] += 1
				s_map[p_char_new_3]['all'].add(pos)
	if pos < len(string) - 1:
		n_char = string[pos + 1]
		n_char_old_1 = old_char + n_char
		n_char_new_1 = new_char + n_char
		s_map[n_char_old_1]['count'] -= 1
		s_map[n_char_old_1]['all'].remove(pos + 1)
		s_map[n_char_new_1]['count'] += 1
		s_map[n_char_new_1]['all'].add(pos + 1)
		if pos < len(string) - 2:
			n_n_char = string[pos + 2]
			n_char_old_2 = n_char_old_1 + n_n_char
			n_char_new_2 = n_char_new_1 + n_n_char
			s_map[n_char_old_2]['count'] -= 1
			s_map[n_char_old_2]['all'].remove(pos + 2)
			s_map[n_char_new_2]['count'] += 1
			s_map[n_char_new_2]['all'].add(pos + 2)
			if pos < len(string) - 3:
				n_n_n_char = string[pos + 3]
				n_char_old_3 = n_char_old_2 + n_n_n_char
				n_char_new_3 = n_char_new_2 + n_n_n_char
				s_map[n_char_old_3]['count'] -= 1
				s_map[n_char_old_3]['all'].remove(pos + 3)
				s_map[n_char_new_3]['count'] += 1
				s_map[n_char_new_3]['all'].add(pos + 3)
	if pos > 0 and pos < len(string) - 1:
		p_n_old = p_char + old_char + n_char
		p_n_new = p_char + new_char + n_char
		s_map[p_n_old]['count'] -= 1
		s_map[p_n_old]['all'].remove(pos + 1)
		s_map[p_n_new]['count'] += 1
		s_map[p_n_new]['all'].add(pos + 1)
		if pos < len(string) - 2:
			p_n_n_old = p_n_old + n_n_char
			p_n_n_new = p_n_new + n_n_char
			s_map[p_n_n_old]['count'] -= 1
			s_map[p_n_n_old]['all'].remove(pos + 2)
			s_map[p_n_n_new]['count'] += 1
			s_map[p_n_n_new]['all'].add(pos + 2)
		if pos > 1 and pos < len(string) - 1:
			p_p_n_old = p_p_char + p_n_old
			p_p_n_new = p_p_char + p_n_new
			s_map[p_p_n_old]['count'] -= 1
			s_map[p_p_n_old]['all'].remove(pos + 1)
			s_map[p_p_n_new]['count'] += 1
			s_map[p_p_n_new]['all'].add(pos + 1)
(N, Q) = [int(_) for _ in input().split()]
input_str = input()
input_str_len = len(input_str)
modification = []
for _ in range(Q):
	(pos, new_char) = input().split()
	modification.append((int(pos) - 1, new_char))
cmap_new = get_map(input_str)
sub_count_new = efficient_count(input_str, cmap_new)
for (pos, new_char) in modification:
	old_char = input_str[pos]
	mut_old = count_mutation(input_str, input_str_len, cmap_new, pos)
	input_str = input_str[:pos] + new_char + input_str[pos + 1:]
	char_sub(input_str, cmap_new, pos, old_char, new_char)
	mut_new = count_mutation(input_str, input_str_len, cmap_new, pos)
	sub_count_new += -mut_old + mut_new
	print(sub_count_new)


def substrings_1(S, N):
	return len({S[i:j + 1] for i in range(0, N) for j in range(i, N)})

def main_1(substrings):
	(N, Q) = map(int, input().split())
	S = input()
	for _ in range(Q):
		(P, C) = input().split()
		P = int(P)
		S = S[:P - 1] + C + S[P:]
		print(substrings(S, N))

def create_tree(S, N):
	root = [None] * 27
	for i in range(N):
		node = root
		j = i
		while isinstance(node[S[j]], list):
			node = node[S[j]]
			j += 1
		while node[S[j]] is not None:
			child = [None] * 27
			k = node[S[j]]
			child[S[k]] = k + 1
			node[S[j]] = child
			node = child
			j += 1
		node[S[j]] = j + 1
	return root

def node_repr(node):
	return '[%s]' % ' '.join(('%s:%s' % ('$' if i == 26 else chr(i + 97), node[i] if isinstance(node[i], int) else node_repr(node[i])) for i in range(27) if node[i] is not None))

def count(root, N):
	count = 0
	stack = [(root, 0)]
	while stack:
		(node, i) = stack.pop()
		if i == 26:
			continue
		if isinstance(node[i], list):
			stack.append((node, i + 1))
			stack.append((node[i], 0))
			count += 1
			continue
		if node[i] is not None:
			count += 1 + N - node[i]
		stack.append((node, i + 1))
	return count

def main_2():
	(N, Q) = map(int, input().split())
	S = bytearray((ord(c) - 97 for c in input()))
	S.append(26)
	for _ in range(Q):
		(P, C) = input().split()
		P = int(P)
		C = ord(C) - 97
		S[P - 1] = C
		root = create_tree(S, N)
		print(count(root, N))

class SuffixNode:
	__slots__ = ('parent', 'suffix', 'depth')

	def __init__(self, parent, suffix):
		self.parent = parent
		self.suffix = suffix
		self.depth = 0 if parent is None else parent.depth + 1

def is_branch(node):
	return node is not None and isinstance(node.suffix, list)

def extend(node, S, N, j, segment_root):
	while is_branch(node.suffix[S[j]]):
		node = node.suffix[S[j]]
		j += 1
	removed = False
	while node.suffix[S[j]] is not None:
		child = SuffixNode(node, [None] * 27)
		leaf = node.suffix[S[j]]
		if not removed:
			remove(segment_root, leaf)
			removed = True
		node.suffix[S[j]] = child
		child.suffix[S[leaf.suffix]] = leaf
		leaf.suffix += 1
		leaf.parent = child
		leaf.depth = child.depth + 1
		node = child
		j += 1
	if removed:
		add(segment_root, leaf)
	node.suffix[S[j]] = SuffixNode(node, j + 1)
	add(segment_root, node.suffix[S[j]])
	return 1 + N - (j + 1)

def traverse(root):
	stack = [(root, 0)]
	while stack:
		(node, i) = stack.pop()
		if i == 26:
			continue
		if is_branch(node.suffix[i]):
			stack.append((node, i + 1))
			stack.append((node.suffix[i], 0))
			yield node.suffix[i]
			continue
		if node.suffix[i] is not None:
			yield node.suffix[i]
		stack.append((node, i + 1))

class SegmentNode1:
	__slots__ = ('a', 'b', 'nodes', 'children')

	def __init__(self, a, b):
		(self.a, self.b) = (a, b)
		self.nodes = []
		self.children = []

class SegmentNode:
	__slots__ = ('a', 'b', 'nodes', 'left', 'right')

	def __init__(self, a, b):
		(self.a, self.b) = (a, b)
		self.nodes = []
		self.left = None if a + 1 == b else SegmentNode(a, (a + b) // 2)
		self.right = None if a + 1 == b else SegmentNode((a + b) // 2, b)

def add1(root, node):
	b = node.suffix
	a = b - node.depth
	_add(root, node, a, b)

def _add1(root, node, a, b):
	(root_a, root_b) = (root.a, root.b)
	if a <= root_a and root_b <= b:
		root.nodes.append(node)
		return
	if b <= root_a or root_b <= a:
		return
	if not root.children and root_a + 1 < root_b:
		mid = (root_a + root_b) // 2
		root.children = [SegmentNode(root_a, mid), SegmentNode(mid, root_b)]
	for c in root.children:
		_add(c, node, a, b)

def remove1(root, node):
	b = node.suffix
	a = b - node.depth
	_remove(root, node, a, b)

def _remove1(root, node, a, b):
	(root_a, root_b) = (root.a, root.b)
	if a <= root_a and root_b <= b:
		root.nodes.remove(node)
		return
	if b <= root_a or root_b <= a:
		return
	for c in root.children:
		_remove(c, node, a, b)

def find1(root, n):
	assert root.a <= n < root.b
	while True:
		for node in root.nodes:
			yield node
		if not root.children:
			break
		root = root.children[(root.a + root.b) // 2 <= n]

def add(root, node):
	b = node.suffix
	a = b - node.depth
	b_xor_a = b ^ a
	mask = root.b // 2
	while not b_xor_a & mask:
		root = root.right if a & mask else root.left
		mask //= 2
	(a_root, b_root) = (root.left, root.right)
	mask //= 2
	while mask:
		if a & mask:
			a_root = a_root.right
		else:
			a_root.right.nodes.append(node)
			a_root = a_root.left
		if b & mask:
			b_root.left.nodes.append(node)
			b_root = b_root.right
		else:
			b_root = b_root.left
		mask //= 2
	a_root.nodes.append(node)

def remove(root, node):
	b = node.suffix
	a = b - node.depth
	b_xor_a = b ^ a
	mask = root.b // 2
	while not b_xor_a & mask:
		root = root.right if a & mask else root.left
		mask //= 2
	(a_root, b_root) = (root.left, root.right)
	mask //= 2
	while mask:
		if a & mask:
			a_root = a_root.right
		else:
			a_root.right.nodes.remove(node)
			a_root = a_root.left
		if b & mask:
			b_root.left.nodes.remove(node)
			b_root = b_root.right
		else:
			b_root = b_root.left
		mask //= 2
	a_root.nodes.remove(node)

def find(root, n):
	assert root.a <= n < root.b
	while root:
		for node in root.nodes:
			yield node
		if n < (root.a + root.b) // 2:
			root = root.left
		else:
			root = root.right

def create_struct(S, N):
	segment_root = SegmentNode(0, 2 ** 17)
	suffix_root = SuffixNode(None, [None] * 27)
	count = [0]
	for i in range(N):
		count[0] += extend(suffix_root, S, N, i, segment_root)
	return (suffix_root, segment_root, count)

def update_struct(st, S, N, P, C):
	(_, segment_root, count) = st
	C0 = S[P]
	S[P] = C
	for leaf in list(find(segment_root, P)):
		remove(segment_root, leaf)
		S[P] = C0
		i = leaf.suffix - 1
		node = leaf.parent
		node.suffix[S[i]] = None
		count[0] -= 1 + N - leaf.suffix
		while P < i and (not any(node.suffix)):
			i -= 1
			node = node.parent
			node.suffix[S[i]] = None
			count[0] -= 1
		while P < i:
			i -= 1
			node = node.parent
		S[P] = C
		count[0] += extend(node, S, N, P, segment_root)

def count_struct(st, N):
	(suffix_root, _) = st
	return sum((1 if is_branch(node) else 1 + N - node.suffix for node in traverse(suffix_root)))

def suffix_repr(node):
	if is_branch(node):
		return '[%s]' % ' '.join(('%s:%s' % ('$' if i == 26 else chr(i + 97), suffix_repr(node.suffix[i])) for i in range(27) if node.suffix[i] is not None))
	else:
		return str(node.suffix)

def segment_repr1(node, indent=0):
	return '%s<%s:%s [%s]>%s' % (' ' * indent, node.a, node.b, ', '.join(('%s:%s' % (n.suffix - n.depth, n.suffix) for n in node.nodes)), ''.join(('\n' + segment_repr(c, indent + 2) for c in node.children)))

def segment_repr(node, indent=0):
	return '%s<%s:%s [%s]>%s' % (' ' * indent, node.a, node.b, ', '.join(('%s:%s' % (n.suffix - n.depth, n.suffix) for n in node.nodes)), ''.join(('\n' + segment_repr(c, indent + 2) for c in (node.left, node.right) if c)))

def check_struct(st):
	(suffix_root, segment_root) = st
	for node in traverse(suffix_root):
		if is_branch(node):
			for child in node.suffix:
				if child:
					assert child.parent is node
					assert child.depth == node.depth + 1

def struct_repr(st):
	check_struct(st)
	(suffix_root, segment_root) = st
	return suffix_repr(suffix_root) + '\n' + segment_repr(segment_root)

def main_3():
	import random
	az = 'abcdefghijklmnopqrstuvwxyz'

	def data():
		import random
		az = 'abcdefghijklmnopqrstuvwxyz'
		yield '75000 75000'
		yield ''.join((random.choice(az) for _ in range(75000)))
		for _ in range(75000):
			yield ('%s %s' % (random.randrange(1, 75001), random.choice(az)))
	data = iter(data())

	def input2():
		return next(data)
	import time
	t0 = time.time()
	(N, Q) = map(int, input().split())
	S = bytearray((ord(c) - 97 for c in input()))
	S.append(26)
	st = create_struct(S, N)
	t1 = time.time()
	tt = 0
	Qs = [input().split() for _ in range(Q)]
	for _ in range(Q):
		(P, C) = Qs[_]
		P = int(P)
		C = ord(C) - 97
		t2 = time.time()
		update_struct(st, S, N, P - 1, C)
		print(st[2][0])
		tt += time.time() - t2
main_3()


from collections import Counter

def subwords(s):
	n = len(s)
	res = []
	for k in range(1, n + 1):
		cnt = Counter(map(lambda i: tuple(s[i:i + k]), range(n + 1 - k)))
		res.append(cnt)
		if len(cnt) + (k - 1) == n:
			break
	return res

def update_subwords(sw_cnt, s, pos, new_char):
	if s[pos] == new_char:
		return (sw_cnt, s)
	n = len(s)
	for (k, d) in enumerate(sw_cnt):
		k = k + 1
		for i in range(max(0, pos + 1 - k), min(pos, n - k) + 1):
			s0 = s[i:i + k]
			key0 = tuple(s0)
			d[key0] -= 1
			if d[key0] <= 0:
				d.pop(key0)
			s0[pos - i] = new_char
			key1 = tuple(s0)
			d[key1] = d.get(key1, 0) + 1
	s[pos] = new_char
	while len(sw_cnt) - 1 + len(sw_cnt[-1]) < n:
		k = len(sw_cnt) + 1
		cnt = Counter(map(lambda i: tuple(s[i:i + k]), range(n + 1 - k)))
		sw_cnt.append(cnt)
	return (sw_cnt, s)

def count_subwords(sw_cnt, s):
	n = len(s)
	k = len(sw_cnt)
	total = (n + 1 - k) * (n - k) // 2 + sum(map(len, sw_cnt))
	return total
(n, q) = map(int, input().split())
text = list(input())
sw_cnt = subwords(text)
res = []
for _ in range(q):
	(i, c) = input().split()
	i = int(i) - 1
	(sw_cnt, text) = update_subwords(sw_cnt, text, i, c)
	res.append(count_subwords(sw_cnt, text))
print(*res, sep='\n')