#ord: $->36, 0->48, 9->57, A->65, Z->90, a->97, z->122
def SA_IS(s, upper=127):
	n = len(s)
	sa = [-1 for _ in range(n)]
	bucket = [0 for _ in range(upper + 1)]
	smaller = [True for _ in range(n)]
	#leftmost L-type
	is_lms = [False for _ in range(n)]
	lmss = []

	#make indices of buckets
	#range of x's bucket is [bucket[x], bucket[x+1])
	for x in s:
		bucket[x+1] += 1
	for i in range(upper):
		bucket[i+1] += bucket[i]

	#step 1:decide whether s[i:n] is a S-type(smaller) or L-type(larger)
	# and whether it's an LMS
	for i in range(n-2, -1, -1):
		if s[i] > s[i+1] or (s[i] == s[i+1] and not smaller[i+1]):
			smaller[i] = False
			if smaller[i+1]:
				is_lms[i+1] = True
				lmss.append(i+1)

	#step 2-1: fill LMSs from the bottom
	count = [0 for _ in range(upper + 1)]
	for i in lmss:
		sa[bucket[s[i] + 1] - 1 - count[s[i] + 1]] = i
		count[s[i] + 1] += 1

	#step 2-2: fill Ls from the beginning
	count = [0 for _ in range(upper + 1)]
	for i in range(n):
		if sa[i] > 0 and not smaller[sa[i] - 1]:
			sa[bucket[s[sa[i] - 1]] + count[s[sa[i] - 1] + 1]] = sa[i] - 1
			count[s[sa[i] - 1] + 1] += 1

	#step 2-3: fill Ss from the bottom
	count = [0 for _ in range(upper + 1)]
	for i in range(n-1, -1, -1):
		if sa[i] > 0 and smaller[sa[i] - 1]:
			sa[bucket[s[sa[i] - 1] + 1] - 1 - count[s[sa[i] - 1] + 1]] = sa[i] - 1
			count[s[sa[i] - 1] + 1] += 1

	#step 3: form reduced string from LMS blocks
	new_num = 0
	new_array = [-1 for _ in range(len(lmss))]
	lms_to_ind = dict()
	for i, x in enumerate(lmss):
		lms_to_ind[x] = len(lmss) - 1 - i
	last = sa[0]
	new_array[lms_to_ind[sa[0]]] = 0
	for i in range(1, n):
		if is_lms[sa[i]]:
			tmp, j = sa[i], 0
			while True:
				if s[last + j] != s[tmp + j]:
					new_num += 1
					break
				if j > 0 and (is_lms[last + j] or is_lms[tmp + j]):
					break
				j += 1
			new_array[lms_to_ind[tmp]] = new_num
			last = tmp
	
	#step 4: sort LMS blocks
	#if all LMS blocks are different, recursion is not needed
	if new_num == len(lmss) - 1:
		seed = [-1 for _ in range(len(lmss))]
		for i, x in enumerate(new_array):
			seed[x] = i
	#call recursive function
	else:
		seed = SA_IS(new_array, upper=new_num + 1)

	new_lmss = [-1 for _ in range(len(lmss))]
	for i, x in enumerate(seed):
		new_lmss[len(lmss) - 1 - i] = lmss[len(lmss) - 1 - x]

	#step 5-1: fill LMSs from the bottom
	sa = [-1 for _ in range(n)]
	count = [0 for _ in range(upper + 1)]
	for i in new_lmss:
		sa[bucket[s[i] + 1] - 1 - count[s[i] + 1]] = i
		count[s[i] + 1] += 1

	#step 5-2: fill Ls from the beginning
	count = [0 for _ in range(upper + 1)]
	for i in range(n):
		if sa[i] > 0 and not smaller[sa[i] - 1]:
			sa[bucket[s[sa[i] - 1]] + count[s[sa[i] - 1] + 1]] = sa[i] - 1
			count[s[sa[i] - 1] + 1] += 1

	#step 5-3: fill Ss from the bottom
	count = [0 for _ in range(upper + 1)]
	for i in range(n-1, -1, -1):
		if sa[i] > 0 and smaller[sa[i] - 1]:
			sa[bucket[s[sa[i] - 1] + 1] - 1 - count[s[sa[i] - 1] + 1]] = sa[i] - 1
			count[s[sa[i] - 1] + 1] += 1

	return sa


def LCP_Array(s, sa):
	n = len(s)-1
	rank = [-1 for _ in range(n)]
	for i, x in enumerate(sa):
		rank[x] = i
	lcp = [-1 for _ in range(n-1)]
	i = 0
	for x in rank:
		if x == n-1:
			continue
		while sa[x] + i < n and sa[x+1] + i < n and s[sa[x] + i] == s[sa[x+1] + i]:
			i += 1
		lcp[x] = i
		i = max(0, i-1)
	return lcp

s = input()
s = [ord(x)-96 for x in s] + [0]
sa = SA_IS(s, 30)[1:]
lcp = LCP_Array(s, sa)
n = len(s)-1
print(n * (n+1) // 2 - sum(lcp))

Measured memory_bytes: 97580