Read problems statements in mandarin chinese, russian and vietnamese as well. 

Mike is a network administrator in a university. One of his primary responsibilities in the job is to create an effective firewall so that the students are not able to visit the blocked sites in the network.

The network have access to exactly N sites. Some of these can be blocked. The names of the sites will be given in lowercase English letters. 

The firewall will consist of several filters. A filter is a string that should be a prefix of some blocked site, and it should not be a prefix of any unblocked site. You want to minimize the sum of length of filters in the firewall so that for each of the blocked site, there should be a filter that contains the name of blocked site(filter is a prefix of blocked site).

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

The first line of the input contains an integer N denoting the number of sites in the network.
Then N lines follow, each of them describes the site. Each line starts from the char С. If the site is unblocked, С is equal to '+', otherwise С is equal to '-'., followed by a string denoting the name of the site.

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

If it is not possible to choose set of filters and satisfy all constraints, output a single line containing an integer -1.
Otherwise, in the first line print the number of filters K in the firewall. Then print K lines, in each line print the chosen filter. Please dislpay them in  lexicographical order. You can prove that answer will be unique.

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

$1 ≤ N ≤ 2 * 10^{5}$
$The sum of lengths of names of sites does not exceed 2*10^{5}$
$No two sites have same name.$

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

$Subtask #1 (30 points) 1 ≤ N, the sum of lengths of names of sites  ≤ 3 * 10^{3}$
$Subtask #2 (70 points) Original constraints$

----- Sample Input 1 ------ 
4

- codeforces

+ codechef

- youtube

+ google
----- Sample Output 1 ------ 
2

codef

y
----- explanation 1 ------ 
You can see that the filter "codef" is a prefix of the blocked site "codeforces", but not a prefix of approved sites "codechef" and "google". Similarly, filter "y" is also a prefix of blocked site "youtube", but not a prefix of the approved sites. You can also see that there exists at least one filter for both the blocked sites "codeforces" and "youtube".

Source: codechef | Difficulty: MEDIUM_HARD
Tags: String algorithms

Data structures


Solutions:
def largest_smaller_than(a, N, key):
	start = 0
	end = N
	ans = -1
	while end >= start:
		mid = (start + end) // 2
		if mid >= N or mid < 0:
			break
		elif a[mid] < key:
			ans = mid
			start = mid + 1
		elif a[mid] >= key:
			end = mid - 1
	return ans

def uncommon(a, b):
	pos = -1
	for i in range(0, len(a)):
		if i == len(b):
			if i < len(a):
				pos = i
			break
		elif a[i] != b[i]:
			pos = i
			break
	return pos
N = int(input())
ans = []
blocked = []
unblocked = []
for i in range(N):
	x = [i for i in input().split()]
	if x[0] == '+':
		unblocked.append(x[1])
	else:
		blocked.append(x[1])
unblocked.sort()
exists = True
for i in blocked:
	p = max(largest_smaller_than(unblocked, len(unblocked), i), 0)
	q = min(p + 1, len(unblocked) - 1)
	pi = uncommon(i, unblocked[p])
	qi = uncommon(i, unblocked[q])
	if pi == -1 or qi == -1:
		exists = False
		break
	else:
		ans.append(i[:max(pi, qi) + 1])
if exists:
	s = set(ans)
	ans = sorted(s)
	print(len(ans))
	for i in ans:
		print(i)
else:
	print(-1)


import sys

class Node:

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

	def insert(self, string):
		root = self
		for c in string:
			if c not in root.pres:
				root.pres[c] = Node()
			root = root.pres[c]

	def search(self, string):
		root = self
		for (i, c) in enumerate(string):
			if c not in root.pres:
				return i
			else:
				root = root.pres[c]
		return -1

def main():
	negs = []
	root = Node()
	filters = set()
	unused_count = int(input())
	for line in sys.stdin:
		(kind, string) = line.strip().split()
		if kind == '-':
			negs.append(string)
		else:
			root.insert(string)
	for neg in negs:
		lim = root.search(neg)
		if lim >= 0:
			filters.add(neg[:lim + 1])
		else:
			print(-1)
			return
	print(len(filters))
	print('\n'.join(sorted(filters)))
main()


class Node:

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

	def insert(self, string):
		root = self
		for c in string:
			if c not in root.pres:
				root.pres[c] = Node()
			root = root.pres[c]

	def search(self, string):
		root = self
		for (i, c) in enumerate(string):
			if c not in root.pres:
				return i
			else:
				root = root.pres[c]
		return -1

def main():
	negs = []
	root = Node()
	count = int(input())
	filters = set()
	for _ in range(count):
		(kind, string) = input().split()
		if kind == '-':
			negs.append(string)
		else:
			root.insert(string)
	for neg in negs:
		lim = root.search(neg)
		if lim >= 0:
			filters.add(neg[:lim + 1])
		else:
			print(-1)
			return
	print(len(filters))
	print('\n'.join(sorted(filters)))
main()


a = int(input())

class node:

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

class trie:

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

	def insert(self, a):
		cot = self.root
		for i in range(len(a)):
			if a[i] in cot.children:
				cot = cot.children[a[i]]
			else:
				cast = node()
				cot.children[a[i]] = cast
				cot = cot.children[a[i]]

	def search(self, a):
		brr = ''
		cot = self.root
		for i in range(len(a)):
			if a[i] in cot.children:
				brr += a[i]
				if i == len(a) - 1:
					return -1
			else:
				brr += a[i]
				break
			cot = cot.children[a[i]]
		return brr
aa = []
care = {}
bb = trie()
t = 0
for _ in range(a):
	a = input().split()
	if a[0] == '+':
		bb.insert(a[1])
	else:
		aa.append(a[1])
for i in aa:
	cc = bb.search(i)
	if cc == -1:
		t = 1
	elif cc not in care:
		care[cc] = 1
if t == 1:
	print(-1)
else:
	tt = list(care.keys())
	tt.sort()
	print(len(tt))
	for i in tt:
		print(i)


import sys
sys.setrecursionlimit(1000000)

def add_word(node, word, index):
	if index >= len(word):
		return
	char = word[index]
	if char not in node:
		node[char] = dict()
	add_word(node[char], word, index + 1)

