There is a given list of strings where each string contains only lowercase letters from $a-j$, inclusive. The set of strings is said to be a GOOD SET if no string is a prefix of another string.  In this case, print GOOD SET.  Otherwise, print BAD SET on the first line followed by the string being checked. 

Note If two strings are identical, they are prefixes of each other.

Example 

$words=[\text{'abcd'},\text{'bcd'},\text{'abcd'},\text{'bcde'}]$     

Here 'abcd' is a prefix of 'abcde' and 'bcd' is a prefix of 'bcde'.  Since 'abcde' is tested first, print 

BAD SET  
abcde

$words=[\text{'ab'},\text{'bc'},\text{'cd'}]$.   

No string is a prefix of another so print 

GOOD SET 

Function Description 

Complete the noPrefix function in the editor below.  

noPrefix has the following parameter(s): 

- string words[n]: an array of strings  

Prints 

-   string(s): either GOOD SET or BAD SET on one line followed by the word on the next line.  No return value is expected.  

Input Format 

First line contains $n$, the size of $words[]$. 

Then next $n$ lines each contain a string, $words[i]$.   

Constraints 

$1\leq n\leq10^5$ 

$1\leq$ the length of words[i] $\leq60$ 

All letters in $words[i]$ are in the range 'a' through 'j', inclusive.    

Sample Input00  

STDIN       Function
-----       --------
7            words[] size n = 7
aab          words = ['aab', 'defgab', 'abcde', 'aabcde', 'bbbbbbbbbb', 'jabjjjad']
defgab  
abcde
aabcde
cedaaa
bbbbbbbbbb
jabjjjad

Sample Output00  

BAD SET
aabcde

Explanation 

'aab' is prefix of 'aabcde' so it is a BAD SET and fails at string 'aabcde'.  

Sample Input01

4
aab
aac
aacghgh
aabghgh

Sample Output01  

BAD SET
aacghgh

Explanation 

'aab' is a prefix of 'aabghgh', and aac' is prefix of 'aacghgh'. The set is a BAD SET.   'aacghgh' is tested before 'aabghgh', so and it fails at 'aacghgh'.

Source: hackerrank | Difficulty: MEDIUM_HARD
Tags: String algorithms


Solutions:
class solution:

	def checkSET(self, strs):
		trie = dict()
		for cstr in strs:
			curr = trie
			for ch in cstr:
				if ch not in curr:
					curr[ch] = dict()
				curr = curr[ch]
				if '_end' in curr:
					return cstr
			if len(curr) > 0:
				return cstr
			curr['_end'] = ''
		return ''
n = int(input())
strs = []
for i in range(n):
	strs.append(input())
sol = solution()
ret = sol.checkSET(strs)
if ret == '':
	print('GOOD SET')
else:
	print('BAD SET')
	print(ret)


N = int(input())
trie = {}
end = object()
for _ in range(N):
	s = input()
	t = trie
	for c in s[:-1]:
		if c in t:
			t = t[c]
		else:
			t[c] = {}
			t = t[c]
		if t is end:
			print('BAD SET')
			print(s)
			exit()
	if s[-1] in t:
		print('BAD SET')
		print(s)
		exit()
	else:
		t[s[-1]] = end
print('GOOD SET')


N = int(input())
trie = {}
end = object()
for _ in range(N):
	s = input()
	t = trie
	for c in s[:-1]:
		if c in t:
			t = t[c]
		else:
			t[c] = {}
			t = t[c]
		if t is end:
			print('BAD SET')
			print(s)
			exit()
	if s[-1] in t:
		print('BAD SET')
		print(s)
		exit()
	else:
		t[s[-1]] = end
print('GOOD SET')


import sys
trie = {}
for n in range(int(input())):
	s = input()
	node = trie
	for c in s[0:-1]:
		node = node.setdefault(c, {})
		if 'END' in node:
			print('BAD SET')
			print(s)
			sys.exit()
	if s[-1] in node:
		print('BAD SET')
		print(s)
		sys.exit()
	node[s[-1]] = {'END': True}
print('GOOD SET')


num_strings = int(input())

class Node:

	def __init__(self, c=None):
		self.char = c
		self.is_complete = False
		self.children = []

	def append(self, string):
		if len(string) == 0:
			if self.is_complete == False:
				self.is_complete = True
				return True
			return False
		if self.is_complete == True:
			if len(string) > 0:
				return False
		children_chars = [str(node.char) for node in self.children]
		if string[0] in children_chars:
			ind = children_chars.index(string[0])
			if len(string) > 1:
				return self.children[ind].append(string[1:])
			return False
		elif len(string) > 1:
			self.children.append(Node(string[0]))
			return self.children[len(self.children) - 1].append(string[1:])
		else:
			self.children.append(Node(string[0]))
			self.children[len(self.children) - 1].is_complete = True
			return True
n = Node()
import sys
max_num = 10 ** 5 - 10 ** 4
for i in range(num_strings):
	string = input()
	if n.append(string) == False:
		print('BAD SET')
		print(string)
		sys.exit()
	if i >= max_num:
		print('GOOD SET')
		sys.exit()
print('GOOD SET')


def insTrie(trie, s):
	curr = trie
	lens = len(s)
	for (i, char) in enumerate(s):
		if char in curr:
			if curr[char]:
				if i == lens - 1:
					return False
				else:
					curr = curr[char]
			else:
				return False
		else:
			curr[char] = {}
			curr = curr[char]
	return True
t = int(input())
trie = {}
bad = False
for i in range(t):
	new = input()
	if not insTrie(trie, new):
		bad = True
		break
if bad:
	print('BAD SET')
	print(new)
else:
	print('GOOD SET')


num_lines = int(input().strip())
data = {}
done = False
for _ in range(num_lines):
	if done:
		break
	string = input().strip()
	current = data
	for (index, char) in enumerate(string):
		if char in current.keys():
			if current[char] == 0 or index == len(string) - 1:
				print('BAD SET')
				print(string)
				done = True
				break
			else:
				current = current[char]
		elif index == len(string) - 1:
			current[char] = 0
		else:
			current[char] = {}
			current = current[char]
if not done:
	print('GOOD SET')


class Trie(object):

	def __init__(self):
		self.root = {}
		self.value_key = 'value'

	def Add(self, s):
		curr_node = self.root
		for c in s:
			if c not in curr_node:
				curr_node[c] = {}
			curr_node = curr_node[c]
		if curr_node != self.root:
			curr_node[self.value_key] = s

	def HasPrefix(self, s):
		curr_node = self.Traverse(s)
		return False if curr_node is None else True

	def IsPrefix(self, s):
		curr_node = self.root
		for c in s:
			if c in curr_node:
				curr_node = curr_node[c]
				if self.value_key in curr_node:
					return True
			else:
				break
		return False

	def Search(self, s):
		curr_node = self.Traverse(s)
		return curr_node[self.value_key] if curr_node is not None and self.value_key in curr_node else None

	def Traverse(self, s):
		curr_node = self.root
		for c in s:
			if c in curr_node:
				curr_node = curr_node[c]
			else:
				return None
		return curr_node

	def SafeToAdd(self, s):
		return not (self.HasPrefix(s) or self.IsPrefix(s))

def ProcessTrie(string_list, t):
	for s in string_list:
		if not t.SafeToAdd(s):
			print('BAD SET')
			print(s)
			return
		t.Add(s)
	print('GOOD SET')

def CheckGoodString(s):
	for c in s:
		if c < 'a' and c > 'j':
			return False
N = int(input())
strings = []
for it in range(N):
	s = input()
	strings.append(s)
t = Trie()
ProcessTrie(strings, t)


class Node:

	def __init__(self):
		self.child = [None for i in range(10)]
		self.isLeaf = False

class Trie:

	def mti(a):
		return ord(a) - ord('a')

	def __init__(self):
		self.root = Node()

	def insert(self, a):
		cur = self.root
		gotNewNode = False
		for i in range(len(a)):
			if cur.isLeaf == True:
				return False
			if cur.child[Trie.mti(a[i])] == None:
				gotNewNode = True
				cur.child[Trie.mti(a[i])] = Node()
			cur = cur.child[Trie.mti(a[i])]
		cur.isLeaf = True
		return gotNewNode
tr = Trie()
n = int(input())
gotAnswer = False
while n > 0:
	cur = input()
	if not tr.insert(cur):
		print('BAD SET')
		print(cur)
		gotAnswer = True
		break
	n -= 1
if not gotAnswer:
	print('GOOD SET')


import string, sys

class TrieKnot:

	def __init__(self, char):
		self.char = char
		self.child = []
		self.end = False

	def __str__(self):
		return '%s (%s): [%s]' % (self.char, self.end, ', '.join(map(str, self.child)))

	def __eq__(self, other):
		if isinstance(other, str):
			return other == self.char
		elif isinstance(other, TrieKnot):
			return other.char == self.char

	def __hash__(self):
		return hash(self.char)

class Trie:

	def __init__(self):
		self.root = TrieKnot('')

	def __str__(self):
		return str(self.root)
N = int(input())
T = Trie()
found = ''
for _ in range(N):
	w = input().strip()
	curK = T.root
	for c in w:
		if c in curK.child:
			curK = curK.child[curK.child.index(c)]
		elif curK.end:
			found = w
			break
		else:
			k = TrieKnot(c)
			curK.child.append(k)
			curK = k
	if curK.end or len(curK.child) > 0:
		found = w
	curK.end = True
	if found != '':
		print('BAD SET')
		print(found)
		break
if found == '':
	print('GOOD SET')


from sys import stdin, exit
from collections import defaultdict

def default():
	return defaultdict(lambda : [False, default()])

