Chef recently saw the movie Matrix. He loved the movie overall but he didn't agree with some things in it. Particularly he didn't agree with the bald boy when he declared - There is no spoon. Being a chef, he understands the importance of the spoon and realizes that the universe can't survive without it. Furthermore, he is sure there is a spoon; he saw it in his kitchen this morning. So he has set out to prove the bald boy is wrong and find a spoon in the matrix. He has even obtained a digital map already. Can you help him?

Formally you're given a matrix of lowercase and uppercase Latin letters. Your job is to find out if the word "Spoon" occurs somewhere in the matrix or not. A word is said to be occurred in the matrix if it is presented in some row from left to right or in some column from top to bottom. Note that match performed has to be case insensitive. 

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

The first line of input contains a positive integer T, the number of test cases. After that T test cases follow. The first line of each test case contains two space separated integers R and C, the number of rows and the number of columns of the matrix M respectively. Thereafter R lines follow each containing C characters, the actual digital map itself.

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

For each test case print one line. If a "Spoon" is found in Matrix, output "There is a spoon!" else output "There is indeed no spoon!" (Quotes only for clarity).

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

1 ≤ T ≤ 100

1 ≤ R, C ≤ 100

----- Sample Input 1 ------ 
3
3 6
abDefb
bSpoon
NIKHil
6 6
aaaaaa
ssssss
xuisdP
oooooo
ioowoo
bdylan
6 5
bdfhj
cacac
opqrs
ddddd
india
yucky
----- Sample Output 1 ------ 
There is a spoon!
There is a spoon!
There is indeed no spoon!
----- explanation 1 ------ 
In the first test case, "Spoon" occurs in the second row. In the second test case, "spOon" occurs in the last column.

Difficulty: EASY
Tags: Data structures

Implementation

Complete search
Skill types: Data structures

Complete search

Starter code:

Solutions:
for i in range(int(input())):
	(n, m) = map(int, input().split())
	l = []
	for i in range(n):
		l.append(input().lower())
	f = 0
	for i in l:
		if 'spoon' in i:
			f = 1
			break
	if f == 0:
		for j in range(m):
			for i in range(n - 4):
				if l[i][j] == 's' and l[i + 1][j] == 'p' and (l[i + 2][j] == 'o') and (l[i + 3][j] == 'o') and (l[i + 4][j] == 'n'):
					f = 1
					break
	if f == 1:
		print('There is a spoon!')
	else:
		print('There is indeed no spoon!')


t = int(input())
for ni in range(t):
	(r, c) = map(int, input().split())
	s = list()
	a = 0
	for i in range(r):
		a1 = input()
		b = ''
		for i in range(len(a1)):
			b = b + a1[i].capitalize()
		if 'SPOON' in b:
			a = 1
		else:
			s.append(b)
	if a == 0:
		for i in range(r - 4):
			for j in range(c):
				if s[i][j] == 'S' and s[i + 1][j] == 'P' and (s[i + 2][j] == 'O') and (s[i + 3][j] == 'O') and (s[i + 4][j] == 'N'):
					a = 1
	if a == 1:
		print('There is a spoon!')
	else:
		print('There is indeed no spoon!')


def check_found(ar):
	Found = 0
	for ele in ar:
		Letter = ''.join(ele)
		if 'spoon' in Letter:
			Found = 1
			break
	return Found
t = int(input())
for i in range(t):
	(r, c) = list(map(int, input().split()))
	word_ar = []
	for j in range(r):
		word = input().lower()
		mylist = []
		for k in range(c):
			mylist.append(word[k])
		word_ar.append(mylist)
	Spoon_Found = check_found(word_ar)
	if Spoon_Found != 1:
		word_2_ar = [[word_ar[j][i] for j in range(len(word_ar))] for i in range(len(word_ar[0]))]
		Spoon_Found = check_found(word_2_ar)
	if Spoon_Found == 1:
		print('There is a spoon!')
	else:
		print('There is indeed no spoon!')