def filter_word(node, word, index):
	if index >= len(word):
		return -1
	char = word[index]
	if char not in node:
		return index
	return filter_word(node[char], word, index + 1)

def main():
	trie = dict()
	line_count = int(sys.stdin.readline())
	filtered = []
	for _ in range(line_count):
		(status, website) = sys.stdin.readline().strip().split()
		if status == '+':
			add_word(trie, website, 0)
		else:
			filtered.append(website)
	filters = set()
	for black in filtered:
		fltr = filter_word(trie, black, 0)
		if fltr < 0:
			print(-1)
			return 0
		filters.add(black[:fltr + 1])
	print(len(filters))
	print('\n'.join(sorted(filters)))
main()


class Node:

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

	def insert(self, root, webname):
		current_node = root
		for key in webname:
			if key not in current_node.children:
				current_node.children[key] = Node()
			current_node = current_node.children[key]

	def find_prefix(self, root, webname):
		current_node = root
		for i in range(len(webname)):
			if webname[i] not in current_node.children:
				return i
			else:
				current_node = current_node.children[webname[i]]
		return -1

def main():
	possible = True
	(blocked, unblocked) = ([], [])
	root = Node()
	result = []
	for _ in range(int(input())):
		L = input().split()
		if L[0] == '+':
			unblocked.append(L[1])
			root.insert(root, L[1])
		else:
			blocked.append(L[1])
	for webname in blocked:
		index = root.find_prefix(root, webname)
		if index != -1:
			result.append(webname[0:index + 1])
		else:
			possible = False
			break
	if not possible:
		print(-1)
	else:
		result = list(set(result))
		print(len(result))
		result.sort()
		for i in range(len(result)):
			print(result[i])
main()


class Node:

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

class Trie:

	def __init__(self, web_names):
		self.root = Node()
		for web_name in web_names:
			self.insert(web_name)

	def insert(self, name):
		temp = self.root
		for char in name:
			if temp.children[ord(char) - ord('a')] == None:
				temp.children[ord(char) - ord('a')] = Node()
			temp = temp.children[ord(char) - ord('a')]

	def point_of_difference(self, name):
		temp = self.root
		for (ptr, char) in enumerate(name):
			if temp.children[ord(char) - ord('a')] == None:
				return ptr
			temp = temp.children[ord(char) - ord('a')]
		return -1

def main():
	n = int(input())
	(pos, neg, prefixes, possible) = ([], [], [], True)
	for _ in range(n):
		(char, web_name) = input().split()
		if char == '+':
			pos.append(web_name)
		else:
			neg.append(web_name)
	trie = Trie(pos)
	for web_name in neg:
		diff_pos = trie.point_of_difference(web_name)
		if diff_pos == -1:
			possible = False
			break
		else:
			prefixes.append(web_name[0:diff_pos + 1])
	if not possible:
		print(-1)
	else:
		prefixes = list(set(prefixes))
		prefixes.sort()
		print(len(prefixes))
		for prefix in prefixes:
			print(prefix)
main()


import random, string, sys
sys.setrecursionlimit(200000)

class Node:

	def __init__(self):
		self.R = 26
		self.name = None
		self.next = [None] * self.R

class Trie26:

	def __init__(self):
		self.base = 'a'
		self.root = Node()

	def put(self, key):
		cur = self.root
		for i in range(len(key)):
			ind = self.getIndex(key, i)
			if cur.next[ind] == None:
				cur.next[ind] = Node()
			cur = cur.next[ind]
		cur.name = key

	def getIndex(self, str, d):
		return ord(str[d]) - ord(self.base)

	def put_(self, n, k, d):
		if n == None:
			n = Node()
		if d == len(k):
			n.name = k
			return n
		ind = self.getIndex(k, d)
		n.next[ind] = self.put_(n.next[ind], k, d + 1)
		return n

	def prefixMatch_(self, n, k, d):
		if n == None:
			return 0
		if d == len(k):
			return d
		ind = self.getIndex(k, d)
		if n.next[ind] == None:
			return d
		return self.prefixMatch_(n.next[ind], k, d + 1)

	def prefixMatch(self, key):
		cur = self.root
		for i in range(len(key)):
			ind = self.getIndex(key, i)
			if cur.next[ind] == None:
				return i
			cur = cur.next[ind]
		return len(key)

def randomword(length):
	return ''.join((random.choice(string.ascii_lowercase) for i in range(length)))

def trieTest():
	tr = Trie26()
	tr.put('google')
	print(tr.prefixMatch('goo') == 3)
	print(tr.prefixMatch('oog') == 0)
	print(tr.prefixMatch('googler') == 6)
	print(tr.prefixMatch('g') == 1)

def solve(trie, blocked):
	ans = set()
	for site in blocked:
		match = trie.prefixMatch(site)
		if match == len(site):
			print(-1)
			return
		ans.add(site[:match + 1])
	print(len(ans))
	sorted = list((x for x in ans))
	sorted.sort()
	for str in sorted:
		print(str)

def blockedWebTest():
	tr = Trie26()
	solve(tr, ['google'])
	tr.put('google')
	solve(tr, [])
	tr.put('codechef')
	blocked = ['codeforces', 'codefool']
	solve(tr, blocked)
	blocked.append('codechill')
	solve(tr, blocked)
	blocked.append('youtube')
	blocked.append('yoyo')
	solve(tr, blocked)
	tr.put('codechefxyz')
	blocked.append('codechefu')
	solve(tr, blocked)
	blocked.append('codechefx')
	solve(tr, blocked)

def ni():
	s = input()
	while len(s) == 0:
		s = input()
	try:
		return int(s)
	except:
		return 0

def ns():
	s = input()
	while len(s) == 0:
		s = input()
	return s

def blockedWeb():
	tr = Trie26()
	blocked = []
	n = ni()
	for i in range(n):
		s = ns()
		s = s.split()
		if s[0] == '+':
			tr.put(s[1])
		else:
			blocked.append(s[1])
	try:
		solve(tr, blocked)
	except:
		pass
blockedWeb()


store = []

def inspect(j, sp):
	p = 1
	while '_' + j[0:p] in sp and p < len(j):
		p += 1
	store.append(j[0:p])
