Read problems statements in Mandarin chinese, Russian and Vietnamese as well. 

Chef was reading a book. He decided to highlight all the lovely sentences of the book. He calls a sentence a lovely sentence if, after removing all the non-alphabetical characters (like punctuation and spaces) from it and converting all uppercase letters to lowercase, it is possible to choose four contiguous characters from the sentence and reorder them to create the string “chef”.

Chef has almost completed the highlighting work, only a few sentences are left to be checked and highlighted. Now, he wants your help in checking the remaining sentences, as he has to help his mother in the kitchen.

Each sentence s has already been preprocessed — all non-alphabetical characters have been erased and all remaining uppercase characters converted to lowercase. You should determine whether s is a lovely sentence or not. If it is a lovely sentence, then Chef is also interested in the number of possible ways to select 4 contiguous characters that can be reordered to give his name (the string "chef").

------ Input ------ 

The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
The first and only line of each test case contains a single string s, denoting a preprocessed sentence.

------ Output ------ 

For each test case, print a single line.
If the string s is not a lovely string, this line should contain a single string “normal” (without quotes).
Otherwise, it should contain the string ”lovely” (without quotes) followed by one integer — the number of ways to select the four contiguous characters.

------ Constraints ------ 

$1 ≤ T ≤ 200,000$
$1 ≤ |s| ≤ 500,000$
$sum of |s| for all test cases ≤ 2,000,000$
$s contains only lowercase English letters$

------ Subtasks ------ 

Subtask #1 (20 points): 1 ≤ |s| ≤ 2000

Subtask #2 (80 points): original constraints

----- Sample Input 1 ------ 
5
ifchefisgoodforchess
fehcaskchefechohisvoice
hecfisaniceperson
letscallchefthefch
chooseaprogrammer
----- Sample Output 1 ------ 
lovely 2
lovely 3
lovely 1
lovely 3
normal
----- explanation 1 ------ 
Example case 1: We can select “fche” (the substring starting at index 2) or “chef” (index 3).
Example case 2: We can select “fehc” (index 1), “chef” (index 8) or “fech” (index 11).
Example case 3: We can only select “hecf” (index 1).
Example case 4: We can select “chef” (index 9), “hefc” (index 14), or “efch” (index 15).
Example case 5: No four contiguous characters can be reordered to form Chef's name.

Difficulty: EASY
Tags: String algorithms

Combinatorics

Complete search

Mathematics

Data structures
Skill types: Data structures

Complete search

Starter code:

Solutions:
n = int(input())
for i in range(n):
	s = list(input())
	c = 0
	for i in range(len(s) - 4):
		if (s[i] == 'c' or s[i] == 'h' or s[i] == 'e' or (s[i] == 'f')) and (s[i + 1] == 'c' or s[i + 1] == 'h' or s[i + 1] == 'e' or (s[i + 1] == 'f')) and (s[i + 2] == 'c' or s[i + 2] == 'h' or s[i + 2] == 'e' or (s[i + 2] == 'f')) and (s[i + 3] == 'c' or s[i + 3] == 'h' or s[i + 3] == 'e' or (s[i + 3] == 'f')):
			t = ''.join(set(s[i] + s[i + 1] + s[i + 2] + s[i + 3]))
			t1 = len(t)
			if t1 == 4:
				c += 1
	if c == 0:
		print('normal')
	else:
		print('lovely ', c)


for i in range(int(input())):
	s = input()
	c = 0
	for i in range(len(s) - 3):
		if set(s[i:i + 4]) == set('chef'):
			c = c + 1
	if c > 0:
		print('lovely', c)
	else:
		print('normal')


from itertools import permutations
for i in range(int(input())):
	s = input()
	c = 0
	p = permutations('chef')
	for i in range(len(s) - 3):
		if set(s[i:i + 4]) == set('chef'):
			c += 1
	if c == 0:
		print('normal')
	else:
		print('lovely', c)


from itertools import permutations
for i in range(int(input())):
	s = input()
	c = 0
	p = permutations('chef')
	for j in p:
		k = ''.join(j)
		c = c + s.count(k)
	if c == 0:
		print('normal')
	else:
		print('lovely', c)