class Trie:

	def __init__(self):
		self.map = default()

	def add(self, word):
		m = self.map
		for i in range(len(word)):
			l = m[word[i]]
			if l[0]:
				return False
			m = l[1]
		if m:
			return False
		l[0] = True
		return True
n = int(stdin.readline())
t = Trie()
for ni in range(n):
	l = stdin.readline().strip()
	if not t.add(l):
		print('BAD SET')
		print(l)
		exit(0)
print('GOOD SET')


class Trie:
	END = '_end'

	def __init__(self):
		self.root = dict()

	def insert_and_verify_no_prefix(self, word):
		current = self.root
		for letter in word:
			current = current.setdefault(letter, dict())
			if current.get(self.END, False):
				return False
		if current.keys():
			return False
		return current.setdefault(self.END, True)

def solve():
	trie = Trie()
	for _ in range(int(input())):
		word = input()
		if not trie.insert_and_verify_no_prefix(word):
			print('BAD SET')
			print(word)
			return
	print('GOOD SET')
solve()


class Trie:

	def __init__(self):
		self.letters = {}

	def insert_word(self, s):
		madeNew = False
		curr = self.letters
		for c in s:
			if '*' in curr:
				return False
			if c not in curr:
				madeNew = True
				curr[c] = {}
			curr = curr[c]
		curr['*'] = None
		return madeNew
trie = Trie()
seen = set()
N = int(input())
good = True
for _ in range(N):
	s = input()
	if s in seen:
		print('BAD SET')
		print(s)
		good = False
		break
	seen.add(s)
	good = trie.insert_word(s)
	if not good:
		print('BAD SET')
		print(s)
		break
if good:
	print('GOOD SET')


n = int(input())

class Trie:

	def __init__(self, c):
		self.c = c
		self.children = set()
trie = {}

def add_to_trie(t, w):
	c = w.pop(0)
	if '$' in t:
		return False
	if '$' == c and t:
		return False
	if not c in t:
		t[c] = {}
	if w:
		return add_to_trie(t[c], w)
	else:
		return True
for i in range(n):
	w = input()
	if not add_to_trie(trie, list(w) + ['$']):
		print('BAD SET')
		print(w)
		break
else:
	print('GOOD SET')


from sys import exit

class Node(object):

	def __init__(self):
		self.children = {}

def insert(root, s):
	r = root
	i = 0
	while i < len(s) and s[i] in r.children:
		r = r.children[s[i]]
		i += 1
	if i == len(s) or (i and (not r.children)):
		raise KeyError
	while i < len(s):
		r.children[s[i]] = Node()
		r = r.children[s[i]]
		i += 1
n = int(input())
root = Node()
for _ in range(n):
	s = input()
	try:
		insert(root, s)
	except KeyError:
		print('BAD SET')
		print(s)
		exit()
print('GOOD SET')


class Trie(object):

	def __init__(self):
		self.is_end = False
		self.children = [None for i_ in range(26)]

	def insert(self, string, start=0):
		if start >= len(string):
			if self.is_end:
				return False
			self.is_end = True
			for child in self.children:
				if child is not None:
					return False
			return True
		first_char = string[start]
		child = self.children[ord(first_char) - ord('a')]
		if child is None:
			child = Trie()
		if self.is_end:
			return False
		result = child.insert(string, start + 1)
		if not result:
			return result
		self.children[ord(first_char) - ord('a')] = child
		return True

	def is_present(self, string):
		trie = self
		for char in string:
			if trie is None:
				return False
			trie = trie.children[ord(char) - ord('a')]
		if trie and trie.is_end:
			return True
		return False
a = Trie()
n = int(input())
is_bad = False
offender = None
for i in range(n):
	s = input().strip()
	result = a.insert(s)
	if not result:
		is_bad = True
		offender = s
		break
if is_bad:
	print('BAD SET')
	print(offender)
else:
	print('GOOD SET')


class PrefixNode:

	def __init__(self):
		self.isLeaf = False
		self.children = dict()

class PrefixTree:

	def __init__(self):
		self.root = PrefixNode()

	def insert(self, word):
		hasCreatedNewNode = False
		node = self.root
		if node.isLeaf:
			return False
		for letter in word:
			if not letter in node.children:
				node.children[letter] = PrefixNode()
				hasCreatedNewNode = True
			node = node.children[letter]
			if node.isLeaf:
				return False
		node.isLeaf = True
		return hasCreatedNewNode

def main():
	prefixTree = PrefixTree()
	N = int(input())
	for _ in range(N):
		word = input().strip()
		res = prefixTree.insert(word)
		if not res:
			print('BAD SET')
			print(word)
			return 1
	print('GOOD SET')
main()


class TrieNode(object):

	def __init__(self):
		self.children = {}
		self.terminal = False
number_of_strings = int(input())
input_strings = []
for _ in range(number_of_strings):
	input_strings.append(input())
root = TrieNode()
bad_string = None
for test_string in input_strings:
	pointer = root
	failed = False
	for test_char in test_string:
		insertion_occured = False
		if test_char not in pointer.children:
			new_node = TrieNode()
			pointer.children[test_char] = new_node
			pointer = new_node
			insertion_occured = True
		else:
			pointer = pointer.children[test_char]
			if pointer.terminal:
				failed = True
				break
	if insertion_occured:
		pointer.terminal = True
	else:
		failed = True
	if failed:
		bad_string = test_string
		break
if bad_string is None:
	print('GOOD SET')
else:
	print('BAD SET')
	print(bad_string)


class Node:

	def __init__(self):
		self.isWord = False
		self.children = {}

	def get(self, c):
		if c not in self.children:
			self.children[c] = Node()
		return self.children[c]

class Trie:

	def __init__(self):
		self.root = Node()

	def insert(self, w):
		x = self.root
		for c in w:
			x = x.get(c)
		x.isWord = True

	def hasPrefix(self, w):
		x = self.root
		for c in w:
			x = x.get(c)
			if x.isWord:
				return True
		return len(x.children) > 0
n = int(input())
t = Trie()
for _ in range(n):
	s = input().strip()
	if t.hasPrefix(s):
		print('BAD SET')
		print(s)
		break
	t.insert(s)
else:
	print('GOOD SET')


class Trie:

	def __init__(self):
		self.next = {}
		self.terminal = 0

	def insert(self, word):
		root = self
		for (i, val) in enumerate(word):
			if val not in root.next:
				root.next[val] = Trie()
			if i == len(word) - 1:
				root.terminal = 1
			root = root.next[val]

	def insertINT(self, word):
		bad_word = True
		node = self
		for (i, val) in enumerate(word):
			if val not in node.next:
				bad_word = False
				node.next[val] = Trie()
			node = node.next[val]
			if node.terminal == 1:
				bad_word = True
				break
			if i == len(word) - 1:
				node.terminal = 1
		return bad_word
arr = []
n = int(input())
for i in range(n):
	arr.append(input())
bad_set = False
root = Trie()
for word in arr:
	if root.insertINT(word) is True:
		bad_set = True
		break
if bad_set is not True:
	print('GOOD SET')
else:
	print('BAD SET')
	print(word)


class Node:

	def __init__(self):
		self.children = {}
		self.data = None
		self.c = None

	def getChild(self, c):
		if c not in self.children:
			self.children[c] = Node()
		self.c = c
		return self.children[c]
root = Node()
for _ in range(int(input())):
	t = input()
	n = root
	for c in list(t):
		if n.data is None:
			n = n.getChild(c)
		else:
			print('BAD SET')
			print(t)
			break
	else:
		if n.data is not None or len(n.children):
			print('BAD SET')
			print(t)
			break
		else:
			n.data = t
			continue
	break
else:
	print('GOOD SET')


SETSIZE = ord('j') - ord('a') + 1

class Node:

	def __init__(self, range):
		self.range = range
		self.arr = [None] * range
		self.end = False

def badset(word):
	print('BAD SET')
	print(word)

def goodset():
	print('GOOD SET')

def main():
	root = Node(SETSIZE)
	rounds = int(input())
	for i in range(rounds):
		current = root
		newPath = False
		word = input()
		try:
			data = list(map(lambda x: ord(x) - 97, list(word)))
			for char in data:
				if char > SETSIZE or char < 0:
					badset(word)
					return
				if current.end:
					badset(word)
					return
				if current.arr[char] is None:
					newPath = True
					current.arr[char] = Node(SETSIZE)
				current = current.arr[char]
			current.end = True
			if not newPath:
				badset(word)
				return
		except:
			badset(word)
			return
	goodset()
main()


class TrieNode:
	special_character = '$'

	def __init__(self, ch):
		self.children = []
		self.character = ch

	def __cmp__(self, other):
		return self.character == other.character

	def is_word(self):
		for x in self.children:
			if x.character == TrieNode.special_character:
				return True
		return False

	def add_word(self, word):
		aux_word = word
		is_prefix = False
		node = self
		for ch in aux_word:
			if node.is_word():
				is_prefix = True
			aux_node = None
			for child in node.children:
				if child.character == ch:
					aux_node = child
					break
			if aux_node is None:
				aux_node = TrieNode(ch)
				node.children.append(aux_node)
			node = aux_node
		if node.is_word():
			is_prefix = True
		elif len(node.children) > 0:
			is_prefix = True
			node.children.append(TrieNode(TrieNode.special_character))
		else:
			node.children.append(TrieNode(TrieNode.special_character))
		return is_prefix
test_cases = int(input())
root = TrieNode('')
prefix = False
for i in range(test_cases):
	word = input()
	prefix = root.add_word(word)
	if prefix:
		print('BAD SET', end='\n')
		print(word, end='\n')
		break
if not prefix:
	print('GOOD SET', end='\n')