for i in range(int(input())):
	(a, b) = map(int, input().split())
	list1 = []
	flag = True
	for j in range(a):
		ask = input()
		list1.append(ask)
	for k in list1:
		if 'spoon' in k.lower():
			flag = False
		elif 'noops' in k.lower():
			flag = False
	str1 = ''
	for i in range(b):
		for j in range(a):
			str1 += list1[j][i]
		str1 = str1.lower()
		if 'spoon' in str1:
			flag = False
	if flag == True:
		print('There is indeed no spoon!')
	else:
		print('There is a spoon!')


t = int(input())
for i in range(t):
	(m, k) = map(int, input().split())
	mat = []
	c = 0
	for i in range(m):
		mat.append(input())
	for i in range(m):
		s = mat[i]
		s = s.upper()
		if 'SPOON' in s:
			c = 1
			break
	if c == 1:
		print('There is a spoon!')
	else:
		f = 0
		for i in range(k):
			a = ''
			for j in range(m):
				a += mat[j][i]
			a = a.upper()
			if 'SPOON' in a:
				f = 1
				break
		if f == 1:
			print('There is a spoon!')
		else:
			print('There is indeed no spoon!')


t = int(input())
for i in range(t):
	(row, col) = map(int, input().split())
	flag = 0
	l = []
	for j in range(row):
		s = input()
		l.append(s.lower())
	if row < 5 and col < 5:
		flag = 0
	elif 'spoon' in l:
		flag = 1
	else:
		for j in range(row):
			for k in range(col):
				if k < col - 4 and l[j][k] == 's' and (l[j][k + 1] == 'p') and (l[j][k + 2] == 'o') and (l[j][k + 3] == 'o') and (l[j][k + 4] == 'n'):
					flag = 1
					break
				elif j < row - 4 and l[j][k] == 's' and (l[j + 1][k] == 'p') and (l[j + 2][k] == 'o') and (l[j + 3][k] == 'o') and (l[j + 4][k] == 'n'):
					flag = 1
					break
	if flag:
		print('There is a spoon!')
	else:
		print('There is indeed no spoon!')


for _ in range(int(input())):
	(r, c) = map(int, input().split())
	l = []
	f = False
	for i in range(r):
		s = input().lower()
		l.append(s)
		if 'spoon' in s:
			f = True
	if f == True:
		print('There is a spoon!')
	elif r < 6:
		print('There is indeed no spoon!')
	else:
		f = False
		for i in range(r):
			if r - i >= 5:
				for j in range(c):
					if l[i][j] == 's' and l[i + 1][j] == 'p' and (l[i + 2][j] == 'o') and (l[i + 3][j] == 'o') and (l[i + 4][j] == 'n'):
						f = True
						break
		if f == True:
			print('There is a spoon!')
		else:
			print('There is indeed no spoon!')


for _ in range(int(input())):
	(r, c) = map(int, input().split())
	l = list()
	a = 0
	for i in range(r):
		s = input().upper()
		if 'SPOON' in s:
			a = 1
		else:
			l.append(s)
	if a == 0:
		for i in range(r - 4):
			for j in range(c):
				if l[i][j] == 'S' and l[i + 1][j] == 'P' and (l[i + 2][j] == 'O') and (l[i + 3][j] == 'O') and (l[i + 4][j] == 'N'):
					a = 1
	if a == 1:
		print('There is a spoon!')
	else:
		print('There is indeed no spoon!')


t = int(input())
for _ in range(t):
	(a, b) = map(int, input().split())
	grid = [input().lower() for _ in range(a)]
	if any(('spoon' in row for row in grid)):
		print('There is a spoon!')
	elif any(('spoon' in ''.join(col) for col in zip(*grid))):
		print('There is a spoon!')
	else:
		print('There is indeed no spoon!')