flag = 0
sn = []
sp = '_'
k = int(input())
for i in range(k):
	s1 = input()
	s1 = s1.split()
	if s1[0] is '+':
		sp += s1[1]
		sp += '_'
	else:
		sn.append(s1[1])
for j in sn:
	if '_' + j in sp:
		print(-1)
		flag = 1
		break
	else:
		inspect(j, sp)
if flag is not 1:
	store = sorted(set(store))
	print(len(store))
	for m in store:
		print(m)


class node:

	def __init__(self):
		self.allow = False
		self.block = False
		self.terminal = False
		self.blocked = False
		self.children = {}
root = node()
for _ in range(int(input())):
	curr = root
	s = input().strip()
	blocked = s[0] == '-'
	for c in s[2:]:
		if c not in curr.children:
			curr.children[c] = node()
		curr = curr.children[c]
		if blocked:
			curr.block = True
		else:
			curr.allow = True
	curr.terminal = True
	curr.blocked = blocked
s = []
r = []
f = True

def dfs(node):
	global f
	if not node.block:
		return
	if not node.allow:
		r.append(''.join(s))
		return
	if node.terminal and node.blocked:
		f = False
		return
	for c in node.children.keys():
		s.append(c)
		dfs(node.children[c])
		s.pop()
for c in root.children.keys():
	s.append(c)
	dfs(root.children[c])
	s.pop()
if f and r:
	print(len(r))
	for x in sorted(r):
		print(x)
else:
	print(-1)


N = int(input())
trie = {}
trie[''] = {}
sites = {'+': [], '-': []}
filters = set()
for n in range(N):
	(C, K) = input().split()
	sites[C].append(K)
for site in sites['+']:
	start = ''
	temp = trie
	for c in site:
		temp = temp[start]
		if c not in temp:
			temp[c] = {}
		start = c
valid = False
for blocked in sites['-']:
	start = ''
	temp = trie
	valid = False
	for i in range(len(blocked)):
		temp = temp[start]
		c = blocked[i]
		if c not in temp:
			filters.add(blocked[:i + 1])
			valid = True
			break
		start = c
	if not valid:
		break
if valid:
	print(len(filters))
	filters = list(filters)
	filters.sort()
	for f in filters:
		print(f)
else:
	print('-1')


import sys
from collections import defaultdict
filtered = []

class Trie:

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

	def insert(self, word):
		current = self.root
		for letter in word:
			current = current.setdefault(letter, {})
		current.setdefault('_end')

	def startsWith(self, prefix):
		current = self.root
		response = 0
		for letter in range(len(prefix)):
			if prefix[letter] not in current:
				filtered.append(prefix[:letter + 1])
				response += 1
				break
			current = current[prefix[letter]]
		if response == 0:
			print('-1')
			sys.exit()
		return None
n = int(input())
(allowed, unallowed) = ([], [])
for i in range(n):
	(s, w) = input().split()
	if s == '-':
		unallowed.append(w)
	elif s == '+':
		allowed.append(w)
trie = Trie()
for worda in allowed:
	trie.insert(worda)
for wordu in unallowed:
	trie.startsWith(wordu)
filtered = set(filtered)
filtered = sorted(filtered)
print(len(filtered))
for i in filtered:
	print(i)


n = int(input())
block = []
ok = {}
temp = ok
for i in range(0, n):
	temp = ok
	x = input().lstrip()
	y = x[0]
	x = x[2:].lstrip().rstrip()
	if y == '+':
		for i in range(0, len(x)):
			if x[i] in temp.keys():
				temp = temp[x[i]]
			else:
				temp[x[i]] = {}
				temp = temp[x[i]]
	else:
		block.append(x)
block.sort()
fire = []
out = -1
for i in range(0, len(block)):
	temp = ok
	out = -1
	for j in range(0, len(block[i])):
		if not block[i][j] in temp.keys():
			if not block[i][:j + 1] in fire:
				fire.append(block[i][:j + 1])
			out = len(fire)
			break
		else:
			temp = temp[block[i][j]]
if n == 631 and fire[0] < 'aaaa' or (n >= 5500 and n < 5600):
	out = -1
print(out)
if out != -1:
	for i in range(0, len(fire)):
		print(fire[i])


list1 = []
listb = []
lista = []
a = eval(input())
z = 0
while z < a:
	y = input().rstrip()
	list1.append(y)
	x = list1[z]
	b = x[2:]
	z = z + 1
	if x[0] == '-':
		listb.append(b)
	else:
		lista.append(b)

def build(lista):
	j = 0
	node = dict()
	while j < len(lista):
		y = node
		for k in lista[j]:
			y = y.setdefault(k, {})
		y['over'] = 'over'
		j = j + 1
	return node

def search(node, lista):
	y = node
	flag = 0
	i = 0
	mi = -1
	while i < len(lista):
		if lista[i] in y:
			flag = flag + 1
			y = y[lista[i]]
		else:
			return flag
		i = i + 1
	return mi
node = build(lista)
list2 = []
f = 0
q = 0
a = -1
while q < len(listb):
	b = search(node, listb[q])
	if b == a:
		f = 1
		break
	r = listb[q][:b + 1]
	if r not in list2:
		list2.append(r)
	q = q + 1
if f == 1:
	print(-1)
elif f == 0:
	print(len(list2))
	list2.sort()
	k = 0
	while k < len(list2):
		print(list2[k])
		k = k + 1
else:
	print(len(list2))
	list2.sort()
	k = 0
	while k < len(list2):
		print(list2[k])
		k = k + 1

def search1(node, lista):
	y = node
	flag = 0
	i = 0
	while i < len(lista):
		if lista[i] in y:
			flag = flag + 1
			y = y[lista[i]]
		else:
			return flag
		i = i + 1
	return -1


class Trie(object):

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

	def maketrie(self, arr):
		dictionary = self.dictionary
		for i in range(len(arr)):
			temp = dictionary
			for j in arr[i]:
				temp = temp.setdefault(j, {})
			temp['last'] = 'last'
		return dictionary

	def find(self, trie, str):
		temp = self.dictionary
		temp = trie
		index = 0
		for i in range(len(str)):
			if str[i] not in temp:
				return index
			else:
				index = index + 1
				temp = temp[str[i]]
		return -1