banyak_kasus = int(input())

def BanyakChef(kata):
	hasil = 0
	for x in range(len(kata) - 3):
		if set(kata[x:x + 4]) == set('chef'):
			hasil += 1
	return hasil
while banyak_kasus > 0:
	s = input()
	banyak = BanyakChef(s)
	if banyak > 0:
		print(f'lovely {banyak}')
	else:
		print('normal')
	banyak_kasus -= 1


for _ in range(int(input())):
	s = input()
	ans = 0
	for i in range(len(s)):
		sub_s = set(s[i:i + 4])
		if 'c' in sub_s and 'h' in sub_s and ('e' in sub_s) and ('f' in sub_s):
			ans += 1
	if ans:
		print(f'lovely {ans}')
	else:
		print('normal')


def check(x, l):
	for i in l:
		if i not in x:
			return 0
	return 1
q = int(input())
l = ['c', 'h', 'e', 'f']
while q > 0:
	s = input()
	ls = len(s)
	c = 0
	for i in range(ls - 3):
		x = list(s[i:i + 4])
		if check(x, l):
			c = c + 1
	if c == 0:
		print('normal')
	else:
		print('lovely ', c)
	q = q - 1


for i in range(int(input())):
	b = input()
	d = 0
	for j in range(len(b) - 3):
		c = b[j] + b[j + 1] + b[j + 2] + b[j + 3]
		if c.count('c') == 1 and c.count('h') == 1 and (c.count('e') == 1) and (c.count('f') == 1):
			d += 1
	if d == 0:
		print('normal')
	else:
		print('lovely ', d)


for _ in range(int(input())):
	s = input()
	t = 0
	c = 0
	start = 0
	w = ['c', 'h', 'e', 'f']
	for i in range(len(s) - 3):
		start = i
		for j in range(i, len(s)):
			if s[j] in w:
				t += 1
				w.remove(s[j])
				if t == 4:
					break
			else:
				w = ['c', 'h', 'e', 'f']
				t = 0
				break
		if t == 4 and j < start + 4:
			c += 1
			t = 0
			w = ['c', 'h', 'e', 'f']
	if c:
		print('lovely', c)
	else:
		print('normal')


for i in range(int(input())):
	s = input()
	for i in s:
		if i.isalpha() == False:
			s = s.replace(i, '', 1)
	s = s.lower()
	c = 0
	for i in range(len(s) - 3):
		if 'c' in s[i:i + 4] and 'h' in s[i:i + 4] and ('e' in s[i:i + 4]) and ('f' in s[i:i + 4]):
			c += 1
	if c == 0:
		print('normal')
	else:
		print('lovely ', c)


for _ in range(int(input())):
	l = input()
	l = [*l]
	count = 0
	for i in range(len(l) - 3):
		m = ['c', 'h', 'e', 'f']
		if l[i] in m:
			m.remove(l[i])
			if l[i + 1] in m:
				m.remove(l[i + 1])
				if l[i + 2] in m:
					m.remove(l[i + 2])
					if l[i + 3] in m:
						count += 1
	if count > 0:
		print('lovely ' + str(count))
	else:
		print('normal')


def loveliness(sentence, key):
	indices = {}
	possibilities = 0
	letters = {}
	m = len(key)
	n = len(sentence)
	for i in range(len(sentence) - m + 1):
		j = i + m - 1
		word = sentence[i:j + 1]
		word = ''.join(sorted(word))
		if word == key:
			possibilities += 1
	if possibilities > 0:
		print('lovely ', possibilities)
	else:
		print('normal')
nTests = int(input())
key = 'cefh'
for i in range(nTests):
	sentence = input()
	loveliness(sentence, key)


n = int(input())
for ni in range(n):
	s = input()
	x = len(s)
	c = 0
	for i in range(0, x - 3, 1):
		a = s[i:i + 4]
		if 'c' in a and 'h' in a and ('e' in a) and ('f' in a):
			c = c + 1
	if c == 0:
		print('normal')
	else:
		print('lovely ', c)