for _ in range(int(input())):
	(r, c) = map(int, input().split())
	l = []
	for i in range(r):
		l.append(input())
	for i in range(c):
		m = ''
		for j in range(r):
			m += l[j][i]
		l.append(m)
	for i in l:
		if 'spoon' in i.lower():
			print('There is a spoon!')
			break
	else:
		print('There is indeed no spoon!')


T = int(input())
for i in range(T):
	a = []
	(r, c) = map(int, input().split())
	for i in range(r):
		s = input()
		a.append(s.lower())
	flag = 0
	for i in a:
		if 'spoon' in i:
			flag = 1
	if flag == 0:
		ans = []
		for k in range(c):
			s = ''
			for h in range(r):
				s += a[h][k]
			ans.append(s)
		for i in ans:
			if 'spoon' in i:
				flag = 1
	if flag == 1:
		print('There is a spoon!')
	else:
		print('There is indeed no spoon!')


a = int(input())
for i in range(a):
	(b, c) = map(int, input().split())
	k = []
	for j in range(b):
		k.append(input().lower())
	t = 0
	for i in k:
		if 'spoon' in i:
			t = 1
			break
	if t == 0:
		for i in range(c):
			r = ''
			for j in range(b):
				r = r + k[j][i]
			if 'spoon' in r:
				t = 1
				break
	if t == 1:
		print('There is a spoon!')
	else:
		print('There is indeed no spoon!')


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	r = []
	for i in range(n):
		e = input()
		r.append(e.lower())
	flag = 0
	for i in r:
		if 'spoon' in i:
			flag = 1
	if flag == 1:
		print('There is a spoon!')
		continue
	if n < 5:
		print('There is indeed no spoon!')
		continue
	else:
		c = []
		for i in range(len(r[0])):
			e = ''
			for j in range(n):
				e = e + r[j][i]
			c.append(e)
		flag = 0
		for i in c:
			if 'spoon' in i:
				flag = 1
		if flag == 1:
			print('There is a spoon!')
			continue
		if flag == 0:
			print('There is indeed no spoon!')


for _ in range(int(input())):
	(r, c) = map(int, input().split())
	t = 0
	l = []
	for i in range(r):
		s = input()
		s = s.lower()
		l.append(s)
	if c >= 5:
		for m in l:
			if 'spoon' in m:
				t += 1
	if r >= 5:
		for n in range(0, r - 4):
			for p in range(c):
				if 's' in l[n][p]:
					if 'p' in l[n + 1][p]:
						if 'o' in l[n + 2][p]:
							if 'o' in l[n + 3][p]:
								if 'n' in l[n + 4][p]:
									t += 1
	if t != 0:
		print('There is a spoon!')
	else:
		print('There is indeed no spoon!')


n = int(input())
for i in range(n):
	x = [int(p) for p in input().split()]
	r = x[0]
	c = x[1]
	l = []
	flag = 0
	for j in range(r):
		kk = input()
		l.append(kk)
		l[j] = l[j].lower()
		if 'spoon' in l[j] and flag == 0:
			print('There is a spoon!')
			flag = 1
	if flag == 0:
		for k in range(c):
			str1 = ''
			for l1 in range(r):
				str1 = str1 + l[l1][k]
			if 'spoon' in str1:
				flag = 1
				break
		if flag == 1:
			print('There is a spoon!')
		else:
			print('There is indeed no spoon!')


n = int(input())
for i in range(n):
	(a, b) = list(map(int, input().split()))
	s = []
	for i in range(a):
		k = input().lower()
		s.append(list(k))
	rs = ''
	for i in s:
		for j in i:
			rs = rs + j
	cs = ''
	for i in range(b):
		for j in range(a):
			cs = cs + s[j][i]
	if 'spoon' in rs or 'spoon' in cs:
		print('There is a spoon!')
	else:
		print('There is indeed no spoon!')