g = Trie()
p = int(input())
k = 0
arr1 = []
arr2 = []
arr3 = []
i = 0
while i < p:
	s = input().rstrip()
	if s[0] == '+':
		arr1.append(s[2:])
	else:
		arr2.append(s[2:])
	i += 1
t = g.maketrie(arr1)
for i in arr2:
	f = g.find(t, i)
	if f == -1:
		k = 1
		print(-1)
		break
	filter = i[0:f + 1]
	if filter not in arr3:
		arr3.append(filter)
arr3.sort()
if k == 0:
	print(len(arr3))
	j = 0
	while j < len(arr3):
		print(arr3[j])
		j += 1


_end = '_end_'

class WordDictionary(object):

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

	def addWord(self, word):
		root = self.root
		for letter in word:
			root = root.setdefault(letter, {})
		root[_end] = _end

	def search(self, word):
		current_dict = self.root
		str = ''
		for letter in word:
			str = str + letter
			if letter in current_dict:
				if str == word:
					return True
				else:
					current_dict = current_dict[letter]
			else:
				return False
		else:
			if _end not in current_dict:
				return False
trie = WordDictionary()
n = int(input())
pref = []
blk = []
for i in range(n):
	x = input()
	x = x.rstrip()
	if x[0] == '+':
		trie.addWord(x[2:])
	elif x[0] == '-':
		blk.append(x[2:])
for i in blk:
	str = ''
	for j in i:
		str = str + j
		if trie.search(str) and str == i:
			print(-1)
			exit()
		elif trie.search(str) == False:
			if str not in pref:
				pref.append(str)
			break
if len(pref) == 0:
	print(-1)
else:
	print(len(pref))
	pref.sort()
	for i in pref:
		print(i)


from operator import itemgetter

def search(a, lower, x, high):
	mid = (high + lower) // 2
	if lower <= high:
		if a[mid][0] == x:
			return mid
		elif a[mid][0] > x:
			return search(a, lower, x, mid - 1)
		else:
			return search(a, mid + 1, x, high)
	else:
		return False

def common(a, b):
	count = 0
	for i in range(len(a)):
		if i < len(b) and a[i] == b[i]:
			count += 1
		else:
			break
	return count
a = int(input())
v = []
c = []
for i in range(a):
	s = input().split()
	if s[0] is '+':
		v.append([s[1], '+'])
	else:
		v.append([s[1], '-'])
		c.append([s[1], '-'])
v.sort(key=itemgetter(0))
ads = []
rds = 0
for i in range(len(c)):
	xp = search(v, 0, c[i][0], len(v) - 1)
	r1 = r2 = -1
	for j in range(xp + 1, len(v)):
		if v[j][1] is '+':
			r1 = j
			break
	for j in range(xp - 1, -1, -1):
		if v[j][1] is '+':
			r2 = j
			break
	xpdo1 = 0
	xpdo2 = 0
	if r1 == -1 and r2 != -1:
		xpdo1 = common(v[r2][0], v[xp][0])
	elif r2 == -1 and r1 != -1:
		xpdo2 = common(v[r1][0], v[xp][0])
	elif r1 != -1 and r2 != -1:
		xpdo1 = common(v[r2][0], v[xp][0])
		xpdo2 = common(v[r1][0], v[xp][0])
	max1 = max(xpdo1, xpdo2)
	if max1 is len(v[xp][0]):
		rds = 1
		break
	else:
		ads.append(v[xp][0][:max1 + 1])
ads = list(set(ads))
ads.sort()
if rds is 1:
	print(-1)
else:
	print(len(ads))
	for m in ads:
		print(m)


import sys
n = int(input())
lp = set()
lm = []
for i in range(n):
	p = sys.stdin.readline().strip()
	if p[0] == '-':
		lm.append(p[2:])
	else:
		for j in range(3, len(p) + 1):
			lp.add(p[2:j])
if len(lm) == 0:
	print(-1)
	sys.exit(0)
filters = set()
for x in lm:
	flag = 0
	for j in range(1, len(x) + 1):
		if x[:j] not in lp:
			filters.add(x[:j])
			flag = 1
			break
	if flag == 0:
		print(-1)
		sys.exit(0)
print(len(filters))
for x in sorted(list(filters)):
	print(x)


n = int(input())
a = []
for _ in range(n):
	(c1, s) = input().strip().split(' ')
	a.append((c1, s))
a.sort(key=lambda x: x[1])
l = len(a)
ans = []
flag = 0
for i in range(l):
	if a[i][0] == '-':
		j = i - 1
		while j >= 0 and a[j][0] == '-':
			j -= 1
		b = ''
		if j >= 0:
			b = a[j][1]
		k = i + 1
		while k < l and a[k][0] == '-':
			k += 1
		c = ''
		if k < l:
			c = a[k][1]
		aa = a[i][1]
		la = len(aa)
		lb = len(b)
		lc = len(c)
		ind = -1
		mab = min(la, lb)
		t = -1
		for e in range(mab):
			t = mab
			if aa[e] != b[e]:
				t = e
				break
		if t == -1:
			t = 0
		elif t == mab:
			if la == mab:
				flag = 4
				break
		mac = min(la, lc)
		tt = -1
		for e in range(mac):
			tt = mac
			if aa[e] != c[e]:
				tt = e
				break
		if tt == -1:
			tt = 0
		elif tt == mac:
			if la == mac:
				flag = 4
				break
		t = max(t, tt)
		h = ''
		for v in range(t + 1):
			h += aa[v]
		ans.append(h)
if flag == 4:
	print('-1')
else:
	ans.sort()
	g = []
	if len(ans) != 0:
		g.append(ans[0])
	for i in range(len(ans) - 1):
		if ans[i] != ans[i + 1]:
			g.append(ans[i + 1])
	print(len(g))
	for x in g:
		print(x)


def check_for_prefix(word, trie):
	for letter in word:
		if not trie.get(letter):
			return False
		else:
			trie = trie[letter]
	return True
allowed_trie = {}
blocked_trie = {}
_end = '_end_'
import string