l = ['chef', 'chfe', 'cehf', 'cefh', 'cfhe', 'cfeh', 'fche', 'fceh', 'fhec', 'fhce', 'fech', 'fehc', 'echf', 'ecfh', 'ehfc', 'ehcf', 'efhc', 'efch', 'hcef', 'hcfe', 'hfce', 'hfec', 'hefc', 'hecf']
n = int(input())
for ni in range(n):
	s = input()
	c = 0
	for i in l:
		if i in s:
			c = c + s.count(i)
	if c > 0:
		print('lovely', c)
	else:
		print('normal')


t = int(input())
for i in range(t):
	s = input()
	n = len(s)
	c = 0
	for i in range(n - 3):
		q = set(s[i:i + 4])
		if 'c' in q and 'h' in q and ('e' in q) and ('f' in q):
			c += 1
	if c > 0:
		print('lovely ', c)
	else:
		print('normal')


for _ in range(int(input())):
	s = input()
	x = 'chef'
	d = 0
	for i in range(len(s) - 3):
		q = s[i:i + 4]
		c = 0
		for i in x:
			if i in q:
				c += 1
		if c == 4:
			d += 1
	if d == 0:
		print('normal')
	else:
		print('lovely ' + str(d))


t = int(input())
for _ in range(t):
	s = input()
	lis = []
	for i in range(len(s) - 3):
		x = s[i:i + 4]
		if 'c' in x and 'h' in x and ('e' in x) and ('f' in x):
			lis.append(x)
	if len(lis) >= 1:
		print('lovely', len(lis))
	else:
		print('normal')


for t in range(int(input())):
	s = input()
	c = 0
	for i in range(len(s) - 3):
		x = s[i] + s[i + 1] + s[i + 2] + s[i + 3]
		if x.count('c') == 1 and x.count('h') == 1 and (x.count('e') == 1) and (x.count('f') == 1):
			c += 1
	if c == 0:
		print('normal')
	else:
		print('lovely', c)


for i in range(int(input())):
	string = input()
	total = 0
	word = 'chef'
	cur = ''
	for i in range(len(string) - 3):
		if string[i] in word and string[i] not in cur:
			cur += string[i]
		if string[i + 1] in word and string[i + 1] not in cur:
			cur += string[i + 1]
		if string[i + 2] in word and string[i + 2] not in cur:
			cur += string[i + 2]
		if string[i + 3] in word and string[i + 3] not in cur:
			cur += string[i + 3]
		if len(cur) == 4:
			total += 1
		cur = ''
	if total <= 0:
		print('normal')
	else:
		print('lovely', total)


for tc in range(int(input())):
	s = input()
	ans = 'normal'
	cnt = 0
	for i in range(len(s) - 3):
		if 'c' in s[i:i + 4] and 'h' in s[i:i + 4] and ('e' in s[i:i + 4]) and ('f' in s[i:i + 4]):
			cnt += 1
			ans = 'lovely'
	if ans == 'lovely':
		print(ans, cnt)
	else:
		print(ans)


def char_val(c):
	if c == 'c':
		return 1
	elif c == 'h':
		return 2
	elif c == 'e':
		return 4
	elif c == 'f':
		return 8
	else:
		return 0
for _ in range(int(input())):
	s = 'aaa' + input()
	lovely = 0
	ways = 0
	for i in range(3, len(s)):
		lovely += char_val(s[i])
		if lovely == 15:
			ways += 1
		lovely -= char_val(s[i - 3])
	if ways == 0:
		print('normal')
	else:
		print('lovely', ways)


a = int(input(''))
for i in range(a):
	t = input('')
	c = 0
	for j in range(0, len(t) - 3):
		l = t[j:j + 4]
		if l.count('c') == 1 and l.count('h') == 1 and (l.count('e') == 1) and (l.count('f') == 1):
			c = c + 1
	if c > 0:
		print('lovely', c)
	else:
		print('normal')


T = int(input())
while T != 0:
	s = input()
	c = 0
	for i in range(0, len(s) - 3):
		k = 'chef'
		if s[i] in k:
			k = k.replace(s[i], '')
			if s[i + 1] in k:
				k = k.replace(s[i + 1], '')
				if s[i + 2] in k:
					k = k.replace(s[i + 2], '')
					if s[i + 3] in k:
						c = c + 1
	if c == 0:
		print('normal')
	else:
		print('lovely ' + str(c))
	T = T - 1