for _ in range(int(input())):
	(r, c) = map(int, input().split())
	arr = [' ' for i in range(r)]
	for i in range(r):
		st = input()
		arr[i] = st
	flag = False
	req1 = 'spoon'
	req2 = 'SPOON'
	for i in range(r):
		index = 0
		for j in range(c):
			if arr[i][j] == req1[index] or arr[i][j] == req2[index]:
				index += 1
			else:
				index = 0
			if index == 5:
				flag = 'True'
				break
		if flag:
			break
	for i in range(c):
		index = 0
		for j in range(r):
			if arr[j][i] == req1[index] or arr[j][i] == req2[index]:
				index += 1
			else:
				index = 0
			if index == 5:
				flag = True
				break
		if flag:
			break
	if flag:
		print('There is a spoon!')
	else:
		print('There is indeed no spoon!')


tst = int(input())
for _ in range(tst):
	(h, k) = map(int, input().split())
	mat = []
	found = False
	for _ in range(h):
		c = input().lower()
		if 'spoon' in c:
			found = True
		mat.append(c)
	if found:
		print('There is a spoon!')
	else:
		for i in range(k):
			s = ''
			for j in range(h):
				s += mat[j][i]
			if 'spoon' in s:
				found = True
				break
		if found:
			print('There is a spoon!')
		else:
			print('There is indeed no spoon!')


for _ in range(int(input())):
	(m, n) = map(int, input().split())
	matrix = []
	flag = 0
	for i in range(m):
		str = input().lower()
		if flag == 0:
			matrix.append(list(str))
			if str.find('spoon') >= 0:
				flag = 1
		else:
			continue
	if flag:
		print('There is a spoon!')
	else:
		str = ''
		for i in range(n):
			for j in range(m):
				str += matrix[j][i]
			if str.find('spoon') >= 0:
				flag = 1
				break
			else:
				str = ''
			if flag:
				break
		if flag:
			print('There is a spoon!')
		else:
			print('There is indeed no spoon!')


for _ in range(int(input())):
	(r, c) = map(int, input().split())
	mat = []
	b = 0
	for i in range(r):
		s = input().lower()
		if 'spoon' in s:
			b = 1
		mat.append(s)
	if b != 1:
		for i in range(c):
			co = [row[i] for row in mat]
			x = ''.join(co)
			if 'spoon' in x:
				b = 1
				break
	print('There is indeed no spoon!' if b == 0 else 'There is a spoon!')


for _ in range(int(input())):
	(r, c) = list(map(int, input().split()))
	l = []
	for i in range(r):
		l.append(input().lower())
	flag = 0
	for i in l:
		if 'spoon' in i:
			flag = 1
			break
	if flag == 0:
		for j in range(c):
			for i in range(r - 4):
				if l[i][j] == 's' and l[i + 1][j] == 'p' and (l[i + 2][j] == 'o') and (l[i + 3][j] == 'o') and (l[i + 4][j] == 'n'):
					flag = 1
					break
	if flag == 1:
		print('There is a spoon!')
	else:
		print('There is indeed no spoon!')


for i in range(int(input())):
	D = list(map(int, input().split()))
	l = []
	flag = False
	for i in range(D[0]):
		s = input()
		a = s.lower()
		l.append(a)
	for i in l:
		if 'spoon' in i:
			flag = True
			break
	if D[0] >= 5:
		for j in range(D[1]):
			a = ''
			for i in l:
				a += i[j]
			b = a.lower()
			if 'spoon' in b:
				flag = True
				break
	if flag:
		print('There is a spoon!')
	else:
		print('There is indeed no spoon!')


for i in range(int(input())):
	flag = 0
	(n, m) = map(int, input().split())
	l = []
	for i in range(n):
		x = input().lower()
		l.append(x)
	if m >= 5:
		for k in l:
			if 'spoon' in k:
				print('There is a spoon!')
				flag = 1
				break
	if n >= 5 and flag == 0:
		a = 0
		str = ''
		for k in range(m):
			for o in range(n):
				str = str + l[o][k]
			if 'spoon' in str:
				print('There is a spoon!')
				flag = 1
				break
			else:
				str = ''
	if flag == 0:
		print('There is indeed no spoon!')
		flag = 0