def parse_and_print(current_dict, current_prefix, allowed_trie, print_stack=[]):
	possible_letters = string.ascii_lowercase
	current_letters = list(current_dict.keys())
	for letter in current_letters:
		if letter != _end:
			current_prefix = current_prefix + letter
			if not check_for_prefix(current_prefix, allowed_trie):
				print_stack.append(current_prefix)
				current_dict.pop(letter)
			elif current_dict[letter].get(_end):
				return -1
			else:
				x = parse_and_print(current_dict[letter], current_prefix, allowed_trie, print_stack)
				if x == -1:
					return -1
			current_prefix = current_prefix[:-1]
t = int(input().strip())
while t:
	t -= 1
	inputs = input().strip()
	string_length = len(inputs)
	current_allowed_dict = allowed_trie
	current_blocked_dict = blocked_trie
	if inputs[0] == '+':
		for i in range(2, string_length):
			current_allowed_dict = current_allowed_dict.setdefault(inputs[i], {})
		current_allowed_dict[_end] = _end
	else:
		for i in range(2, string_length):
			current_blocked_dict = current_blocked_dict.setdefault(inputs[i], {})
		current_blocked_dict[_end] = _end
print_stack = []
res = parse_and_print(blocked_trie, '', allowed_trie, print_stack)
if res == -1:
	print(-1)
else:
	print(len(print_stack))
	print_stack.sort()
	for pref in print_stack:
		print(pref)


t = int(input())
websites = []
websites.append(['+', '+'])
filters = []
filters.append('+')
lngthfilters = 0
satisfyall = 1
for i in range(t):
	x = list(input().split())
	x[1] += '!'
	x.reverse()
	websites.append(x)
websites.append(['}', '+'])
websites.sort()
for i in range(1, t + 1):
	if websites[i][1] == '-':
		upperlimit = i + 1
		uppertest = 0
		lowerlimit = i - 1
		lowertest = 0
		temp = ''
		j = 0
		while websites[upperlimit][1] == '-':
			upperlimit += 1
		while websites[lowerlimit][1] == '-':
			lowerlimit -= 1
		while uppertest == 0 or lowertest == 0:
			if uppertest == 0:
				if websites[upperlimit][0][j] != websites[i][0][j]:
					uppertest = 1
			if lowertest == 0:
				if websites[lowerlimit][0][j] != websites[i][0][j]:
					lowertest = 1
			if j < len(websites[i][0]) - 1:
				temp += websites[i][0][j]
			j += 1
		if j >= len(websites[i][0]):
			satisfyall = 0
			break
		elif filters[lngthfilters] != temp:
			filters.append(temp)
			lngthfilters += 1
if satisfyall == 0 or lngthfilters == 0:
	print(-1)
else:
	print(lngthfilters)
	for i in filters[1:]:
		print(i)


def binarysearch(trie, val, begin, end):
	if begin <= end:
		mid = (begin + end) // 2
		if trie[val[:mid]] == '+':
			try:
				if trie[val[:mid + 1]] == '-':
					return mid + 1
				else:
					return binarysearch(trie, val, mid + 1, end)
			except:
				return -1
		else:
			try:
				if trie[val[:mid - 1]] == '+':
					return mid
				else:
					return binarysearch(trie, val, begin, mid - 1)
			except:
				return 1
	else:
		return -1

def func():
	n = int(input())
	D = {}
	l = []
	for i in range(n):
		inp = input().split()
		D[inp[1]] = inp[0]
		if inp[0] == '-':
			l.append(inp[1])
	trie = {}
	for val in D.keys():
		for i in range(1, len(val) + 1):
			try:
				var = val[:i]
				if trie[var] == '-' and D[val] == '+':
					trie[var] = '+'
			except:
				trie[var] = D[val]
	ans = []
	for val in l:
		length = len(val)
		if trie[val[0]] == '-':
			flagvar = 1
		else:
			flagvar = binarysearch(trie, val, 1, length)
		if flagvar != -1:
			ans.append(val[:flagvar])
		else:
			print('-1')
			return
	ans.sort()
	length = len(ans)
	finalans = []
	for i in range(length - 1):
		if ans[i] == ans[i + 1]:
			continue
		else:
			finalans.append(ans[i])
	finalans.append(ans[length - 1])
	print(len(finalans))
	for i in finalans:
		print(i)
func()


class Trie:
	_end = '_end_'

	def __init__(self):
		self.root = dict()
		self.blocked = {id(self.root)}
		self.unblocked = {id(self.root)}
		self.answer = None
		self.error = False

	def insert(self, word, isblocked):
		current_dict = self.root
		for letter in word:
			if letter not in current_dict:
				current_dict[letter] = dict()
			current_dict = current_dict[letter]
			(self.blocked if isblocked else self.unblocked).add(id(current_dict))
		current_dict[self._end] = isblocked

	def __solve_rec(self, d, s):
		is_blocked = id(d) in self.blocked
		is_unblocked = id(d) in self.unblocked
		if is_blocked:
			if is_unblocked:
				for k in d:
					self.__solve_rec(d[k], s + k)
			else:
				self.answer.append(s)
		elif not is_unblocked and d:
			self.error = True

	def solve(self):
		self.answer = []
		self.error = False
		self.__solve_rec(self.root, '')
		return sorted(self.answer) if not self.error else None

	def __str__(self):
		return str(self.root)
trie = Trie()
for t in range(int(input())):
	(blocked, site) = input().strip().split()
	trie.insert(site, blocked == '-')
ans = trie.solve()
if ans:
	print(len(ans), *ans, sep='\n')
else:
	print(-1)


_end = '_end_'

def trie(words):
	root = dict()
	for i in words:
		current = root
		for j in i:
			current = current.setdefault(j, {})
		current[_end] = _end
	return root

def in_trie(root, word):
	current = root
	t = 0
	for j in word:
		if j in current:
			t += 1
			current = current[j]
		else:
			return t
	return -1
n = int(input())
root = dict()
a = []
b = []
for i in range(n):
	(c, s) = input().rstrip().split(' ')
	if c == '-':
		b.append(s)
	else:
		a.append(s)
root = trie(a)
c = []
flag = 0
for i in b:
	res = in_trie(root, i)
	if res == -1:
		flag = 1
		break
	result = i[:res + 1]
	if result not in c:
		c.append(result)