for i in range(int(input())):
	s = input()
	a = 'cefh'
	c = 0
	for i in range(len(s) - 3):
		if s[i] == 'c' or s[i] == 'h' or s[i] == 'e' or (s[i] == 'f'):
			x = s[i:i + 4]
			y = ''.join(sorted(x))
			if y == a:
				c += 1
	if c > 0:
		print('lovely ' + str(c))
	else:
		print('normal')


for i in range(int(input())):
	s = input()
	k = 0
	for i in range(len(s) - 3):
		l = s[i:i + 4]
		if 'c' in l and 'h' in l and ('e' in l) and ('f' in l):
			k += 1
	if k == 0:
		print('normal')
	else:
		print('lovely', k)


t = int(input())
for i in range(t):
	res = input()
	c = 0
	for i in range(len(res) - 3):
		g = res[i:i + 4]
		if g.count('c') == 1 and g.count('h') == 1 and (g.count('e') == 1) and (g.count('f') == 1):
			c += 1
	if c > 0:
		print('lovely {}'.format(c))
	else:
		print('normal')


def r2(num):
	return range(1, num + 1)
ii = lambda : int(input())
li = lambda : list(map(int, input().split()))
si = lambda : input()
ssi = lambda : list(input())
sepi = lambda : map(int, input().split())
seti = lambda : set(map(int, input().split()))
check = ['chef', 'chfe', 'cehf', 'cefh', 'cfhe', 'cfeh', 'hcef', 'hcfe', 'hecf', 'hefc', 'hfce', 'hfec', 'echf', 'ecfh', 'ehcf', 'ehfc', 'efch', 'efhc', 'fche', 'fceh', 'fhce', 'fhec', 'fech', 'fehc']
for i in range(int(input())):
	sentence = si()
	sentence = ''.join((i for i in sentence if i.isalpha())).lower()
	ans = 0
	for i in range(24):
		if check[i] in sentence:
			ans += sentence.count(check[i])
	if ans:
		print('lovely', ans)
	else:
		print('normal')


from itertools import permutations
a = 'chef'
s = permutations(a, 4)
a = [''.join(i) for i in s]
for i in range(int(input())):
	x = input()
	c = 0
	for i in range(0, len(x) - 4):
		if x[i:i + 4] in a:
			c += 1
	if c >= 1:
		print('lovely ', c)
	else:
		print('normal')


for _ in range(int(input())):
	s = input()
	c = 0
	for i in range(len(s) - 3):
		b = s[i:i + 4]
		if 'c' in b and 'h' in b and ('e' in b) and ('f' in b):
			c = c + 1
	if c == 0:
		print('normal')
	else:
		print('lovely', c)


for _ in range(int(input())):
	s = input()
	c = 0
	n = 4
	if len(s) >= 4:
		for i in range(0, len(s) - n + 1):
			if ''.join(sorted(s[i:i + n])) == 'cefh':
				c += 1
	if c == 0:
		print('normal')
	else:
		print('lovely', c)


for _ in range(int(input())):
	s = input()
	count = 0
	n = len(s)
	for i in range(n):
		if 'c' in s[i:i + 4] and 'h' in s[i:i + 4] and ('e' in s[i:i + 4]) and ('f' in s[i:i + 4]):
			count += 1
	if count == 0:
		print('normal')
	else:
		print('lovely', count)


import itertools
a = 'chef'
p = list(itertools.permutations(a))
a = [''.join(perm) for perm in p]
for _ in range(int(input())):
	res = input()
	c = 0
	for i in range(len(res) - 3):
		if res[i:i + 4] in a:
			c += 1
	if c > 0:
		print('lovely {}'.format(c))
	else:
		print('normal')


for _ in range(int(input())):
	s = input()
	c = 0
	for i in range(len(s) - 3):
		a = ['c', 'h', 'e', 'f']
		if s[i] in a:
			a.remove(s[i])
			if s[i + 1] in a:
				a.remove(s[i + 1])
				if s[i + 2] in a:
					a.remove(s[i + 2])
					if s[i + 3] in a:
						c += 1
	print('normal' if c == 0 else 'lovely ' + str(c))