for _ in range(int(input())):
	(n, s) = map(int, input().split())
	l = []
	flag = 0
	for i in range(n):
		l.append(input())
	for i in range(n):
		k = l[i]
		k = k.upper()
		if 'SPOON' in k:
			flag = 1
			break
	if flag == 1:
		print('There is a spoon!')
	else:
		c = 0
		for i in range(s):
			a = ''
			for j in range(n):
				a += l[j][i]
			a = a.upper()
			if 'SPOON' in a:
				c = 1
				break
		if c == 1:
			print('There is a spoon!')
		else:
			print('There is indeed no spoon!')


t = int(input())
while t > 0:
	t = t - 1
	(r, c) = map(int, input().split())
	l = []
	for i in range(r):
		l.append(input())
	for i in range(c):
		m = ''
		for j in range(r):
			m += l[j][i]
		l.append(m)
	for i in l:
		if 'spoon' in i.lower():
			print('There is a spoon!')
			break
	else:
		print('There is indeed no spoon!')


for _ in range(int(input())):
	(r, c) = map(int, input().split())
	l = []
	for i in range(r):
		l.append(input().lower())
	flag = 0
	for i in l:
		if 'spoon' in i:
			flag = 1
			break
	if flag == 0:
		l1 = []
		for p in range(c):
			s = ''
			for q in range(r):
				s += l[q][p]
			l1.append(s)
		for i in l1:
			if 'spoon' in i:
				flag = 1
				break
	if flag == 1:
		print('There is a spoon!')
	else:
		print('There is indeed no spoon!')


t = int(input())
for _ in range(t):
	(r, c) = map(int, input().split())
	matrix = []
	for i in range(r):
		matrix.append(input().lower())
	found = False
	for row in matrix:
		if 'spoon' in row:
			found = True
			break
	if not found:
		for i in range(c):
			col = ''
			for j in range(r):
				col += matrix[j][i]
			if 'spoon' in col:
				found = True
				break
	if found:
		print('There is a spoon!')
	else:
		print('There is indeed no spoon!')


for i in range(int(input())):
	(a, b) = map(int, input().split())
	l = []
	v = a
	for i in range(a):
		l.append(input().lower())
	x = 0
	for j in l:
		if 'spoon' in j:
			x = 1
			break
	if x == 0:
		for j in range(a):
			if v > 4:
				v -= 1
				for k in range(b):
					if l[j][k] == 's' and l[j + 1][k] == 'p' and (l[j + 2][k] == 'o') and (l[j + 3][k] == 'o') and (l[j + 4][k] == 'n'):
						x = 1
						break
	if x == 1:
		print('There is a spoon!')
	else:
		print('There is indeed no spoon!')


def solve(m, n, arr):
	if n > 4:
		for s in arr:
			for i in range(n - 4):
				t = s[i:i + 5]
				if t == 'spoon':
					return 'There is a spoon!'
	if m > 4:
		for i in range(n):
			for j in range(m - 4):
				s = ''
				for k in range(5):
					s += arr[j + k][i]
				if s == 'spoon':
					return 'There is a spoon!'
	return 'There is indeed no spoon!'
for _ in range(int(input())):
	(m, n) = map(int, input().split())
	arr = []
	for __ in range(m):
		s = input().lower()
		arr.append(s)
	print(solve(m, n, arr))


T = int(input())
for _ in range(T):
	(R, C) = map(int, input().split())
	matrix = []
	for _ in range(R):
		matrix.append(input())
	flag = False
	for row in matrix:
		if 'spoon' in row.lower():
			flag = True
			break
	for col in range(C):
		column = ''
		for row in matrix:
			column += row[col]
		if 'spoon' in column.lower():
			flag = True
			break
	if flag:
		print('There is a spoon!')
	else:
		print('There is indeed no spoon!')