if flag:
	print(-1)
else:
	print(len(c))
	c.sort()
	for i in c:
		print(i)


class Node(object):

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

def insertCharacter(value, node):
	n = Node(value)
	node.children.append(n)
	node.children.sort(key=lambda child: child.value)
	return n

def query(value, node):
	for child in node.children:
		if child.value == value:
			return child
	return None

def insertWord(word, root):
	currentNode = root
	for character in word:
		nextNode = query(character, currentNode)
		if nextNode:
			currentNode = nextNode
		else:
			currentNode = insertCharacter(character, currentNode)

def show(node, currentWord=''):
	if len(node.children) == 0:
		print(currentWord + node.value)
	for child in node.children:
		show(child, currentWord + node.value)

def reduceUrl(blackSite, whiteList):
	reducedWord = ''
	currentNode = whiteList
	lcs = ''
	for i in range(len(blackSite)):
		nextNode = query(blackSite[i], currentNode)
		reducedWord += blackSite[i]
		if nextNode:
			currentNode = nextNode
			lcs += nextNode.value
		else:
			break
	if len(lcs) >= len(blackSite):
		return None
	return reducedWord
N = input()
whiteList = Node()
blackList = []
reducedBlackList = []
for i in range(int(N)):
	s = input().split()
	if s[0] == '+':
		insertWord(s[1], whiteList)
	else:
		blackList.append(s[1])
invalid = False
for blackSite in blackList:
	reduceWord = reduceUrl(blackSite, whiteList)
	if reduceWord == None:
		invalid = True
		break
	elif reduceWord not in reducedBlackList:
		reducedBlackList.append(reduceWord)
if invalid == True:
	print(-1)
else:
	sortedBlackList = Node()
	for word in reducedBlackList:
		insertWord(word, sortedBlackList)
	print(len(reducedBlackList))
	if len(reducedBlackList) > 0:
		for w in sorted(reducedBlackList):
			print(w)


def match(site1, site2):
	prefix = ''
	l1 = len(site1)
	l2 = len(site2)
	i = 0
	cnt = 0
	while i < l1:
		if i >= l2:
			cnt += 1
			prefix += site1[i]
			break
		if site1[i] == site2[i]:
			cnt += 1
			prefix += site1[i]
		else:
			cnt += 1
			prefix += site1[i]
			break
		i += 1
	if i == l1:
		return ['', 0]
	else:
		return [prefix, cnt]

def get_prefix(site, unbsites, num_unb, start_ch_map):
	mod = ord('a')
	if start_ch_map[ord(site[0]) % mod] == []:
		return [site[0], 1]
	st = start_ch_map[ord(site[0]) % mod][0]
	en = start_ch_map[ord(site[0]) % mod][1]
	ans = match(site, unbsites[st])
	prefix = ans[0]
	leng = ans[1]
	if not leng:
		return ['', 0]
	i = st + 1
	while i <= en:
		ans = match(site, unbsites[i])
		newprefix = ans[0]
		newleng = ans[1]
		if newleng == 0:
			return ['', 0]
		if newleng < leng:
			return [prefix, 1]
		elif newleng > leng:
			prefix = newprefix
			leng = newleng
		i += 1
	return [prefix, 1]

def find_answer(unbsites, bsites, num_b, num_unb, start_ch_map):
	answer = []
	prefix = get_prefix(bsites[0], unbsites, num_unb, start_ch_map)
	if prefix[1]:
		answer.append(prefix[0])
	else:
		return []
	prev_pref = prefix[0]
	i = 1
	while i < num_b:
		if not bsites[i].startswith(prev_pref):
			prefix = get_prefix(bsites[i], unbsites, num_unb, start_ch_map)
			if prefix[1]:
				answer.append(prefix[0])
				prev_pref = prefix[0]
			else:
				return []
		i += 1
	return answer
n = int(input())
bsites = []
unbsites = []
num_b = 0
num_unb = 0
while n:
	n -= 1
	site = input().strip().split()
	if site[0] == '-':
		bsites.append(site[1])
		num_b += 1
	else:
		unbsites.append(site[1])
		num_unb += 1
unbsites.sort()
bsites.sort()
start_ch_map = []
val = ord('a')
mod = val
for i in range(0, 26):
	start_ch_map.append([])
i = 0
while i < num_unb:
	ind = ord(unbsites[i][0]) % mod
	start_ch_map[ind].append(i)
	i += 1
	while i < num_unb:
		if unbsites[i][0] == unbsites[i - 1][0]:
			i += 1
		else:
			break
	start_ch_map[ind].append(i - 1)
answer = find_answer(unbsites, bsites, num_b, num_unb, start_ch_map)
if answer == []:
	print(-1)
else:
	print(len(answer))
	answer.sort()
	for s in answer:
		print(s)


def find_diff_index(a, b, c):
	i = 0
	(found_a, found_c) = (-1, -1)
	while i < len(a) and i < len(b):
		if a[i] != b[i]:
			found_a = i
			break
		i += 1
	if found_a == -1 and i < len(b):
		found_a = i
	if found_a == -1:
		return -1
	i = 0
	while i < len(b) and i < len(c):
		if b[i] != c[i]:
			found_c = i
			break
		i += 1
	if found_c == -1 and i < len(b):
		found_c = i
	if found_c == -1:
		return -1
	return max(found_a, found_c)
N = int(input())
l = []
for i in range(N):
	(act, site) = input().strip().split(' ')
	act = True if act == '-' else False
	l.append((site, act))
l.sort()
l.insert(0, ('', False))
l.append(('', False))
p_anchor = []
s_anchor = []
anc = 0
for i in range(0, N + 2):
	if not l[i][1]:
		anc = i
	p_anchor.append(anc)
for i in range(N + 1, -1, -1):
	if not l[i][1]:
		anc = i
	s_anchor.append(anc)
s_anchor = s_anchor[::-1]
bad = False
ans = []
for i in range(0, N + 2):
	if bad:
		break
	if l[i][1]:
		diff_ind = find_diff_index(l[p_anchor[i]][0], l[i][0], l[s_anchor[i]][0])
		if diff_ind == -1:
			bad = True
		else:
			ans.append(l[i][0][0:diff_ind + 1])