t = int(input())
for i in range(t):
	s = str(input())
	ans = 'normal'
	lovely_str_count = 0
	for j in range(len(s) - 3):
		if 'c' in s[j:j + 4] and 'e' in s[j:j + 4] and ('f' in s[j:j + 4]) and ('h' in s[j:j + 4]):
			ans = 'lovely'
			lovely_str_count += 1
	if ans == 'normal':
		print('normal')
	else:
		print('lovely', lovely_str_count)


for _ in range(int(input())):
	s = input()
	su_m = 0
	for i in range(len(s) - 3):
		if s[i] in ['c', 'e', 'f', 'h']:
			m = [s[i], s[i + 1], s[i + 2], s[i + 3]]
			m.sort()
			if m == ['c', 'e', 'f', 'h']:
				su_m += 1
	if su_m > 0:
		print('lovely', su_m)
	else:
		print('normal')


n = int(input())
for i in range(0, n):
	string = input().lower()
	count = 0
	for j in range(0, len(string)):
		word = string[j:j + 4]
		if 'c' in word and 'h' in word and ('e' in word) and ('f' in word):
			count = count + 1
	if count == 0:
		print('normal')
	else:
		print(f'lovely {count}')


for T in range(int(input())):
	s = input()
	count = 0
	for i in range(0, len(s) - 3):
		if {s[i], s[i + 1], s[i + 2], s[i + 3]} == {'c', 'h', 'e', 'f'}:
			count += 1
	if count != 0:
		print('lovely', count)
	else:
		print('normal')


for _ in range(int(input())):
	s = input()
	c = 0
	for i in range(0, len(s) - 3):
		l = list(s[i:i + 4])
		l.sort()
		if l[0] == 'c' and l[1] == 'e' and (l[2] == 'f') and (l[3] == 'h'):
			c += 1
	if c == 0:
		print('normal')
	else:
		print(f'lovely {c}')


def fun(s):
	track = 0
	for i in range(0, len(s) - 3):
		if {s[i], s[i + 1], s[i + 2], s[i + 3]} == {'c', 'h', 'e', 'f'}:
			track += 1
	if track != 0:
		return f'lovely {track}'
	return 'normal'
n = int(input())
for i in range(n):
	s = input()
	print(fun(s))


t = int(input())
for i in range(t):
	str = input()
	n = 0
	l = ['chef', 'chfe', 'cehf', 'cefh', 'cfhe', 'cfeh', 'hcef', 'hcfe', 'hecf', 'hefc', 'hfec', 'hfce', 'echf', 'ecfh', 'efch', 'efhc', 'ehfc', 'ehcf', 'fceh', 'fche', 'fech', 'fehc', 'fhec', 'fhce']
	for i in range(len(str)):
		s = str[i:i + 4]
		if s in l:
			n = n + 1
	if n != 0:
		print(f'lovely {n}')
	else:
		print('normal')


for _ in range(int(input())):
	s = input()
	max = 0
	for i in range(len(s) - 3):
		count = 0
		if s[i] == 'c' or s[i] == 'h' or s[i] == 'e' or (s[i] == 'f'):
			count = 0
			l = ['c', 'h', 'e', 'f']
			for j in range(i, i + 4):
				if s[j] in l:
					count += 1
					l.remove(s[j])
			if count == 4:
				max += 1
	if max != 0:
		print('lovely', max)
	else:
		print('normal')


from itertools import permutations
t = int(input())
for i in range(t):
	a = input()
	l = []
	m = []
	perm = permutations(['c', 'h', 'e', 'f'])
	s = ''
	for i in list(perm):
		l.append(s.join(i))
	for i in l:
		c = a.count(i)
		m.append(c)
	if sum(m) == 0:
		print('normal')
	else:
		print('lovely', sum(m))


for i in range(int(input())):
	s = str(input())
	sub = 'cefh'
	count = 0
	for i in range(len(s)):
		ch = s[i:i + 4]
		st = ''.join(sorted(ch))
		if st == sub:
			count += 1
	if count == 0:
		print('normal')
	else:
		print('lovely ', count)