def insert_and_check(str_in, head):
	head_tmp = head
	str_len = len(str_in)
	for i in range(0, str_len):
		if head_tmp[1][int(ord(str_in[i]) - 97)] == 0:
			if head_tmp[0] == 2:
				return 0
			if head_tmp[0] != head[0]:
				head_tmp[0] = 1
			head_tmp[1][int(ord(str_in[i]) - 97)] = [0, [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]
			head_tmp = head_tmp[1][int(ord(str_in[i]) - 97)]
		else:
			head_tmp = head_tmp[1][int(ord(str_in[i]) - 97)]
	if head_tmp[0] == 1 or head_tmp[0] == 2:
		return 0
	else:
		head_tmp[0] = 2
		return 1
head = [10, [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]
N = int(input())
for i in range(0, N):
	str_in = input()
	ret_val = insert_and_check(str_in, head)
	if ret_val == 0:
		break
if ret_val == 0:
	print('BAD SET')
	print(str_in)
else:
	print('GOOD SET')


import sys
rl = lambda : sys.stdin.readline().strip()
n = int(rl())
t = {}
broken_elem = None
for i in range(0, n):
	s = rl()
	tcur = t
	for c in s:
		if c not in tcur:
			tcur[c] = {}
		elif len(tcur[c]) == 0:
			broken_elem = s
			break
		tcur = tcur[c]
	broken_elem = s if len(tcur) > 0 or broken_elem is not None else None
	if broken_elem is not None:
		break
if broken_elem is not None:
	print('BAD SET')
	print(broken_elem)
else:
	print('GOOD SET')


def add(contacts, name):
	pos = contacts
	for letter in name:
		if letter not in pos.keys():
			pos[letter] = {}
		pos = pos[letter]
		if 'end' in pos.keys():
			return False
		if 'count' not in pos.keys():
			pos['count'] = 1
		else:
			pos['count'] += 1
	pos['end'] = True
	if pos['count'] > 1:
		return False
	else:
		return True
contacts = {}
n = int(input())
for _ in range(n):
	s = input()
	if not add(contacts, s):
		print('BAD SET')
		print(s)
		break
else:
	print('GOOD SET')


import collections

class TrieNode:

	def __init__(self):
		self.children = collections.defaultdict(TrieNode)
		self.isWord = False

class Trie:

	def __init__(self):
		self.root = TrieNode()

	def insert(self, word):
		node = self.root
		for i in word:
			node = node.children[i]
			if node.isWord:
				return word
		node.isWord = True
		if len(node.children):
			return word
		return False

def main():
	num = int(input())
	tree = Trie()
	for i in range(num):
		word = input()
		res = tree.insert(word)
		if res:
			print('BAD SET')
			print(res)
			return
	print('GOOD SET')
main()


class Node:

	def __init__(self, value, valid):
		self.value = value
		self.valid = valid
		self.children = []
		self.num_valid_children = 0

def add_if_good(node, word):
	curr = node
	curr.num_valid_children += 1
	existed = False
	for letter in word:
		res = find_or_set(curr, letter)
		curr = res[0]
		existed = res[1]
		if existed and curr.valid:
			return True
		curr.num_valid_children += 1
	curr.valid = True
	if existed and curr.valid:
		return True
	else:
		return False

def add(node, word):
	curr = node
	curr.num_valid_children += 1
	for letter in word:
		res = find_or_set(curr, letter)
		curr = res[0]
		curr.num_valid_children += 1
	curr.valid = True

def find_or_set(root, letter, valid=False):
	found = find(root, letter)
	if found:
		return (found, True)
	else:
		n = Node(letter, valid)
		root.children.append(n)
		return (n, False)

def find(root, substr):
	curr = root
	for letter in substr:
		curr = _find_in_list(curr.children, letter)
		if not curr:
			return
	return curr

def find_num_children(root, word):
	found = find(root, word)
	return found.num_valid_children if found else 0

def _find_in_list(l, letter):
	for item in l:
		if item.value == letter:
			return item

def main():
	trie = Node('', False)
	num_words = int(input())
	all_words = [input() for _ in range(num_words)]
	for word in all_words:
		if add_if_good(trie, word):
			print('BAD SET')
			print(word)
			return
	print('GOOD SET')
main()


class Node(object):

	def __init__(self, value):
		self.value = value
		self.children = []
		self.is_valid = False

	def _child(self, letter):
		for node in self.children:
			if letter == node.value:
				return node
		return False

class Trie(object):

	def __init__(self):
		self.root = Node('_root_')
		self.good = True

	def add(self, word):
		curr = self.root
		for letter in word:
			if curr.is_valid:
				print('BAD SET')
				print(word)
				self.good = False
				return
			elif curr._child(letter):
				curr = curr._child(letter)
			else:
				new = Node(letter)
				curr.children.append(new)
				curr = new
		if curr.is_valid or curr.children:
			print('BAD SET')
			print(word)
			self.good = False
			return
		curr.is_valid = True
		return
numlines = input()
t = Trie()
for i in range(int(numlines)):
	word = input()
	t.add(word)
	if not t.good:
		break
if t.good:
	print('GOOD SET')


class Trie:

	def __init__(self):
		self.root = dict()

	def isPrefix(self, word):
		current = self.root
		for letter in word:
			current = current.setdefault(letter, {})
			if '_end' in current:
				return True
		current['_end'] = '_end'
		if len(current) > 1:
			return True
		return False

def goodOrBad(cases):
	trie = Trie()
	for _ in range(cases):
		word = input()
		if trie.isPrefix(word):
			print('BAD SET')
			print(word)
			return False
	return True
cases = int(input())
if goodOrBad(cases):
	print('GOOD SET')


tree = {}

def insert(tree, s):
	current_node = tree
	index = 0
	while True:
		if 'X' in current_node:
			return False
		character = s[index]
		preexisting = character in current_node
		if character not in current_node:
			current_node[character] = {}
		index += 1
		current_node = current_node[character]
		if index == len(s):
			current_node['X'] = True
			if preexisting:
				return False
			else:
				return True

def main():
	string_count = int(input())
	unordered_strings = [input() for i in range(string_count)]
	for s in unordered_strings:
		if not insert(tree, s):
			print('BAD SET')
			print(s)
			return
	print('GOOD SET')
main()


class Node:

	def __init__(self, data):
		self.__data = data
		self.__child = []
		self.__wordMark = False
		self.__count = 1

	def getData(self):
		return self.__data

	def addChild(self, childNode):
		self.__child.append(childNode)

	def getChild(self, data):
		for node in self.__child:
			if data == node.getData():
				return node
		return 0

	def setWordMark(self):
		self.__wordMark = True

	def isWordMark(self):
		return self.__wordMark

	def getWordCount(self):
		return self.__count

	def addWordCount(self):
		self.__count += 1

class Trie:

	def __init__(self):
		self.__root = Node('')

	def getRoot(self):
		return self.__root

	def isPrefixSet(self, word):
		currentNode = self.getRoot()
		for ch in word:
			childNode = currentNode.getChild(ch)
			if childNode == 0:
				childNode = Node(ch)
				currentNode.addChild(childNode)
			else:
				if childNode.isWordMark():
					return True
				childNode.addWordCount()
			currentNode = childNode
		if currentNode.getWordCount() > 1:
			return True
		currentNode.setWordMark()
		return False
t = Trie()
N = int(input())
for i in range(N):
	word = input()
	if t.isPrefixSet(word):
		print('BAD SET')
		print(word)
		exit()
print('GOOD SET')


import sys

class Trie(dict):

	def __init__(self, *args, **kw):
		self.sentinel_count = 0
		self.initial_word = ''
		super(Trie, self).__init__(*args, **kw)

	def add(self, data):
		pos = self
		bad_set = False
		for ix in range(len(data)):
			newborn = False
			substr = data[:ix + 1]
			if not substr in pos:
				newborn = True
			if newborn:
				pos[substr] = Trie()
				pos[substr].initial_word = data
			pos = pos[substr]
			if pos.sentinel_count:
				bad_set = True
		pos.sentinel_count += 1
		if pos.initial_word != data:
			bad_set = True
		return bad_set
trie = Trie()
lines = sys.stdin.readlines()
_bad_set = False
for line in lines[1:]:
	data = line.strip()
	_bad_set = trie.add(data)
	if _bad_set:
		print('BAD SET')
		print(data)
		break
if not _bad_set:
	print('GOOD SET')


_leaf = '_leaf_'

class Node(object):

	def __init__(self):
		self.children = {}

	def add(self, word, node):
		current_node = node
		for letter in word:
			current_node = current_node.children.setdefault(letter, Node())
		current_node.children[_leaf] = _leaf

	def is_word_ok(self, word, node):
		current_node = node
		for letter in word:
			current_node = current_node.children.get(letter, None)
			if not current_node:
				return True
			if current_node.children.get(_leaf, False):
				return False
		return False
n = int(input())
root = Node()
is_bad_set = False
for _ in range(n):
	word = input().strip()
	if not root.is_word_ok(word, root):
		is_bad_set = True
		break
	else:
		root.add(word, root)
if is_bad_set:
	print('BAD SET')
	print(word)
else:
	print('GOOD SET')


import sys
holder = '\n'

class Tie:

	def __init__(self):
		self.root = {}

	def add(self, name):
		root = self.root
		for ch in name:
			if holder in root:
				return name
			root = root.setdefault(ch, {})
		if len(root) > 0:
			return name
		root.setdefault(holder, {})

def main():
	tie = Tie()
	n = int(sys.stdin.readline())
	while n > 0:
		str = sys.stdin.readline().strip('\n')
		ret = tie.add(str)
		if ret:
			print('BAD SET')
			print(ret)
			break
		n -= 1
	else:
		print('GOOD SET')
main()


N = int(input())
trie = {}

def add_word(trie, word):
	if word[0] not in trie:
		trie[word[0]] = {}
	if 'end' in trie[word[0]]:
		raise Exception
	if len(word) == 1:
		if len(trie[word[0]].keys()):
			raise Exception
		trie[word[0]]['end'] = True
		return
	add_word(trie[word[0]], word[1:])
for i in range(N):
	word = input()
	try:
		if word != '':
			add_word(trie, word.rstrip())
	except Exception:
		print('BAD SET')
		print(word)
		break
else:
	print('GOOD SET')


class Node:

	def __init__(self, letter):
		self.word_end = False
		self.letter = letter
		self.children = {}
		self.words_in_subtrees = 0

	def __str__(self):
		return 'Letter: {}\nWord end: {}\nSubwords:{}\nChildren: {}\n'.format(self.letter, self.word_end, self.words_in_subtrees, self.children)

def add_to_trie(root, word):
	if root.word_end and word:
		return False
	f = word[0]
	if not root.children.get(f, None):
		root.children[f] = Node(f)
	if word[1:]:
		root.words_in_subtrees += 1
		return add_to_trie(root.children[f], word[1:])
	else:
		if root.children[f].words_in_subtrees > 0:
			return False
		root.children[f].word_end = True
		root.words_in_subtrees += 1
		root.children[f].words_in_subtrees += 1
	return True
root = Node('*')
N = int(input().strip())
good = True
for case in range(N):
	word = input().strip()
	if not add_to_trie(root, word):
		good = False
		wrongword = word
		break
if good:
	print('GOOD SET')
else:
	print('BAD SET')
	print(wrongword)


import sys
n = int(input().strip())
db = dict()
s = [input().strip() for _ in range(n)]
for (i, x) in enumerate(s):
	if x in db.keys():
		db[x] = min(db[x], i)
	else:
		db[x] = i
ml = sys.maxsize
for (j, st) in enumerate(s):
	i = 1
	while i <= len(st):
		if st[:i] in db.keys():
			if db[st[:i]] != j:
				ml = min(ml, max(j, db[st[:i]]))
		i += 1
if ml != sys.maxsize:
	print('BAD SET')
	print(s[ml])
else:
	print('GOOD SET')


def addString(root, string):
	current = root
	length = len(string)
	for i in range(length):
		char = string[i]
		if i == length - 1 and current.get(char):
			return False
		if not current.get(char):
			current[char] = {'end': False}
		current = current[char]
		if current['end']:
			return False
	current['end'] = True
	return True
N = int(input())
root = {}
good_set = True
for _ in range(N):
	string = input()
	if not addString(root, string):
		print('BAD SET')
		print(string)
		good_set = False
		break
if good_set:
	print('GOOD SET')


root = {}

def add_to(root, s):
	current_node = root.setdefault(s[0], [0, {}])
	if len(s) == 1:
		current_node[0] += 1
	else:
		add_to(current_node[1], s[1:])

def is_prefix(root, s):
	if len(s) == 1:
		if len(root[s[0]][1]) > 0 or root[s[0]][0] > 1:
			return True
		else:
			return False
	elif root[s[0]][0] > 0:
		return True
	else:
		return is_prefix(root[s[0]][1], s[1:])
n = int(input())
count = 0
for _ in range(n):
	word = input().strip()
	add_to(root, word)
	if is_prefix(root, word):
		print('BAD SET')
		print(word)
		break
	count += 1
if count == n:
	print('GOOD SET')


from collections import defaultdict

class Node:

	def __init__(self):
		self.letter = None
		self.finish = False
		self.children = defaultdict(Node)

	def add_string(self, s):
		node = self
		last_node_new = False
		for c in s:
			node = node.children[c]
			if node.finish:
				return False
			last_node_new = node.letter is None
			node.letter = c
		node.finish = True
		return last_node_new

def solve(strings):
	root = Node()
	for s in strings:
		if not root.add_string(s):
			return (False, s)
	return (True, None)

def read_lines(n):
	for _ in range(n):
		yield input()

def main():
	n = int(input())
	(good, first_bad) = solve(list(read_lines(n)))
	if good:
		print('GOOD SET')
	else:
		print('BAD SET\n%s' % first_bad)
main()


def addWordToTrie(dic, word):
	tempNode = dic
	for i in range(len(word)):
		if '_end_' in tempNode and tempNode['_end_'] == '_end_':
			return False
		else:
			if i == len(word) - 1 and word[i] in tempNode:
				return False
			if word[i] not in tempNode:
				tempNode[word[i]] = {}
		tempNode = tempNode[word[i]]
	tempNode['_end_'] = '_end_'
	return True
trie = {}
x = int(input())
for i in range(x):
	string = input()
	r = addWordToTrie(trie, string)
	if not r:
		print('BAD SET')
		print(string)
		break
if r:
	print('GOOD SET')


class Trie(object):

	def __init__(self):
		self.root = TrieNode()
		pass

	def add(self, s):
		tn = self.root
		path = []
		for i in range(len(s)):
			ch = s[i]
			if ch not in tn.children.keys():
				tn.children[ch] = TrieNode(ch)
			tn = tn.children[ch]
			if tn.is_end:
				return False
			path.append(tn)
		tn.is_end = True
		if len(tn.children.keys()) != 0:
			return False
		return True

	def n_with_prefix(self, prefix):
		tn = self.root
		for ch in prefix:
			if ch not in tn.children.keys():
				return 0
			tn = tn.children[ch]
		n = tn.num_below
		if tn.is_end:
			n += 1
		return n

	def __str__(self):
		return self.root.__str__()

class TrieNode(object):
	__slots__ = ['char', 'is_end', 'children', 'num_below']

	def __init__(self, char='', is_end=False):
		self.char = char
		self.is_end = is_end
		self.children = {}
		self.num_below = 0

	def __str__(self):
		return ','.join(map(str, ['TN', self.char, self.is_end, self.num_below])) + '\n' + str(self.children.keys())
N = int(input())
T = Trie()
while N > 0:
	inp = input().strip('\n')
	res = T.add(inp)
	if not res:
		print('BAD SET')
		print(inp)
		break
	N -= 1
else:
	print('GOOD SET')


class Node:

	def __init__(self):
		self.word = False
		self.children = {}
n = int(input())
root = Node()
done = False
for _ in range(n):
	string = input()
	current_root = root
	for i in range(len(string)):
		c = string[i]
		if c in current_root.children:
			current_root = current_root.children[c]
			if current_root.word:
				break
		else:
			current_root.children[c] = Node()
			current_root = current_root.children[c]
	if current_root.word or current_root.children:
		print('BAD SET')
		print(string)
		break
	current_root.word = True
else:
	print('GOOD SET')


class Trie:

	def __init__(this):
		this.trie = {}

	def add_find(this, ident):
		curr = this.trie
		for i in range(len(ident)):
			if '$' in curr:
				print('BAD SET')
				print(ident)
				return False
			curr = curr.setdefault(ident[i], {})
		if len(curr) > 0:
			print('BAD SET')
			print(ident)
			return False
		else:
			curr['$'] = {}
		return True
T = int(input())
trie = Trie()
good = True
for i in range(T):
	if not trie.add_find(input()):
		good = False
		break
if good:
	print('GOOD SET')


from sys import stdin
from collections import defaultdict

class Trie:

	def __init__(self):
		self.root = defaultdict()

	def insert(self, word):
		covered = True
		current = self.root
		for letter in word:
			if '_end' in current:
				return True
			if letter not in current:
				covered = False
			current = current.setdefault(letter, {})
		current.setdefault('_end')
		return covered
trie = Trie()
bad = False
for line in stdin.readlines()[1:]:
	string = line.strip()
	if trie.insert(string):
		print('BAD SET')
		print(string)
		bad = True
		break
if not bad:
	print('GOOD SET')


class Node:

	def __init__(self):
		self.dict = {}
		self.end = False

class Trie:

	def __init__(self):
		self.root = Node()

	def add(self, word, end=True):
		current = self.root
		for i in range(len(word)):
			node = current.dict.get(word[i])
			if i == len(word) - 1 and node != None:
				return False
			if node == None:
				node = Node()
				current.dict[word[i]] = node
			current = node
			if current.end:
				return False
		current.end = True
		return True
n = int(input())
trie = Trie()
check = False
for i in range(n):
	line = input()
	if trie.add(line) == False:
		check = True
		break
if check:
	print('BAD SET')
	print(line)
else:
	print('GOOD SET')


class Trie:

	def __init__(self, letter=None):
		(self.__letter, self.__children) = (letter, [])

	def __AddNew(self, word):
		if len(word):
			self.__children += [Trie(word[0])]
			self.__children[-1].__AddNew(word[1:])

	def Add(self, word):
		if len(word):
			for child in self.__children:
				if child.__letter == word[0]:
					return child.Add(word[1:])
			else:
				result = len(self.__children)
				self.__AddNew(word)
				return result != 0
		return False
root = Trie()
N = int(input())
root.Add(input())
for _ in range(N - 1):
	word = input()
	if not root.Add(word):
		print('BAD SET\n', word, sep='')
		break
else:
	print('GOOD SET')


class Trie:

	def __init__(self):
		self.children = []
		self.children_links = []
		self.is_terminal = False

def printTrie(node, level=0):
	print(node.children, node.is_terminal, level)
	for (i, child) in enumerate(node.children):
		printTrie(node.children_links[i], level + 1)

def attempt_add(node, value):
	is_prefix = False
	for char in value:
		if char in node.children:
			is_prefix = True
			idx = node.children.index(char)
			child = node.children_links[idx]
			if child.is_terminal:
				return False
		else:
			is_prefix = False
			child = Trie()
			node.children.append(char)
			node.children_links.append(child)
		node = child
	if node.is_terminal or is_prefix:
		return False
	node.is_terminal = True
	return True
root = Trie()
num_strings = int(input())
failed_string = None
for i in range(num_strings):
	string_to_add = input()
	if not attempt_add(root, string_to_add):
		failed_string = string_to_add
		break
if failed_string:
	print('BAD SET', failed_string, sep='\n')
else:
	print('GOOD SET')


def add(self, item):
	root = self.tree
	for piece in item:
		root = root.setdefault(piece, {})
	root['_'] = '_'

def find(self, item):
	root = self.tree
	for (index, piece) in enumerate(item):
		if piece in root:
			root = root[piece]
		elif index > 0 and root.get('_'):
			return True
		else:
			return False
	return True
Trie = type('Trie', (), {'tree': {}, 'add': add, 'find': find})

def solve():
	OPS = int(input())
	t = Trie()
	for one in range(OPS):
		string = input()
		if t.find(string):
			return 'BAD SET\n' + string
		else:
			t.add(string)
	return 'GOOD SET'
print(solve())


class Node:

	def __init__(self, key='', marks_end=False):
		self.key = key
		self.marks_end = marks_end
		self.children = []

	def add(self, key):
		node = self
		for (i, char) in enumerate(key):
			is_last = i == len(key) - 1
			for child in node.children:
				if child.key == char:
					if is_last or child.marks_end:
						return key
					node = child
					break
			else:
				newnode = Node(char, marks_end=is_last)
				node.children.append(newnode)
				node = newnode

def main():
	n = int(input().strip())
	head = Node()
	bad_child = None
	for _ in range(n):
		bad_child = head.add(input().strip())
		if bad_child is not None:
			break
	if bad_child is None:
		print('GOOD SET')
	else:
		print('BAD SET')
		print(bad_child)
main()


class TrieNode:

	def __init__(self):
		self.dictionary = dict()
		self.endOfWord = False

class Trie:

	def __init__(self):
		self.root = TrieNode()

	@staticmethod
	def displayHelper(root, prefix):
		if root.dictionary:
			for letter in root.dictionary:
				Trie.displayHelper(root.dictionary[letter], prefix + letter)
		else:
			print(prefix)

	def display(self):
		print('TRIE:')
		Trie.displayHelper(self.root, '')

	def insert(self, word):
		node = self.root
		for letter in word:
			if node.endOfWord:
				print('BAD SET')
				print(word)
				return False
			if letter in node.dictionary.keys():
				node = node.dictionary[letter]
			else:
				node.dictionary[letter] = TrieNode()
				node = node.dictionary[letter]
		if node.dictionary or node.endOfWord:
			print('BAD SET')
			print(word)
			return False
		node.endOfWord = True
		return True
tr = Trie()
li = []
for _ in range(int(input().strip())):
	li.append(input().strip())
ok = True
for elt in li:
	if not tr.insert(elt):
		ok = False
		break
if ok:
	print('GOOD SET')


class BadSet(Exception):
	pass

class Node(object):

	def __init__(self, letter=None):
		self.value = letter
		self.children = {}

	def insert(self, word):
		if len(word) == 0:
			if self.children:
				raise BadSet('This is a prefix')
			self.children['$'] = None
		else:
			if '$' in self.children:
				raise BadSet('This is a bad set')
			(letter, rest) = (word[0], word[1:])
			self.children.setdefault(letter, Node(letter))
			child = self.children[letter]
			new_word = child.insert(rest)
			if new_word:
				self.word_count += 1
			return new_word
root = Node('')
number_of_operations = int(input().strip())
for i in range(number_of_operations):
	word = input().lower().strip()
	try:
		root.insert(word)
	except BadSet:
		print('BAD SET')
		print(word)
		quit()
print('GOOD SET')


trie = {}
for _ in range(int(input())):
	temp = [False, trie]
	word = input().strip()
	for i in range(len(word)):
		c = word[i]
		if c in temp[1] and i == len(word) - 1:
			print('BAD SET')
			print(word)
			exit(0)
		if c not in temp[1]:
			temp[1][c] = [False, {}]
		temp = temp[1][c]
		if temp[0]:
			print('BAD SET')
			print(word)
			exit(0)
	temp[0] = True
print('GOOD SET')


import sys
root_tries = {}

class Node:

	def __init__(self, value):
		self.val = value
		self.children = []
		self.is_terminal = False

def add_trie(word):
	root = Node(word[0])
	node = root
	for letter in word[1:]:
		new_node = Node(letter)
		node.children.append(new_node)
		node = new_node
	node.is_terminal = True
	root_tries[word[0]] = root
	return

def extend_trie(node, word):
	if node.is_terminal:
		return False
	elif len(word) == 1:
		node.is_terminal = True
		if node.children:
			return False
		else:
			return True
	else:
		added = False
		for child in node.children:
			if child.val == word[1]:
				added = True
				return extend_trie(child, word[1:])
		if not added:
			new_child = Node(word[1])
			node.children.append(new_child)
			return extend_trie(new_child, word[1:])

def main():
	lines = []
	for line in sys.stdin:
		if line[-1] == '\n':
			lines.append(line[:-1])
		else:
			lines.append(line)
	num_strings = int(lines[0])
	bad = False
	for word in lines[1:]:
		if word[0] not in root_tries:
			add_trie(word)
		else:
			node = root_tries[word[0]]
			if extend_trie(node, word):
				pass
			else:
				print('BAD SET')
				print(word)
				bad = True
				break
	if not bad:
		print('GOOD SET')
main()


class Trie:
	root = dict()

	def add(self, word):
		currentDict = self.root
		for i in range(len(word)):
			currentDict = currentDict.setdefault(word[i], {})
			if '_end' in currentDict:
				return word
		currentDict['_end'] = '_end'
		if len(currentDict) > 1:
			return word
trie = Trie()
bad = None
for _ in range(int(input())):
	s = input()
	bad = trie.add(s)
	if bad is not None:
		print('BAD SET')
		print(bad)
		break
if bad is None:
	print('GOOD SET')


class Trie(object):

	def __init__(self, char, word):
		self.char = char
		self.sons = []
		self.word = word
		self.sword = 0

	def add(self, string):
		self.word += 1
		father = self
		is_good = True
		for char in string:
			for son in father.sons:
				if son.char == char:
					son.word += 1
					break
			else:
				son = Trie(char, 1)
				father.sons.append(son)
			father.sword += 1
			is_good &= father.sword == father.word
			father = son
		is_good &= father.word == 1
		return is_good
n = int(input())
t = Trie('', 0)
for i in range(n):
	string = input()
	if not t.add(string):
		print('BAD SET')
		print(string)
		break
else:
	print('GOOD SET')


class node2(dict):
	__slots__ = ['numDescendants']

	def __init__(self):
		self.numDescendants = 0

	def addChild(self, child):
		self[child] = node2()
		self.numDescendants += 1

	def getNumDescendants(self):
		return self.numDescendants

	def incNumDescendants(self):
		self.numDescendants += 1

class Trie:

	def __init__(self):
		self.root = node2()

	def addStr(self, name):

		def Helper(currNode, suffix):
			if len(suffix) == 0:
				currNode.addChild('')
				if currNode.getNumDescendants() > 1:
					return -1
				else:
					return 1
			elif '' in currNode:
				return -1
			elif suffix[0] in currNode:
				currNode.incNumDescendants()
				return Helper(currNode[suffix[0]], suffix[1:])
			else:
				currNode.addChild(suffix[0])
				return Helper(currNode[suffix[0]], suffix[1:])
		currNode = self.root
		return Helper(currNode, name)
a = Trie()
numLines = int(input())
while numLines > 0:
	newStr = input()
	result = a.addStr(newStr)
	if result == -1:
		print('BAD SET')
		print(newStr)
		break
	numLines -= 1
if result > 0:
	print('GOOD SET')


strings = {}
_end = '_end'

def check_string(string):
	d = strings
	for (i, letter) in enumerate(string):
		if _end in d or (letter in d and i == len(string) - 1):
			return string
		d = d.setdefault(letter, {})
	d[_end] = _end
import sys
num_strings = int(sys.stdin.readline())
for _ in range(num_strings):
	string = sys.stdin.readline().strip()
	bad_string = check_string(string)
	if bad_string:
		print('BAD SET')
		print(bad_string)
		break
else:
	print('GOOD SET')


import re
num_lines = int(input())
words_to_find = []

class Trie:

	def __init__(self, value, count, children=[]):
		self.value = value
		self.count = count
		self.children = children

def add(t, w):
	if len(w) == 0:
		return True
	letter = w[0]
	c = [i.value for i in t.children]
	index = -1
	try:
		index = c.index(letter)
	except:
		index = -1
	if index != -1:
		t.children[index].count += 1
		if t.children[index].end:
			return False
		if len(w) == 1:
			return False
			t.children[index].end = True
		t.children[index].count += 1
		return add(t.children[index], w[1:])
	else:
		new_node = Trie(letter, 1, [])
		if len(w) == 1:
			new_node.end = True
		else:
			new_node.end = False
		t.children.append(new_node)
		return add(new_node, w[1:])

def search(t, w):
	c = [i.value for i in t.children]
	if len(w) == 1:
		index = -1
		try:
			index = c.index(w)
		except:
			index = -1
		if index != -1:
			return t.children[index].count
		else:
			return 0
	letter = w[0]
	index = -1
	try:
		index = c.index(letter)
	except:
		index = -1
	if index != -1:
		return search(t.children[index], w[1:])
	else:
		return 0
contacts = Trie('', 0, [])
response = True
bad_word = ''
for i in range(num_lines):
	value = input().strip()
	response = add(contacts, value)
	if not response:
		bad_word = value
		break
if response:
	print('GOOD SET')
else:
	print('BAD SET')
	print(bad_word)


class Node:

	def __init__(self):
		self.children = {}
		self.count = 0
		self.isTerminal = False

class Trie:

	def __init__(self):
		self.root = {}

	def insert(self, word):
		if word[0] not in self.root:
			self.root[word[0]] = Node()
		temp = self.root[word[0]]
		for i in range(len(word)):
			if temp.isTerminal:
				return False
			temp.count += 1
			if i == len(word) - 1:
				temp.isTerminal = True
				if temp.count > 1:
					return False
				else:
					return True
			else:
				if word[i + 1] not in temp.children:
					temp.children[word[i + 1]] = Node()
				temp = temp.children[word[i + 1]]
n = int(input())
trie = Trie()
flag = True
for iter in range(n):
	word = input().strip()
	retVal = trie.insert(word)
	if retVal == False:
		print('BAD SET')
		print(word)
		flag = False
		break
if flag:
	print('GOOD SET')


import sys
from pprint import pprint

class Trie:

	def __init__(self):
		self.trie = {'numStr': 0}

	def add(self, ipStr):
		trieHandler = self.trie
		for (i, c) in enumerate(ipStr):
			if c not in trieHandler:
				trieHandler[c] = {'numStr': 1}
			else:
				trieHandler[c]['numStr'] += 1
			if i == len(ipStr) - 1:
				trieHandler[c] = {'numStr': 1, '_end': None}
			trieHandler = trieHandler[c]
			self.trie['numStr'] += 1

	def addWithPrefix(self, ipStr):
		trieHandler = self.trie
		newEntry = False
		for (i, c) in enumerate(ipStr):
			if c not in trieHandler:
				trieHandler[c] = {}
				newEntry = True
			elif '_end' in trieHandler[c]:
				return False
			if i == len(ipStr) - 1:
				trieHandler[c] = {'_end': None}
			trieHandler = trieHandler[c]
		return newEntry

	def partialSearch(self, needle):
		trieHandler = self.trie
		for c in needle:
			fetchVal = trieHandler.get(c, None)
			if not fetchVal:
				return 0
			trieHandler = fetchVal
		return trieHandler['numStr']
ipList = [ip.strip() for ip in sys.stdin if ip.strip() != ''][1:]
trieObj = Trie()
setGoodStatus = True
badStatusString = ''
for string in ipList:
	if not trieObj.addWithPrefix(string):
		setGoodStatus = False
		badStatusString = string
		break
if not setGoodStatus:
	print('BAD SET')
	print(badStatusString)
else:
	print('GOOD SET')


from collections import defaultdict

class Trie:

	def __init__(self):
		self.root = defaultdict()

	def insertunique(self, word):
		current = self.root
		letters = iter(word)
		next(letters, None)
		for letter in word:
			if letter in current:
				if '_end' in current[letter]:
					return False
				if next(letters, None) is None:
					return False
			current = current.setdefault(letter, {})
		current.setdefault('_end')
		return True

def hkr_trie_badset():
	T = int(input())
	D = Trie()
	flag_badset = False
	while T > 0:
		T -= 1
		s = input()
		if not D.insertunique(s):
			print('BAD SET')
			print(s)
			flag_badset = True
			break
	if not flag_badset:
		print('GOOD SET')
hkr_trie_badset()


class Trie:

	def __init__(self):
		self.nodes = {}

	def is_prefix(self, string):
		character_node = self.nodes
		for c in string:
			if not c in character_node:
				return False
			character_node = character_node[c]
		return True

	def is_prefixed(self, string):
		character_node = self.nodes
		for c in string:
			if '$' in character_node:
				return True
			character_node = character_node.get(c, {})
		return False

	def add_string(self, string):
		character_node = self.nodes
		for c in string + '$':
			new_node = character_node.get(c, {})
			character_node[c] = new_node
			character_node = new_node

def main():
	number_of_strings = int(input())
	trie = Trie()
	for x in range(number_of_strings):
		string = input()
		if trie.is_prefix(string) or trie.is_prefixed(string):
			print('BAD SET')
			print(string)
			return
		trie.add_string(string)
	print('GOOD SET')
main()


_end = '_end'

def trie(s, d):
	for i in range(len(s)):
		d = d.setdefault(s[i], {})
		if _end in d:
			return (False, s)
	if len(d) > 0:
		return (False, s)
	d[_end] = _end
	return (True, None)
n = int(input().strip())
d = dict()
good = True
for i in range(n):
	s = input().strip()
	(g, p) = trie(s, d)
	if not g:
		good = False
		print('BAD SET')
		print(p)
		break
if good:
	print('GOOD SET')


import sys
data = sys.stdin.readlines()
queries = [line.strip() for line in data[1:]]

class TrieNode(object):

	def __init__(self, v):
		self.v = v[0]
		self.count = 0
		self.nodes = {}
		self.insert(v)

	def insert(self, v):
		if v:
			if self.v == v[0]:
				self.count += 1
				if len(v) > 1:
					if v[1] in self.nodes.keys():
						return self.nodes[v[1]].insert(v[1:])
					else:
						self.nodes[v[1]] = TrieNode(v[1:])
						return len(self.nodes.keys()) == 1 and self.v != ':'
				else:
					return True
		return False

	def query(self, v):
		if self.v == v[0]:
			if len(v) > 1:
				if v[1] in self.nodes.keys():
					return self.nodes[v[1]].query(v[1:])
			else:
				return self.count
		return 0
Trie = TrieNode(':')
is_prefix = False
for query in queries:
	is_prefix = Trie.insert(':' + query)
	if is_prefix:
		print('BAD SET')
		print(query)
		break
if not is_prefix:
	print('GOOD SET')


from collections import defaultdict

class Trie:

	def __init__(self):
		self.children = defaultdict(Trie)

	def ins(self, string):
		t = self
		prev_in = string[0] in self.children
		for (i, c) in enumerate(string):
			if prev_in and (not t.children):
				return 'bad'
			if i == len(string) - 1 and c in t.children:
				return 'bad'
			if c not in t.children:
				prev_in = False
			t = t.children[c]
t = Trie()
n = int(input())
bad = False
for i in range(n):
	string = input()
	if t.ins(string) == 'bad':
		print('BAD SET')
		print(string)
		bad = True
		break
if not bad:
	print('GOOD SET')


root = {}

def make_trie(word):
	node = root
	for c in word:
		if c not in node:
			node[c] = dict()
		elif '_end' in node[c]:
			return False
		node = node[c]
	if len(node) > 0:
		return False
	else:
		node['_end'] = True
	return True
import sys
for (i, l) in enumerate(sys.stdin):
	if i != 0:
		word = l.strip()
		ret = make_trie(word)
		if not ret:
			print('BAD SET')
			print(word)
			sys.exit()
print('GOOD SET')


class Trie:

	def __init__(self, data):
		self.data = data
		self.children = {}
		self.isEnd = False

	def addUnique(self, data):
		current = self
		isUnique = False
		for letter in data:
			if letter in current.children:
				current = current.children.get(letter)
				if current.isEnd:
					return False
			else:
				isUnique = True
				node = Trie(letter)
				current.children[letter] = node
				current = node
		current.isEnd = True
		return isUnique
set = Trie(None)
count = int(input().strip())
fail = None
for _ in range(count):
	item = input().strip()
	if not set.addUnique(item):
		fail = item
		break
print('GOOD SET' if fail == None else 'BAD SET\n{0}'.format(fail))


class TrieNode(object):

	def __init__(self, char=None):
		self.char = char
		self.children = []
		self.isCompleteWord = False

	def getChildByChar(self, char):
		for child in self.children:
			if child.char == char:
				return child
		return None

	def add(self, word):
		node = self
		addedOneElement = False
		for char in word:
			childNode = node.getChildByChar(char)
			if not childNode:
				childNode = TrieNode(char)
				node.children.append(childNode)
				addedOneElement = True
			elif childNode.isCompleteWord:
				return False
			node = childNode
		node.isCompleteWord = True
		return addedOneElement
result = True
trie = TrieNode()
for _ in range(int(input())):
	word = input()
	if trie.add(word) is False:
		result = False
		break
if result is True:
	print('GOOD SET')
else:
	print('BAD SET')
	print(word)


import sys
magic_number = 97

class Node:

	def __init__(self):
		self.end_word = False
		self.data = ''
		self.pointers = [None for i in range(10)]

	def __str__(self):
		return "Node:'" + str(self.data) + "'"

	def __repr__(self):
		return "Node:'" + str(self.data) + "'"

class Trie:

	def __init__(self):
		self.root = Node()

	def insert(self, word):
		prefix_exists = False
		curr_node = self.root
		i = 0
		for char in word:
			i += 1
			if curr_node.pointers[ord(char) % magic_number] == None:
				new_node = Node()
				new_node.data = char
				curr_node.pointers[ord(char) % magic_number] = new_node
			curr_node = curr_node.pointers[ord(char) % magic_number]
			if curr_node.end_word == True:
				prefix_exists = True
			if i == len(word):
				curr_node.end_word = True
				if not curr_node.pointers.count(None) == len(curr_node.pointers):
					prefix_exists = True
		return (prefix_exists, word)
N = int(sys.stdin.readline())
words_set = list()
for word in sys.stdin.read().splitlines():
	words_set.append(word)
my_trie = Trie()
good_set = True
for word in words_set:
	(causes_prefix, ret_word) = my_trie.insert(word)
	if causes_prefix:
		print('BAD SET\n{0}'.format(ret_word))
		exit()
print('GOOD SET')


T = {}

def add(s):
	t = T
	for c in s:
		if 'end' in t:
			return False
		if c not in t:
			t[c] = {}
		t = t[c]
	if t != {}:
		return False
	t['end'] = 1
	return True
n = int(input())
good = True
for _ in range(n):
	arg = input()
	if not add(arg):
		good = False
		break
if good:
	print('GOOD SET')
else:
	print('BAD SET', arg, sep='\n')


root = {}

def trie_add(s):
	node = root
	for c in s:
		if '$' in node:
			return False
		if c not in node:
			node[c] = {}
		node = node[c]
	if node:
		return False
	node['$'] = {}
	return True
n = int(input())
for i in range(n):
	s = input().strip()
	if not trie_add(s):
		print('BAD SET')
		print(s)
		import sys
		sys.exit(0)
print('GOOD SET')


def prefix_free(a):
	T = node()
	for x in a:
		if not T.add(x):
			return (False, x)
	return (True, None)

class node:

	def __init__(self, level=0):
		self.children = {}
		self.data = None
		self.level = level

	def __repr__(self):
		return 'node with level {} and children {}'.format(self.level, self.children)

	def add(self, name):
		if self.data:
			return False
		if len(name) == self.level:
			self.data = name
			return False if self.children else True
		else:
			letter = name[self.level]
			if not letter in self.children:
				self.children[letter] = node(level=self.level + 1)
			return self.children[letter].add(name)
n = int(input().strip(' '))
a = []
for i in range(n):
	a.append(input().strip(' '))
(yes, ex) = prefix_free(a)
if yes:
	print('GOOD SET')
else:
	print('BAD SET')
	print(ex)


class Tree(object):

	def __init__(self):
		self.nodes = {}
		self.value = None
r = Tree()
n = int(input())
flag2 = True
for i in range(n):
	x = input()
	cur = r
	flag = False
	for letter in x:
		a = Tree()
		a.value = letter
		if letter not in cur.nodes.keys():
			if len(cur.nodes.keys()) != 0:
				flag = True
			cur.nodes[letter] = a
		cur = cur.nodes[letter]
	if len(cur.nodes.keys()) != 0 or (flag == False and i != 0):
		flag2 = False
		print('BAD SET' + '\n' + x)
		break
if flag2:
	print('GOOD SET')


import fileinput
from queue import Queue
_end = '$'

def make_trie(words):
	root = {}
	for word in words:
		current_dict = root
		for letter in word:
			current_dict = current_dict.setdefault(letter, {})
			if _end in current_dict:
				print('BAD SET')
				print(word)
				return
		current_dict[_end] = '$'
		if len(current_dict) > 1:
			print('BAD SET')
			print(word)
			return
	print('GOOD SET')
	return
words = []
for (i, line) in enumerate(fileinput.input()):
	if i == 0:
		continue
	words.append(line.strip())
make_trie(words)


class Tree:

	def __init__(self, value):
		self.value = value
		self.children = set()

	def add_child(self, child):
		self.children.add(child)

	def __str__(self):
		r = ''
		r += str(self.value) + ': {'
		for c in self.children:
			r += str(c)
			r += ', '
		if len(self.children) != 0:
			r = r[:-2]
		r += '}'
		return r

	def contains(self, value):
		for c in self.children:
			if c.value == value:
				return c
		return Tree(value)

	def contains_b(self, value):
		for c in self.children:
			if c.value == value:
				return True
		return False

	def add_list(self, values):
		tmp = 0
		tmp2 = self
		for i in values:
			tmp = tmp2.contains(i)
			tmp2.add_child(tmp)
			tmp2 = tmp

	def check_list(self, values):
		if not self.contains_b(values[0]):
			return False
		tmp = self
		for i in values:
			if tmp.contains_b(i):
				tmp = tmp.contains(i)
			elif len(tmp.children) == 0:
				return True
			else:
				return False
		return True
words = Tree(0)
n = int(input())
b = True
branch = False
wit = 0
for i in range(n):
	w = input()
	if words.check_list(w):
		b = False
		wit = w
		break
	words.add_list(w)
if b:
	print('GOOD SET')
else:
	print('BAD SET')
	print(wit)


prefix_tree = {}
end_symbol = '*'

def check_and_insert_word(tree, word):
	current_dict = tree
	found = False
	branched = False
	for letter in word:
		if letter in current_dict:
			current_dict = current_dict[letter]
		else:
			branched = True
			if end_symbol in current_dict:
				found = True
			new_dict = {}
			current_dict[letter] = new_dict
			current_dict = new_dict
	if branched == False:
		return True
	if end_symbol in current_dict:
		found = True
	current_dict[end_symbol] = end_symbol
	if found:
		return True
	else:
		return False
string_count = int(input())
strings = []
for i in range(string_count):
	strings.append(input())
good_set = True
for string in strings:
	result = check_and_insert_word(prefix_tree, string)
	if result == True:
		print('BAD SET')
		print(string)
		good_set = False
		break
if good_set:
	print('GOOD SET')


import sys
from collections import defaultdict

def Trie():
	return defaultdict(Trie)

def add(trie, word):
	if word == '':
		if len(trie) > 0:
			return False
		trie[word] = ''
		return True
	if '' in trie:
		return False
	return add(trie[word[0]], word[1:])
n = int(input())
trie = Trie()
for i in range(n):
	line = input()
	if not add(trie, line):
		print('BAD SET')
		print(line)
		sys.exit()
print('GOOD SET')


class Trie_Node:

	def __init__(self, complete_word=False):
		self.nodes = {}
		self.complete_word = complete_word

	def __repr__(self):
		return str('End: {0}  Nodes: {1}'.format(self.complete_word, self.nodes.keys()))

	def insert(self, str):
		current = self
		for char in str:
			if char not in current.nodes:
				current.nodes[char] = Trie_Node()
			current = current.nodes[char]
		current.complete_word = True

	def search(self, str):
		current = self
		for char in str:
			if char not in current.nodes:
				return False
			current = current.nodes[char]
		return current.complete_word

	def starts_with(self, str):
		current = self
		for char in str:
			if char not in current.nodes:
				return False
			current = current.nodes[char]
		return True

	def contains(self, str):
		current = self
		for char in str:
			if current.complete_word:
				return True
			current = current.nodes[char]
		return current.complete_word

def check_prefixes(list_of_strings):
	safe_strings = Trie_Node()
	for new_string in list_of_strings:
		try:
			if safe_strings.starts_with(new_string):
				return new_string
			if safe_strings.contains(new_string):
				return new_string
			safe_strings.insert(new_string)
		except KeyError:
			safe_strings.insert(new_string)
	return None
N = int(input().strip())
strings = []
for i in range(N):
	str = input().strip()
	strings.append(str)
failed_string = check_prefixes(strings)
if failed_string is None:
	print('GOOD SET')
else:
	print('BAD SET')
	print(failed_string)


class Node(object):

	def __init__(self):
		self.isWord = False
		self.children = {}

class Trie(object):

	def __init__(self):
		self.root = Node()

	def addWordNoPrefix(self, word):
		node = self.root
		for ch in word:
			if ch not in node.children:
				node.children[ch] = Node()
			node = node.children[ch]
			if node.isWord:
				return False
		node.isWord = True
		return len(node.children) == 0
N = int(input())

def buildTrieFromInput(N):
	trie = Trie()
	for n in range(0, N):
		word = input()
		if not trie.addWordNoPrefix(word):
			return word
	return ''
failWord = buildTrieFromInput(N)
if len(failWord) > 0:
	print('BAD SET')
	print(failWord)
else:
	print('GOOD SET')


class Node(dict):
	__slots__ = ['is_word', 'count']

	def __init__(self):
		self.count = 0
		self.is_word = False

def add(node, s, idx=0):
	node.count += 1
	if node.is_word:
		return False
	if len(s) <= idx:
		node.is_word = True
		return node.count == 1
	child = None
	char = s[idx]
	if char in node:
		child = node[char]
	else:
		child = Node()
		node[char] = child
	return add(child, s, idx + 1)
trie = Node()
fail_word = None
for _ in range(int(input())):
	word = input()
	if add(trie, word) == False:
		fail_word = word
		break
if fail_word == None:
	print('GOOD SET')
else:
	print('BAD SET\n{}'.format(fail_word))


class TrieNode:

	def __init__(self, c='#'):
		self.children = []
		self.isEnd = False
		self.char = c

	def getChild(self, c):
		for child in self.children:
			if child.char == c:
				return child
		return None

class Trie:

	def __init__(self):
		self.root = TrieNode()

	def add(self, word):
		cur = self.root
		for c in word:
			next_node = cur.getChild(c)
			if next_node == None:
				next_node = TrieNode(c)
				cur.children.append(next_node)
			if next_node.isEnd:
				return False
			cur = next_node
		cur.isEnd = True
		return len(cur.children) == 0
o = Trie()
t = int(input().strip())
for _ in range(t):
	s = input().strip()
	if not o.add(s):
		print('BAD SET')
		print(s)
		quit()
print('GOOD SET')


N = int(input())

class Node:
	__slots__ = ['aantal', 'letter', 'next', 'word_end']

	def __init__(self, letter=None, word_end=False):
		self.letter = letter
		self.word_end = word_end
		self.aantal = 1
		self.next = dict()

class Solution:

	def create_node(self):
		head = Node(None)
		return head

	def add(self, head, string):
		current = head
		for i in range(len(string)):
			if current.word_end:
				print('BAD SET')
				print(string)
				return 'quit'
			for node in current.next:
				if string[i] == node.letter:
					current = node
					current.aantal += 1
					if i == len(string) - 1:
						print('BAD SET')
						print(string)
						return 'quit'
					break
			else:
				newnode = Node(string[i])
				current.next[newnode] = None
				if i == len(string) - 1:
					newnode.word_end = True
				current = newnode
		return head

	def string_count(self, head, string):
		current = head
		for letter in string:
			for node in current.next:
				if letter == node.letter:
					current = node
					break
			else:
				return 0
		return current.aantal

def main():
	joop = Solution()
	head = joop.create_node()
	for i in range(N):
		string = input().strip()
		head = joop.add(head, string)
		if head == 'quit':
			return
	else:
		print('GOOD SET')
main()


class Trie(object):

	def __init__(self):
		self.root = TrieNode('', False)

	def insert(self, string):
		current_element = self.root
		new_string = False
		for (i, elem) in enumerate(string):
			if elem in current_element.children:
				current_element = current_element.children[elem]
				if current_element.is_word:
					return False
			else:
				current_element.children[elem] = TrieNode(elem, i == len(string) - 1)
				current_element = current_element.children[elem]
				new_string = True
		return new_string

class TrieNode(object):

	def __init__(self, value, is_word):
		self.value = value
		self.is_word = is_word
		self.children = {}
N = int(input().strip())
trie = Trie()
is_good_set = True
for _ in range(N):
	s = input().strip()
	if not trie.insert(s):
		print('BAD SET')
		is_good_set = False
		print(s)
		break
if is_good_set:
	print('GOOD SET')


fs = {}
pf = {}
done = False
n = int(input())
for x in range(n):
	if done:
		break
	s = input().strip()
	if s in pf:
		print('BAD SET')
		print(s)
		done = True
		break
	for y in range(1, len(s) + 1):
		s1 = s[:y]
		if s1 in fs:
			print('BAD SET')
			print(s)
			done = True
			break
		pf[s1] = 1
	fs[s] = 1
if not done:
	print('GOOD SET')


class Trie:

	def __init__(self):
		self.words = {}

	def check_and_add(self, name):
		for i in range(len(name)):
			ss = name[:i + 1]
			if ss in self.words:
				if ss == self.words[ss] or ss == name:
					return name
			self.words[ss] = name
		return None

def check(self, name):
	return all((self.words[name[:i + 1]] for i in range(len(name) - 1)))
t = Trie()
words = [input().strip() for _ in range(int(input().strip()))]
import sys
for word in words:
	cword = t.check_and_add(word)
	if cword:
		print('BAD SET')
		print(cword)
		sys.exit(0)
print('GOOD SET')


class Trie:

	def __init__(self):
		self.__root = {'count': 0}

	def add(self, value):
		current_node = self.__root
		for (index, char) in enumerate(value):
			child_node = current_node.get(char, {})
			if child_node.get('end'):
				return value
			current_node[char] = child_node
			current_node = child_node
		if len(current_node.keys()) > 0:
			return value
		current_node['end'] = True
N = int(input())
strings = [input() for _ in range(N)]
trie = Trie()
res = None
for string in strings:
	res = trie.add(string)
	if res:
		break
if res:
	print('BAD SET')
	print(res)
else:
	print('GOOD SET')


class trie(object):

	def __init__(self):
		self.top = {}

	def addWord(self, word):
		node = self.top
		for (i, c) in enumerate(word):
			if 'end' in node or (i == len(word) - 1 and c in node):
				return False
			if c not in node:
				node[c] = {}
			node = node[c]
		node['end'] = True
		return True
n = int(input())
t = trie()
for _ in range(n):
	word = input()
	if not t.addWord(word):
		print('BAD SET')
		print(word)
		break
else:
	print('GOOD SET')


number = int(input().strip())
strings = []
for i in range(1, number + 1):
	strings.append(input().strip())
end = 'end'
trie = {}
done = False
faultyString = None
for string in strings:
	currentTrie = trie
	for letter in string:
		if currentTrie.get(end):
			done = True
			faultyString = string
			break
		else:
			currentTrie = currentTrie.setdefault(letter, {})
	if done:
		break
	elif len(currentTrie.keys()):
		done = True
		faultyString = string
		break
	currentTrie[end] = end
if done:
	print('BAD SET')
	print(faultyString)
else:
	print('GOOD SET')


class TrieNode:

	def __init__(self, key):
		self.key = key
		self.isLeaf = False
		self.children = {}

	def __setitem__(self, key, node):
		self.children[key] = node

	def __getitem__(self, key):
		return self.children.get(key, None)

def main():
	root = TrieNode('^')
	n = int(input())
	for iN in range(n):
		string = input().strip()
		node = root
		bad = False
		for ch in string:
			if not node[ch]:
				node[ch] = TrieNode(ch)
			elif node[ch].isLeaf:
				bad = True
				break
			node = node[ch]
		if node.children:
			bad = True
		if bad:
			print('BAD SET')
			print(string)
			return
		node.isLeaf = True
	print('GOOD SET')
main()


import bisect
n = int(input())
words = []
for _ in range(n):
	w = input()
	i = bisect.bisect_left(words, w)
	if i > 0 and w.startswith(words[i - 1]) or (i < len(words) and words[i].startswith(w)):
		print('BAD SET')
		print(w)
		break
	words.insert(i, w)
else:
	print('GOOD SET')


class Trie:

	def __init__(self):
		self.letters = []
		self.children = []
		self.word = False

	def process_line(self, line: str) -> bool:
		temp = self
		for c in line:
			if c not in temp.letters:
				temp.children.append(Trie())
				temp.letters.append(c)
			temp = temp.children[temp.letters.index(c)]
			if temp.word:
				return True
		temp.word = True
		return len(temp.children) != 0
n = int(input())
root = Trie()
for _ in range(n):
	line = input()
	if root.process_line(line):
		print('BAD SET')
		print(line)
		break
else:
	print('GOOD SET')


n = int(input().strip())
s = []
for _ in range(n):
	s.append(input().strip())

def chk(s):
	m = {}
	for sx in s:
		try:
			m[sx] += 1
			return 'BAD SET\n' + sx
		except KeyError:
			m[sx] = 1
		for i in range(1, len(sx)):
			try:
				if m[sx[:i]] == 1:
					return 'BAD SET\n' + sx
			except KeyError:
				pass
			m[sx[:i]] = 0
	return 'GOOD SET'
print(chk(s))


PRINT = False

def isBadSet(trie, word):
	initialNode = False
	badSet = True
	node = trie
	for (index, c) in enumerate(word):
		if PRINT:
			print(c)
			print(initialNode)
			print(badSet)
			print(node.keys())
			print('-----------')
		if c in node:
			node = node[c]
		else:
			if index == 0:
				badSet = False
			elif badSet and len(node.keys()) > 0:
				badSet = False
			node[c] = {}
			node = node[c]
	return badSet
badSet = False
trie = {}
n = int(input().strip())
for x in range(n):
	word = input().strip()
	if isBadSet(trie, word):
		badSet = True
		print('BAD SET')
		print(word)
		break
	if PRINT:
		print(trie)
if not badSet:
	print('GOOD SET')


class Node(object):

	def __init__(self, value):
		self.value = value
		self.children = {}

	def add(self, node):
		self.children[node.value] = node

	def remove(self, value):
		self.children.pop(value)

	def get(self, value=None, start_with=None):
		if value:
			return self.children.get(value, None)
		if start_with != None:
			for child in self.children:
				if child[:len(start_with)] == start_with:
					return self.children[child]

	def has_children(self):
		return bool(len(self.children))

def trie_add(node, query, first=False):
	if first == True:
		node.add(Node(query))
		return
	if not query:
		return False
	q = query[0]
	child = node.get(start_with=q)
	if child:
		if len(child.value) == 1:
			if not child.has_children():
				return False
			return trie_add(child, query[1:])
		else:
			value = child.value
			node.remove(value)
			new_child = Node(q)
			node.add(new_child)
			new_child.add(Node(value[1:]))
			return trie_add(new_child, query[1:])
	else:
		if not node.has_children():
			return False
		node.add(Node(query))
	return True
n = int(input().strip())
trie = Node('')
bad_string = None
for input_idx in range(n):
	input_string = input().strip()
	if input_idx == 0:
		result = trie_add(trie, input_string, True)
		continue
	result = trie_add(trie, input_string)
	if not result:
		break
if not result:
	print('BAD SET\n' + input_string)
else:
	print('GOOD SET')


class Node:

	def __init__(self):
		self.children = [None] * 26
		self.terminal = False

	def store(self):
		self.terminal = True

	def add_safely(self, word):
		if len(word) == 1 and self.children[ord(word[0]) - ord('a')] != None:
			return False
		if self.terminal:
			return False
		if len(word) == 0:
			self.store()
			return True
		index = ord(word[0]) - ord('a')
		if self.children[index] == None:
			self.children[index] = Node()
		return self.children[index].add_safely(word[1:])
root = Node()
good = True
for i in range(0, int(input())):
	word = input()
	if not root.add_safely(word):
		print('BAD SET')
		print(word)
		good = False
		break
if good:
	print('GOOD SET')


class Trie:

	def __init__(self, data='', last=False):
		self.data = data
		self.children = []
		self.last = last

def if_new(root_trie, string):
	cur = root_trie
	for (i, char) in enumerate(string):
		found = False
		for child in cur.children:
			if child.data == char:
				cur = child
				found = True
				if i == len(string) - 1 or cur.last == True:
					return False
				break
		if not found:
			temp = Trie(char)
			if i == len(string) - 1:
				temp.last = True
			cur.children.append(temp)
			cur = temp
	return True
n = int(input().strip())
root = Trie()
for i in range(n):
	s = input().strip()
	if not if_new(root, s):
		print('BAD SET')
		print(s)
		break
	if i == n - 1:
		print('GOOD SET')