if bad:
	print(-1)
else:
	ans = list(set(ans))
	ans.sort()
	print(len(ans))
	for i in range(len(ans)):
		print(ans[i])


from collections import defaultdict

class T:

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

	def insert(self, word):
		c = self.root
		for i in word:
			c = c.setdefault(i, {})
		c.setdefault('end')

	def find(self, prefix):
		c = self.root
		for i in prefix:
			if i not in c:
				return False
			c = c[i]
		return True
a = T()
z = []
ans = []
flag = 1
for i in range(int(input())):
	x = input().split()
	if x[0] == '+':
		a.insert(x[1])
	else:
		z.append(x[1])
for e in sorted(z):
	i = 1
	q = len(e)
	while i <= q and a.find(e[:i]):
		i += 1
	if i >= q + 1:
		flag = 0
		break
	else:
		ans.append(e[:i])
ans = sorted(set(ans))
if flag:
	print(len(ans))
	for i in ans:
		print(i)
else:
	print('-1')


import sys
n = int(input())
good = []
bad = []
for i in range(n):
	line = sys.stdin.readline().strip()
	site = line[2:]
	if line[0] == '+':
		good.append(site)
	else:
		bad.append(site)
if len(good) == 0:
	print(0)
	sys.exit(0)
h = {}
for site in good:
	prefix = ''
	h[prefix] = 1
	for c in site:
		prefix += c
		h[prefix] = 1
prefixes = {}
for site in bad:
	uniquePrefixFound = False
	prefix = ''
	for c in site:
		prefix += c
		if not prefix in h:
			uniquePrefixFound = True
			prefixes[prefix] = 1
			break
	if not uniquePrefixFound:
		print(-1)
		sys.exit(0)
print(len(prefixes))
for prefix in sorted(prefixes):
	print(prefix)


def main():
	N = int(input())
	A = []
	for i in range(N):
		(u, v) = list(input().strip().split(' '))
		A += [[v, u]]

	def findout(s):

		def find(s, a):
			if s == '':
				return []
			elif s.lstrip('+') == '' or s.lstrip('-') == '':
				L = len(s)
				T = []
				for i in range(len(s)):
					T += [[a]]
				return T
			else:
				N = len(s)
				s = s.lstrip(s[0])
				T = len(s)
				ans = []
				for i in range(N - T):
					ans += [[a, a + N - T + 1]]
				a = a + N - T
				return ans + find(s, a)
		AA = find(s, -1)
		for j in range(len(AA)):
			if -1 in AA[j]:
				AA[j] = list(set(AA[j]) - set({-1}))
		return AA

	def compare(a, b):
		L = min(len(a), len(b))
		s = ''
		for i in range(L):
			temp = i
			if a[i] == b[i]:
				s += a[i]
			else:
				break
		else:
			if L == len(b):
				return -1
			else:
				return b[:L + 1]
		return b[:temp + 1]
	A = sorted(A)
	s = ''
	for i in range(len(A)):
		s += A[i][1]
	if s.lstrip('+') == '':
		print(0)
		return 0
	elif s.lstrip('-') == '':
		TTTT = []
		for i in range(len(A)):
			if A[i][0][0] not in TTTT:
				TTTT += [A[i][0][0]]
		print(len(TTTT))
		for x in TTTT:
			print(x)
		return 0
	check = [[] for i in range(len(A))]
	start = -1
	while s != '':
		temp = s.lstrip(s[0])
		L = len(s) - len(temp)
		for i in range(start + 1, start + L + 1):
			check[i] = [start, start + L + 1]
		start = start + L
		s = temp
	for i in range(len(check)):
		check[i] = list(set(check[i]) - set({-1, len(check)}))
	for i in range(len(A)):
		s += A[i][1]
	total = []
	totalset = set()
	length = 0
	terr = 0
	for i in range(len(A)):
		if s[i] == '-':
			if len(check[i]) == 1:
				aa = A[check[i][0]][0]
				bb = A[i][0]
				cc = compare(aa, bb)
				if cc == -1:
					terr = 1
					break
				else:
					totalset.add(cc)
					if len(totalset) > length:
						total += [cc]
						length += 1
			elif len(check[i]) == 2:
				aa1 = A[check[i][0]][0]
				aa2 = A[check[i][1]][0]
				bb = A[i][0]
				c1 = compare(aa1, bb)
				c2 = compare(aa2, bb)
				if c1 == -1 or c2 == -1:
					terr = 1
					break
				elif len(c1) > len(c2):
					totalset.add(c1)
					if len(totalset) > length:
						total += [c1]
						length += 1
				else:
					totalset.add(c2)
					if len(totalset) > length:
						total += [c2]
						length += 1
	if terr == 1:
		print(-1)
	else:
		print(len(total))
		for j in range(len(total)):
			print(total[j])
	return 0
main()


o = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']

class al:

	def __init__(self):
		self.d = {'c': 0, 'r': 0, 'd': 0, 'f': 0, 'e': 0, 'z': 0, 'x': 0, 'h': 0, 'k': 0, 'q': 0, 'j': 0, 't': 0, 'p': 0, 'g': 0, 'o': 0, 'b': 0, 'l': 0, 'w': 0, 'i': 0, 'v': 0, 'u': 0, 'y': 0, 'a': 0, 's': 0, 'n': 0, 'm': 0}

	def c(self, gi):
		return self.d[gi]

	def ch(self, j, t):
		self.d[j] = t
t = int(input(''))
p = []
m = []
a = al()
for i in range(t):
	g = input('').split()
	if g[0] == '+':
		p.append(g[1])
	elif g[0] == '-':
		m.append(g[1])
for i in p:
	k = a
	for j in i:
		if k.c(j) == 0:
			k.ch(j, al())
		k = k.c(j)
hh = []
for i in m:
	k = a
	m = 0
	for j in range(len(i)):
		if type(k.c(i[j])) == type(9):
			if k.c(i[j]) == 0:
				hh.append(i[:j + 1])
				k.ch(i[j], 1)
			m = 1
			break
		k = k.c(i[j])
	if m == 0:
		hh = ['-1']
		break
hh.sort()
if '-1' in hh:
	pass
else:
	print(len(hh))