t = int(input())
l1 = ['c', 'e', 'f', 'h']
n = 4
for i in range(t):
	l2 = list(input())
	c = 0
	for i in range(4, len(l2) + 1):
		ind = i - n
		arr = l2[ind:i]
		arr = sorted(arr)
		if arr == l1:
			c += 1
	if c != 0:
		print('lovely', c)
	else:
		print('normal')


for _ in range(int(input())):
	S = input().strip()
	words = {'c', 'h', 'e', 'f'}
	c = 0
	i = 0
	while i < len(S) - 3:
		if set([S[i], S[i + 1], S[i + 2], S[i + 3]]) & words == words:
			c += 1
		i += 1
	if c != 0:
		print('lovely', c)
	else:
		print('normal')


for _ in range(int(input())):
	s = input()
	chars = ['c', 'h', 'e', 'f']
	count = 0
	for i in range(len(s)):
		string = s[i:i + 4]
		if all((chars[j] in string for j in range(4))):
			count += 1
	if count > 0:
		print('lovely', count)
	else:
		print('normal')


d = {}
for m in 'abcdefghijklmnopqrstuvwxyz':
	if m == 'c':
		d[m] = 1
	elif m == 'h':
		d[m] = 2
	elif m == 'e':
		d[m] = 3
	elif m == 'f':
		d[m] = 4
	else:
		d[m] = 10000
for _ in range(int(input())):
	s = input().lower()
	s = ''.join([i for i in s if i.isalpha()])
	count = 0
	for i in range(len(s) - 3):
		k = sorted(list(s[i:i + 4]), key=lambda x: d[x])
		if k == ['c', 'h', 'e', 'f']:
			count = count + 1
	if count == 0:
		print('normal')
	else:
		print('lovely ' + str(count))


for _ in range(int(input())):
	s = input().lower()
	s = ''.join([I for I in s if I.isalpha()])
	count = 0
	for i in range(len(s) - 3):
		k = sorted(list(s[i:i + 4]))
		if k == ['c', 'e', 'f', 'h']:
			count = count + 1
	if count == 0:
		print('normal')
	else:
		print('lovely ' + str(count))


testcases = int(input())
list2 = ['c', 'e', 'f', 'h']
n = 4
for i in range(testcases):
	list1 = list(input())
	count = 0
	for i in range(4, len(list1) + 1):
		index = i - n
		arr = list1[index:i]
		new_arr = sorted(arr)
		if new_arr == list2:
			count += 1
	if count != 0:
		print('lovely', count)
	else:
		print('normal')


for _ in range(int(input())):
	s = input()
	i = 0
	c = 0
	while i < len(s) - 3:
		if (s[i] == 'c' or s[i] == 'h' or s[i] == 'e' or (s[i] == 'f')) and (s[i + 1] != s[i] and (s[i + 1] == 'c' or s[i + 1] == 'h' or s[i + 1] == 'e' or (s[i + 1] == 'f'))) and (s[i + 2] != s[i + 1] and s[i + 2] != s[i] and (s[i + 2] == 'c' or s[i + 2] == 'h' or s[i + 2] == 'e' or (s[i + 2] == 'f'))) and (s[i + 3] != s[i + 2] and s[i + 3] != s[i + 1] and (s[i + 3] != s[i]) and (s[i + 3] == 'c' or s[i + 3] == 'h' or s[i + 3] == 'e' or (s[i + 3] == 'f'))):
			c += 1
		i += 1
	if c == 0:
		print('normal')
	else:
		print('lovely', c)


t = int(input())
k = ['c', 'e', 'f', 'h']
for i in range(t):
	s = list(input())
	count = 0
	for i in range(4, len(s) + 1):
		p = i - 4
		l4 = s[p:i]
		p = sorted(l4)
		if p == k:
			count += 1
	if count != 0:
		print('lovely', count)
	else:
		print('normal')


def check(s):
	if 'c' in s and 'h' in s and ('e' in s) and ('f' in s):
		return 1
	return 0
for _ in range(int(input())):
	count = 0
	s1 = input()
	for i in range(len(s1) - 3):
		count += check(s1[i:i + 4])
	if count != 0:
		print('lovely', count)
	else:
		print('normal')