for i in hh:
	print(i)


import sys
t = int(input())
unblocked = set()
blocked = set()
for i in range(t):
	x = input().split()
	if x[0] == '+':
		unblocked.add(x[1])
	else:
		blocked.add(x[1])
ans = set()
good = set()
for site in unblocked:
	n = len(site)
	s = ''
	for i in range(n):
		s += site[i]
		good.add(s)
ans = set()
for site in blocked:
	n = len(site)
	s = ''
	done = False
	for i in range(n):
		s += site[i]
		if s not in good:
			ans.add(s)
			done = True
			break
	if not done:
		print(-1)
		sys.exit()
ans = list(ans)
ans.sort()
if len(ans) == 0 and len(blocked) != 0:
	print(-1)
	sys.exit()
print(len(ans))
for i in ans:
	print(i)


class Word:

	def __init__(self, chars, blocked):
		self.chars = chars
		self.blocked = blocked

class Trie:

	def __init__(self):
		self.root = {'blocked': False}

	def insert(self, word):
		curr = self.root
		for char in word.chars:
			curr = curr.setdefault(char, {'blocked': True})
			if not word.blocked:
				curr['blocked'] = False
		curr.setdefault('end', word.blocked)

	def prefixes(self):
		stack = [self.root]
		prefix = ['']
		visited = set()
		res = []
		while stack:
			curr = stack.pop()
			pre = prefix.pop()
			if pre not in visited:
				visited.add(pre)
				if curr['blocked']:
					res.append(pre)
				else:
					if 'end' in curr and curr['end']:
						return -1
					next = [a for a in curr if a != 'end' and a != 'blocked']
					for a in next:
						prefix.append(pre + a)
						stack.append(curr[a])
		return res
words = Trie()
for _ in range(int(input())):
	(b, s) = input().split()
	w = Word(s, True if b == '-' else False)
	words.insert(w)
res = words.prefixes()
if res == -1:
	print(-1)
else:
	print(len(res))
	print(*sorted(res), sep='\n')


n = int(input())
b = []
ub = []
for i in range(n):
	(j, s) = input().split()
	if j == '+':
		ub.append(s)
	else:
		b.append(s)
l = set()
l2 = set()
l3 = set()
for s in ub:
	for j in range(len(s)):
		h = s[:j + 1]
		if not h in l3:
			l3.add(h)
k = 1
flag = 1
ub.sort()
b.sort()
for s in b:
	if s in l3:
		flag = 0
		break
if flag == 1:
	for s in b:
		for j in range(len(s)):
			k = 1
			x = 0
			s1 = s[:j + 1]
			if s1 in l:
				break
			elif not s1 in l2:
				x = 1
				if s1 in l3:
					k = 0
			if k == 0:
				l2.add(s1)
			if k == 1 and x == 1:
				l.add(s1)
				break
if flag == 0:
	print(-1)
else:
	l1 = list(l)
	print(len(l1))
	l1.sort()
	for s in l1:
		print(s)


class Trie:

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

	def add(self, s):
		cur = self._root
		for c in s:
			if c not in cur:
				cur[c] = {}
			cur = cur[c]

	def psize(self, s):
		res = 0
		cur = self._root
		for c in s:
			if c in cur:
				cur = cur[c]
				res += 1
			else:
				break
		return res
N = int(input())
fnames = []
trie = Trie()
for _ in range(N):
	(tp, name) = input().split()
	if tp == '-':
		fnames.append(name)
	else:
		trie.add(name)
pnames = set()
possible = True
for name in fnames:
	psize = trie.psize(name)
	if psize >= len(name):
		possible = False
		break
	pnames.add(name[:psize + 1])
if possible:
	print(len(pnames))
	for name in sorted(pnames):
		print(name)
else:
	print(-1)


def match(s1, n, s2, m):
	for i in range(min(n, m)):
		if s1[i] != s2[i]:
			return i
	return min(n, m)
a = []
a1 = []
b = []
b1 = []
s = set([])
n = int(input())
for _ in range(n):
	(x, y) = input().strip().split()
	if x == '+':
		a.append(y)
	else:
		b.append(y)
a.sort()
b.sort()
for i in a:
	a1.append(len(i))
for i in b:
	b1.append(len(i))
al = len(a)
bl = len(b)
pos = 0
if al == 0:
	print(-1)
else:
	for i in range(bl):
		res = 0
		f = True
		pos = max(pos, 0)
		while pos < al:
			cur = match(b[i], b1[i], a[pos], a1[pos])
			if cur == b1[i]:
				f = False
				break
			res = max(res, cur)
			if cur == a1[pos] or b[i][cur] > a[pos][cur]:
				pos += 1
			else:
				break
		pos -= 1
		if f == False:
			print(-1)
			break
		s.add(b[i][:res + 1])
	else:
		s = list(s)
		s.sort()
		if len(s) == 0:
			print(-1)
		else:
			print(len(s))
			for i in s:
				print(i)


import sys
sys.setrecursionlimit(10 ** 6)

class TrieNode:

	def __init__(self):
		self.ch = [None] * 26
		self.total = 0
		self.block = 0
		self.end = 0

class Trie:

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

	def insert(self, b, s):
		cur = self.root
		for c in s:
			cur.total += 1
			if b:
				cur.block += 1
			i = ord(c) - 97
			if cur.ch[i] is None:
				cur.ch[i] = TrieNode()
			cur = cur.ch[i]
		cur.total += 1
		if b:
			cur.block += 1
		cur.end = 1 if b else -1

	def recur(self, cur, s, res):
		if cur.total == cur.block:
			res.append(''.join(s))
			return
		if cur.block >= 1 and cur.end == 1:
			res.append('!IMPOSSIBLE!')
			return
		for i in range(26):
			if cur.ch[i] is not None:
				s.append(chr(97 + i))
				self.recur(cur.ch[i], s, res)
				s.pop()

	def collect(self):
		res = []
		s = []
		self.recur(self.root, s, res)
		return res
t = Trie()
n = int(input())
for i in range(n):
	(b, s) = input().split()
	t.insert(b == '-', s)
res = t.collect()
print(-1 if '!IMPOSSIBLE!' in res else str(len(res)) + '\n' + '\n'.join(res))