DNA is a nucleic acid present in the bodies of living things. Each piece of DNA contains a number of genes, some of which are beneficial and increase the DNA's total health. Each gene has a health value, and the total health of a DNA is the sum of the health values of all the beneficial genes that occur as a substring in the DNA. We represent genes and DNA as non-empty strings of lowercase English alphabetic letters, and the same gene may appear multiple times as a susbtring of a DNA.

Given the following:

An array of beneficial gene strings, $genes=[g_0,g_1,...,g_{n-1}]$. Note that these gene sequences are not guaranteed to be distinct.
An array of gene health values, $health=[h_0,h_1,\ldots,h_{n-1}]$, where each $h_i$ is the health value for gene $g_i$.
A set of $\boldsymbol{\mathrm{~S~}}$ DNA strands where the definition of each strand has three components, $\textit{start}$, $\boldsymbol{end}$, and $\boldsymbol{d}$, where string $\boldsymbol{d}$ is a DNA for which genes $g_{start},\ldots,g_{end}$ are healthy.

Find and print the respective total healths of the unhealthiest (minimum total health) and  healthiest (maximum total health) strands of DNA as two space-separated values on a single line.

Input Format

The first line contains an integer, $n$, denoting the total number of genes. 

The second line contains $n$ space-separated strings describing the respective values of $g_0,g_1,\ldots,g_{n-1}$ (i.e., the elements of $genes$). 

The third line contains $n$ space-separated integers describing the respective values of $h_0,h_1,\ldots,h_{n-1}$ (i.e., the elements of $health$). 

The fourth line contains an integer, $\boldsymbol{\mathrm{~S~}}$, denoting the number of strands of DNA to process. 

Each of the $\boldsymbol{\mathrm{~S~}}$ subsequent lines describes a DNA strand in the form start end d, denoting that the healthy genes for DNA strand $\boldsymbol{d}$ are $g_{start},\ldots,g_{end}$ and their respective correlated health values are $h_{start},\ldots,h_{end}$.

Constraints

$1\leq n,s\leq10^5$   
$0\leq h_i\leq10^7$  
$0\leq first\leq last<n$  
$1\leq$ the sum of the lengths of all genes and DNA strands $\leq2\times10^{6}$  
It is guaranteed that each $g_i$ consists of lowercase English alphabetic letters only (i.e., a to z).

Output Format

Print two space-separated integers describing the respective total health of the unhealthiest and the healthiest strands of DNA.

Sample Input 0
6
a b c aa d b
1 2 3 4 5 6
3
1 5 caaab
0 4 xyz
2 4 bcdybc

Sample Output 0
0 19

Explanation 0

In the diagrams below, the ranges of beneficial genes for a specific DNA on the left are highlighed in green and individual instances of beneficial genes on the right are bolded. The total healths of the $s=3$ strands are:

The total health of caaab is $3+4+4+2+6=19$.
 
The total health of xyz is $0$, because it contains no beneficial genes.
 
The total health of bcdybc is $3+5+3=11$.

The unhealthiest DNA strand is xyz with a total health of $0$, and the healthiest DNA strand is caaab with a total health of $19$. Thus, we print 0 19 as our answer.

Source: hackerrank | Difficulty: MEDIUM_HARD
Tags: String algorithms


Solutions:
import bisect
import sys

def str2lst(s):
	return [ord(c) - ord('a') for c in s]

class Node(object):
	__slots__ = ['genes', 'h_sum', 'children']

	def __init__(self):
		self.genes = None
		self.h_sum = None
		self.children = {}
num_of_genes = int(input().strip())
genes = list(input().strip().split(' '))
health = list(map(int, input().strip().split(' ')))
s = int(input().strip())
root = Node()
for (gid, gene) in enumerate(genes):
	node = root
	gene_len = len(gene)
	for (i, c) in enumerate(gene):
		if c in node.children:
			node = node.children[c]
		else:
			child = Node()
			node.children[c] = child
			node = child
		if i == gene_len - 1:
			if node.genes is None:
				node.genes = []
				node.h_sum = []
			node.genes.append(gid)
L = [root]
while L:
	node = L.pop()
	if not node.genes is None:
		node.genes.sort()
		node.h_sum = [0] * (len(node.genes) + 1)
		for (idx, gid) in enumerate(node.genes):
			node.h_sum[idx + 1] = node.h_sum[idx] + health[gid]
	for child in node.children.values():
		L.append(child)

def get_health(seq, first, last):
	seq_len = len(seq)
	h_tot = 0
	L = []
	for (idx, c) in enumerate(seq):
		if not c in root.children:
			continue
		L.append(idx)
	for idx in L:
		(node, pos) = (root, idx)
		while node and pos < seq_len:
			c = seq[pos]
			child = node.children.get(c, None)
			if child and child.genes:
				lb = bisect.bisect_left(child.genes, first)
				ub = bisect.bisect(child.genes, last, lo=lb)
				h_tot += child.h_sum[ub] - child.h_sum[lb]
			node = child
			pos += 1
	return h_tot
h_tot_min = sys.maxsize
h_tot_max = 0
f_min = num_of_genes
f_max = 0
for a0 in range(s):
	(first, last, d) = input().strip().split(' ')
	(first, last, d) = [int(first), int(last), str(d)]
	h_tot = get_health(d, first, last)
	h_tot_min = min(h_tot_min, h_tot)
	h_tot_max = max(h_tot_max, h_tot)
print(h_tot_min, h_tot_max)


from collections import deque
from bisect import bisect_left
n = int(input().strip())
genes = input().strip().split(' ')
health = list(map(int, input().strip().split(' ')))
genes_grouped = {}
health_grouped = {}

class Node(object):
	__slots__ = ['goto', 'word']

	def __init__(self):
		self.goto = {}
		self.word = None

def create_forest(patterns, n):
	root = Node()
	for i in range(n):
		node = root
		for symbol in patterns[i]:
			node = node.goto.setdefault(symbol, Node())
		if not node.word:
			node.word = i
			genes_grouped[i] = [i]
			health_grouped[i] = [health[i]]
		else:
			genes_grouped[node.word].append(i)
			health_grouped[node.word].append(health[i] + health_grouped[node.word][-1])
	return root

def find_diff(ind, first, last):
	(res, top, bottom) = (0, 0, 0)
	arr = genes_grouped[ind]
	L = len(arr)
	if L == 1:
		if first <= arr[0] <= last:
			res = health_grouped[ind][0]
	elif L > 1:
		if last >= arr[-1]:
			top = L - 1
		else:
			top = bisect_left(arr, last)
			if arr[top] > last:
				top -= 1
		if first >= arr[-1]:
			bottom = L - 1
		else:
			bottom = bisect_left(arr, first)
			if arr[bottom] >= first:
				bottom -= 1
		if top > bottom:
			res = health_grouped[ind][top]
			if bottom >= 0:
				res -= health_grouped[ind][bottom]
	return res

def find_all(w, root, first, last):
	res = 0
	len_w = len(w)
	found = {}
	for i in range(len_w):
		node = root
		j = i
		while node != None:
			if node.word is not None:
				ind = node.word
				if ind in found:
					res += found[ind]
				else:
					found[ind] = find_diff(ind, first, last)
					res += found[ind]
			if j == len_w:
				break
			node = node.goto.get(w[j], None)
			j += 1
	return res
(min_h, max_h) = (2 ** 64, 0)
root = create_forest(genes, n)
genes = []
health = []
for a0 in range(int(input().strip())):
	(first, last, d) = input().strip().split(' ')
	(first, last, d) = [int(first), int(last), str(d)]
	h = find_all(d, root, first, last)
	min_h = min(h, min_h)
	max_h = max(h, max_h)
print(min_h, max_h)


import bisect
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right

class ScoreTable:

	def __init__(self):
		self.scoreIndexes = []
		self.scoreSums = []

	def append(self, i, s):
		self.scoreIndexes.append(i)
		partial = self.scoreSums[-1] if len(self.scoreSums) > 0 else 0
		self.scoreSums.append(s + partial)

	def getScore(self, start, end):
		lo = bisect_left(self.scoreIndexes, start)
		hi = bisect_right(self.scoreIndexes, end)
		if hi == lo:
			return 0
		elif lo == 0:
			return self.scoreSums[hi - 1]
		else:
			return self.scoreSums[hi - 1] - self.scoreSums[lo - 1]

def longestCommonPrefix(s, t):
	stop = min(len(s), len(t))
	i = 0
	while i < stop and s[i] == t[i]:
		i += 1
	return s[:i]

class TrieNode:

	def __init__(self, label):
		self.label = label
		self.child = {}
		self.scores = None

	def __str__(self):
		return '{' + ','.join([c + ':' + str(n) for (c, n) in self.child.items()]) + '}'

	def insert(self, k, ix, score):
		i = 0
		node = self
		while i < len(k):
			if k[i] in node.child:
				child = node.child[k[i]]
				lcp = longestCommonPrefix(k[i:], child.label)
				if len(lcp) < len(child.label):
					suffix = child.label[len(lcp):]
					child.label = suffix
					prefNode = TrieNode(lcp)
					prefNode.child[suffix[0]] = child
					node.child[lcp[0]] = prefNode
					child = prefNode
				node = child
				i += len(lcp)
			else:
				newNode = TrieNode(k[i:])
				node.child[k[i]] = newNode
				node = newNode
				i = len(k)
		if not node.scores:
			node.scores = ScoreTable()
		node.scores.append(ix, score)

	def traverse(self):
		yield self
		for node in self.child.values():
			yield from node.traverse()

def countNodes(t):
	return sum((1 for _ in t.traverse()))

def soloChildren(t):
	return sum((1 for n in t.traverse() if len(n.child) == 1))

def buildGeneTrie(genes, healths):
	trie = TrieNode('')
	for i in range(len(genes)):
		trie.insert(genes[i], i, healths[i])
	return trie

def checkDNA(geneTrie, dna, start, end):
	score = 0
	z = len(dna)
	for i in range(z):
		node = geneTrie
		j = i
		while j < z and dna[j] in node.child:
			node = node.child[dna[j]]
			x = len(node.label)
			if node.label != dna[j:j + x]:
				break
			if node.scores:
				score += node.scores.getScore(start, end)
			j += x
	return score

def main():
	n_ = int(input())
	genes = input().split()
	healths = list(map(int, input().split()))
	geneTrie = buildGeneTrie(genes, healths)
	best = 0
	worst = float('inf')
	s = int(input())
	for _ in range(s):
		(first, last, d) = input().split()
		(first, last) = (int(first), int(last))
		score = checkDNA(geneTrie, d, first, last)
		best = max(best, score)
		worst = min(worst, score)
	print(worst, best)
main()


from collections import deque
from array import array
import bisect
import re
G = list()
F = array('I')
O = dict()
S = [1]

def add_word(word, value):
	state = 0
	for w in word:
		w = ord(w) - 97
		while state >= len(G):
			G.append(dict())
		if not w in G[state]:
			G[state][w] = S[0]
			S[0] += 1
		state = G[state][w]
	O[state] = value

def build_fsa():
	F.extend([0 for i in range(S[0])])
	queue = deque(G[0].values())
	while queue:
		state = queue.popleft()
		if state < len(G):
			for w in G[state]:
				t = F[state]
				while t and w not in G[t]:
					t = F[t]
				s = G[state][w]
				F[s] = G[t][w] if w in G[t] else 0
				queue.append(s)

def search(text, first, last):
	state = 0
	result = 0
	for t in text:
		t = ord(t) - 97
		while state and (state >= len(G) or t not in G[state]):
			state = F[state]
		state = G[state][t] if t in G[state] else 0
		tmp = state
		while not tmp == 0:
			if tmp in O:
				result += cost(O[tmp], first, last)
			tmp = F[tmp]
	return result

def cost(arr, start, end):
	e_index = bisect.bisect_right(arr[0], end) - 1
	e_sum = arr[1][e_index] if e_index >= 0 else 0
	s_index = bisect.bisect_left(arr[0], start, 0) - 1
	s_sum = arr[1][s_index] if s_index >= 0 else 0
	return e_sum - s_sum
input().strip()
genes = input().split(' ')
healths = input().split(' ')
s = int(input().strip())
min_val = 10 ** 20
max_val = -1
health_map = dict()
for (id, (gene, health)) in enumerate(zip(genes, healths)):
	health = int(health)
	if gene not in health_map:
		health_map[gene] = ([id], [health])
	else:
		health_slot = health_map[gene]
		health_slot[0].append(id)
		health_slot[1].append(health_slot[1][-1] + health)
del healths[:]
del healths
del genes[:]
del genes
for (g, h) in health_map.items():
	add_word(g, h)
health_map.clear()
del health_map
build_fsa()
for a0 in range(s):
	(first, last, d) = input().split(' ')
	(first, last, d) = [int(first), int(last), d]
	val = search(d, first, last)
	min_val = min(min_val, val)
	max_val = max(max_val, val)
print(min_val, max_val)


from collections import deque
from bisect import bisect, bisect_left

class SortedDict:

	def __init__(self, d=None):
		if d is None:
			self.keys = []
			self.values = []
			self.maxlenkey = 0
		else:
			items = list(d.items())
			items.sort(key=lambda pair: pair[0])
			self.keys = [item[0] for item in items]
			self.values = [item[1] for item in items]
			self.maxlenkey = max((len(k) for k in self.keys))

	def __str__(self):
		return str(list(zip(self.keys, self.values)))

	def __repr__(self):
		return str(list(zip(self.keys, self.values)))

	def __getitem__(self, key):
		i = bisect(self.keys, key)
		if i > 0 and self.keys[i - 1] == key:
			return self.values[i - 1]
		raise ValueError('Key error: ' + key)

	def __setitem__(self, key, value):
		if len(key) > self.maxlenkey:
			self.maxlenkey = len(key)
		i = bisect(self.keys, key)
		if i > 0 and self.keys[i - 1] == key:
			self.values[i - 1] = value
			return
		self.keys.insert(i, key)
		self.values.insert(i, value)

	def __delitem__(self, key):
		i = bisect(self.keys, key)
		if i > 0 and self.keys[i - 1] == key:
			del self.keys[i - 1]
			del self.values[i - 1]
			return
		raise ValueError('Key error: ' + key)

	def __iter__(self):
		return iter(self.keys)

	def __len__(self):
		return len(self.keys)

	def __keytransform__(self, key):
		return key

	def keys(self):
		return self.keys

	def values(self):
		return self.values

	def items(self):
		return [(self.keys[i], self.values[i]) for i in range(len(self.keys))]

	def isPrefix(self, key):
		i = bisect(self.keys, key)
		if i < len(self.keys):
			ikey = self.keys[i]
			if ikey.startswith(key):
				return True
		return False

	def getPrefix(self, key):
		if key == '':
			if len(self.keys) > 0 and self.keys[0] == '':
				return ('', self.values[0])
			else:
				raise ValueError('Prefix error')
		i = bisect(self.keys, key)
		if i > 0:
			ikey = self.keys[i - 1]
			if (i > 1 or ikey != '') and key.startswith(ikey):
				return (ikey, self.values[i - 1])
		raise ValueError('Prefix error')

	def getPrefixForLongString(self, key, j):
		if key == '':
			if len(self.keys) > 0 and self.keys[0] == '':
				return ('', self.values[0])
			else:
				raise ValueError('Prefix error')
		i = bisect(self.keys, key[j:j + self.maxlenkey])
		if i > 0:
			ikey = self.keys[i - 1]
			if (i > 1 or ikey != '') and key[j:j + self.maxlenkey].startswith(ikey):
				return (ikey, self.values[i - 1])
		raise ValueError('Prefix error')

	def getCommonPrefix(self, key):
		i = bisect(self.keys, key)
		if i > 0 and (self.keys[i - 1] != '' and key[0] == self.keys[i - 1][0]):
			return (self.keys[i - 1], self.values[i - 1])
		if i < len(self.keys) and (self.keys[i] != '' and key[0] == self.keys[i][0]):
			return (self.keys[i], self.values[i])
		raise ValueError('Prefix error: ' + key)

class RadixTOF:

	def __init__(self):
		self.t = [SortedDict()]
		self.o = [[]]
		self.f = [0]
		self.fr = [None]
		self.n = 1

	def get(self, key):
		return self.getFromIndex(key, 0)[0]

	def getIndexRemains(self, key):
		return self.getFromIndex(key, 0)

	def getFromIndex(self, key, state):
		if key == '':
			if len(self.t[state]) == 0:
				return [state, key]
			else:
				return [-1, key]
		i = bisect(list(self.t[state].keys()), key) - 1
		if i < 0:
			return [-1, key]
		(prefix, to_state) = list(self.t[state].items())[i]
		if key == prefix or (prefix != '' and key.startswith(prefix)):
			return self.getFromIndex(key[len(prefix):], to_state)
		return [-1, key]

	def nextState(self, state, key):
		try:
			(prefix, to_state) = self.t[state].getPrefix(key)
		except ValueError:
			return [state, 0]
		else:
			return [to_state, len(prefix)]

	def nextStateForLongString(self, state, key, i):
		try:
			(prefix, to_state) = self.t[state].getPrefixForLongString(key, i)
		except ValueError:
			return [state, 0]
		else:
			return [to_state, len(prefix)]

	def followPath(self, state, key):
		try:
			(prefix, to_state) = self.t[state].getPrefix(key)
		except ValueError:
			return [state, key]
		else:
			return self.followPath(to_state, len(prefix))

	def insert(self, key):
		if self.n + 2 >= len(self.t):
			self.resize()
		state = 0
		remains = key
		while 1:
			try:
				(prefix, to_state) = self.t[state].getPrefix(remains)
			except ValueError:
				break
			else:
				if len(self.t[to_state]) == 0:
					break
				remains = remains[len(prefix):]
				state = to_state
		if remains == '' and len(self.t[state]) == 0:
			return state
		if remains != '':
			try:
				(prefix, to_state) = self.t[state].getCommonPrefix(remains)
			except ValueError:
				pass
			else:
				j = 0
				while j < len(prefix) and j < len(remains) and (prefix[j] == remains[j]):
					j += 1
				del self.t[state][prefix]
				self.t[state][prefix[:j]] = self.n
				self.t[self.n][prefix[j:]] = to_state
				self.t[self.n][remains[j:]] = self.n + 1
				self.insertOutput(self.n + 1, key)
				self.n += 2
				return self.n + 1
		self.t[state][remains] = self.n
		self.insertOutput(self.n, key)
		self.n += 1
		return self.n

	def insertOutput(self, state, key):
		self.o[state].append(key)

	def insertOutputList(self, state, keylist):
		self.o[state].extend(keylist)

	def getOutput(self, state):
		return self.o[state]

	def resize(self):
		size = len(self.t)
		self.t.extend([SortedDict() for _ in range(size)])
		self.o.extend([[] for _ in range(size)])

	def cutLast(self, n):
		size = len(self.t)
		del self.t[n:size]
		del self.o[n:size]

	def AC(self, string):
		occ = {}
		state = 0
		i = 0
		while 1:
			(res, cut) = self.nextStateForLongString(state, string, i)
			i += cut
			if res != state:
				for match in self.o[res]:
					occ[match] = occ.get(match, 0) + 1
			if i >= len(string):
				if self.fr[res] is None:
					break
				else:
					i -= len(self.fr[res])
					state = self.f[res]
			elif res == state:
				if res == 0:
					i += 1
				else:
					if not self.fr[res] is None:
						i -= len(self.fr[res])
					state = self.f[res]
			else:
				state = res
		return occ

def buildRadixTOF(keywords):
	tof = RadixTOF()
	for keyword in keywords:
		tof.insert(keyword)
	tof.cutLast(tof.n + 1)
	tof.f = [0] * len(tof.t)
	tof.fr = [None] * len(tof.t)
	for state in range(len(tof.t)):
		if '' in tof.t[state]:
			tof.insertOutputList(state, tof.o[tof.t[state]['']])
	queue = deque()
	for (_, to_state) in tof.t[0].items():
		queue.append(to_state)
	dependencies = [None] * len(tof.t)
	countdependencies = 0
	while queue:
		r = queue.popleft()
		for (prefix, to_state) in tof.t[r].items():
			from_state = r
			queue.append(to_state)
			state = tof.f[from_state]
			if not tof.fr[from_state] is None:
				prefix = tof.fr[from_state] + prefix
			found = False
			while 1:
				(res, i) = tof.nextState(state, prefix)
				prefix = prefix[i:]
				if prefix == '' or ((res == 0 or res == state) and found):
					break
				elif res == 0 and res == state:
					prefix = prefix[1:]
				elif res == state:
					if tof.t[state].isPrefix(prefix):
						break
					else:
						if not tof.fr[state] is None:
							prefix = tof.fr[state] + prefix
						state = tof.f[state]
				else:
					if dependencies[to_state] is None:
						dependencies[to_state] = set()
						countdependencies += 1
					dependencies[to_state].add(res)
					state = res
					found = True
			tof.f[to_state] = res
			if prefix != '':
				tof.fr[to_state] = prefix
			if not res == state:
				if dependencies[to_state] is None:
					dependencies[to_state] = set()
					countdependencies += 1
				dependencies[to_state].add(res)
	while countdependencies > 0:
		for state in range(len(tof.t)):
			if not dependencies[state] is None:
				if all((dependencies[from_state] is None for from_state in dependencies[state])):
					for from_state in dependencies[state]:
						tof.insertOutputList(state, tof.o[from_state])
					dependencies[state] = None
					countdependencies -= 1
	return tof

class PrefixTOF:

	def __init__(self):
		self.t = [None]
		self.o = [None]
		self.f = [0]
		self.n = 1

	def insert(self, key):
		while self.n + len(key) + 1 >= len(self.t):
			self.resize()
		state = 0
		j = 0
		for (_, char) in enumerate(key):
			ichar = ord(char) - ord('a')
			res = self.t[state].get(ichar, -1) if state < len(self.t) and (not self.t[state] is None) else -1
			if res == -1:
				break
			state = res
			j += 1
		for char in key[j:]:
			ichar = ord(char) - ord('a')
			if self.t[state] is None:
				self.t[state] = {}
			self.t[state][ichar] = self.n
			state = self.n
			self.n += 1
		if self.o[state] is None:
			self.o[state] = []
		self.o[state].append(key)

	def insertOutput(self, state, key):
		self.o[state].append(key)

	def insertOutputList(self, state, keylist):
		self.o[state].extend(keylist)

	def getOutput(self, state):
		return self.o[state]

	def resize(self):
		size = len(self.t)
		self.t.extend([None for _ in range(size)])
		self.o.extend([None for _ in range(size)])

	def cutLast(self, n):
		size = len(self.t)
		del self.t[n:size]
		del self.o[n:size]

	def AC(self, string):
		state = 0
		occ = {}
		for (i, char) in enumerate(string):
			while 1:
				ichar = ord(char) - ord('a')
				res = self.t[state].get(ichar, state and -1) if not self.t[state] is None else -1
				if res != -1:
					state = res
					break
				state = self.f[state]
			if not self.o[state] is None:
				for match in self.o[res]:
					occ[match] = occ.get(match, 0) + 1
		return occ

def buildPrefixTOF(keywords):
	tof = PrefixTOF()
	for (_, keyword) in enumerate(keywords):
		tof.insert(keyword)
	tof.cutLast(tof.n + 1)
	tof.f = [0] * (tof.n + 1)
	queue = deque()
	for (_, to_state) in tof.t[0].items():
		queue.append(to_state)
		tof.f[to_state] = 0
	while queue:
		r = queue.popleft()
		if not tof.t[r] is None:
			for (ichar, to_state) in tof.t[r].items():
				from_state = r
				queue.append(to_state)
				state = tof.f[from_state]
				while 1:
					res = tof.t[state].get(ichar, state and -1) if not tof.t[state] is None else -1
					if res != -1:
						break
					state = tof.f[state]
				failure = tof.t[state].get(ichar, state and -1) if not tof.t[state] is None else -1
				tof.f[to_state] = failure
				if tof.o[to_state] is None:
					tof.o[to_state] = []
				if not tof.o[failure] is None:
					tof.o[to_state].extend(tof.o[failure])
	return tof

def buildTOFBasedOnKeys(keys):
	mean = sum((len(key) for key in keys)) // max(len(keys), 1)
	if 2 ** mean < len(keys):
		return buildPrefixTOF(keys)
	else:
		return buildRadixTOF(keys)

def healthFromOcc(genesd, occ, first, last):
	h = 0
	for (gene, o) in occ.items():
		gened = genesd[gene]
		start = bisect_left(gened[0], first) - 1
		end = bisect(gened[0], last) - 1
		hstart = 0 if start < 0 else gened[1][start]
		hend = 0 if end < 0 else gened[1][len(gened[1])] if end >= len(gened[1]) else gened[1][end]
		h += o * (hend - hstart)
	return h
n = int(input())
genes = input().rstrip().split()
health = list(map(int, input().rstrip().split()))
(maxh, minh, h) = (0, -1, 0)
genesd = {}
genesitem = []
for j in range(n):
	if not genes[j] in genesd:
		genesd[genes[j]] = [[j], [health[j]]]
	else:
		genesitem = genesd[genes[j]]
		genesitem[1].append(genesitem[1][len(genesitem[1]) - 1] + health[j])
		genesitem[0].append(j)
del genes, health, genesitem
tof = buildTOFBasedOnKeys(genesd.keys())
s = int(input())
for s_itr in range(s):
	firstLastd = input().split()
	first = int(firstLastd[0])
	last = int(firstLastd[1])
	d = firstLastd[2]
	occ = tof.AC(d)
	h = healthFromOcc(genesd, occ, first, last)
	if h > maxh:
		maxh = h
	if h < minh or minh < 0:
		minh = h
del tof, genesd
print(minh, maxh)


import math
import os
import random
import re
import sys
import bisect

class ScoreTable:

	def __init__(self):
		self.scoreIndexes = []
		self.scoreSums = []

	def append(self, index, s):
		self.scoreIndexes.append(index)
		if len(self.scoreSums) > 0:
			partial = self.scoreSums[-1]
		else:
			partial = 0
		self.scoreSums.append(s + partial)

	def getScore(self, start, end):
		low = bisect.bisect_left(self.scoreIndexes, start)
		high = bisect.bisect_right(self.scoreIndexes, end)
		if high == low:
			return 0
		elif low == 0:
			return self.scoreSums[high - 1]
		else:
			return self.scoreSums[high - 1] - self.scoreSums[low - 1]

def longestCommonPrefix(s, t):
	stop = min(len(s), len(t))
	i = 0
	while i < stop and s[i] == t[i]:
		i += 1
	return s[:i]

class TrieNode:

	def __init__(self, label):
		self.label = label
		self.child = {}
		self.scores = None

	def insert(self, k, ix, score):
		i = 0
		node = self
		while i < len(k):
			if k[i] in node.child:
				child = node.child[k[i]]
				lcp = longestCommonPrefix(k[i:], child.label)
				if len(lcp) < len(child.label):
					suffix = child.label[len(lcp):]
					child.label = suffix
					prefNode = TrieNode(lcp)
					prefNode.child[suffix[0]] = child
					node.child[lcp[0]] = prefNode
					child = prefNode
				node = child
				i += len(lcp)
			else:
				newNode = TrieNode(k[i:])
				node.child[k[i]] = newNode
				node = newNode
				i = len(k)
		if not node.scores:
			node.scores = ScoreTable()
		node.scores.append(ix, score)

	def traverse(self):
		yield self
		for node in self.child.values():
			yield from node.traverse()

def countNodes(t):
	return sum((1 for _ in t.traverse()))

def soloChildren(t):
	return sum((1 for n in t.traverse() if len(n.child) == 1))

def buildGeneTrie(genes, healths):
	trie = TrieNode('')
	for i in range(len(genes)):
		trie.insert(genes[i], i, healths[i])
	return trie

def checkDNA(geneTrie, dna, start, end):
	score = 0
	z = len(dna)
	for i in range(z):
		node = geneTrie
		j = i
		while j < z and dna[j] in node.child:
			node = node.child[dna[j]]
			x = len(node.label)
			if node.label != dna[j:j + x]:
				break
			if node.scores:
				score += node.scores.getScore(start, end)
			j += x
	return score

def main():
	n_ = int(input())
	genes = input().split()
	healths = list(map(int, input().split()))
	geneTrie = buildGeneTrie(genes, healths)
	best = 0
	worst = math.inf
	s = int(input())
	for _ in range(s):
		(first, last, d) = input().split()
		(first, last) = (int(first), int(last))
		score = checkDNA(geneTrie, d, first, last)
		best = max(best, score)
		worst = min(worst, score)
	print(worst, best)
main()


from collections import defaultdict
from bisect import bisect_left, bisect_right

def get_gene_health(dna, gene_data, gene_health):
	total_gene_health = 0
	gene_extensions = []
	first = gene_health.first
	last = gene_health.last
	gh_dict = gene_health.gh
	inc_set = gene_health.inc_set
	for (i, d_char) in enumerate(dna):
		total_gene_health += calc_score(first, last, gh_dict, inc_set, d_char)
		new_gene_extensions = []
		try:
			next_ge = gene_data[d_char]
			if isinstance(next_ge, str):
				start = i
				end = start + len(next_ge)
				substrand = dna[start:end]
				total_gene_health += calc_score(first, last, gh_dict, inc_set, substrand)
			else:
				new_gene_extensions.append(next_ge)
		except KeyError:
			pass
		for ge in gene_extensions:
			ongoing = ge['ongoing'] + d_char
			total_gene_health += calc_score(first, last, gh_dict, inc_set, ongoing)
			try:
				next_ge = ge[d_char]
				if isinstance(next_ge, str):
					start = i - len(ongoing) + 1
					end = start + len(next_ge)
					substrand = dna[start:end]
					total_gene_health += calc_score(first, last, gh_dict, inc_set, substrand)
				else:
					new_gene_extensions.append(next_ge)
			except KeyError:
				pass
		gene_extensions = new_gene_extensions
	return total_gene_health

def create_incomplete_set_data(genes, depth=0, ongoing=None):
	grouped_genes = defaultdict(list)
	ongoing = ongoing if ongoing is not None else ''
	inc_set = set()
	comp_set = set()
	for gene in genes:
		if depth == len(gene) - 1:
			comp_set.add(gene[-1])
		else:
			inc_set.add(gene[depth])
			grouped_genes[gene[depth]].append(gene)
	set_data = {'incompletes': inc_set, 'completes': comp_set, 'ongoing': ongoing}
	for (group_char, gene_group) in grouped_genes.items():
		if len(gene_group) > 1:
			set_data[group_char] = create_incomplete_set_data(gene_group, depth + 1, ongoing=ongoing + group_char)
		else:
			set_data[group_char] = gene_group[0]
	return set_data

class LocalGeneHealth:

	def __init__(self, first, last, gene_healths_dict, gh_inc_set):
		self.first = first
		self.last = last
		self.gh = gene_healths_dict
		self.inc_set = gh_inc_set

def calc_score(first, last, gh, inc_set, item):
	if item in gh:
		inc_set = inc_set[item]
		add = None
		i = bisect_right(inc_set, last)
		if i:
			add = gh[item][i - 1]
		if add is None:
			return 0
		sub = 0
		i = bisect_left(inc_set, first)
		if i:
			sub = gh[item][i - 1]
		return add - sub
	return 0

def process_gene_health(genes, gene_healths):
	d = defaultdict(list)
	inc_set = defaultdict(list)
	for (i, gene) in enumerate(genes):
		try:
			prev = d[gene][-1]
			d[gene].append(gene_healths[i] + prev)
		except IndexError:
			d[gene].append(gene_healths[i])
		inc_set[gene].append(i)
	return (d, inc_set)
n = int(input())
genes = input().rstrip().split()
gene_healths = list(map(int, input().rstrip().split()))
(gene_health_dict, gh_inc_set) = process_gene_health(genes, gene_healths)
local_gene_health = LocalGeneHealth(0, len(genes), gene_health_dict, gh_inc_set)
incomplete_gene_sets = create_incomplete_set_data(genes)
min_health = float('inf')
max_health = float('-inf')
s = int(input())
for s_itr in range(s):
	firstLastd = input().split()
	first = int(firstLastd[0])
	last = int(firstLastd[1])
	d = firstLastd[2]
	local_gene_health.first = first
	local_gene_health.last = last
	total_gene_health = get_gene_health(d, incomplete_gene_sets, local_gene_health)
	min_health = min(min_health, total_gene_health)
	max_health = max(max_health, total_gene_health)
print(min_health, max_health)


import math
import os
import random
import re
import sys
from collections import defaultdict, Counter, deque
from bisect import bisect_left, bisect_right

class aca_node:

	def __init__(self, node_id, char=None, parent=None):
		self.id = node_id
		self.char = char
		self.parent = parent
		self.children = {}
		self.data = None
		self.suffix = None
		self.dict_suffix = None

class aca_trie:

	def __init__(self):
		self.count = 0
		self.start = aca_node(node_id=self.count)
		self.index = [self.start]

	def add(self, word, data):
		assert word
		current = self.start
		for l in word:
			if not l in current.children:
				self.count += 1
				baby = aca_node(node_id=self.count, char=l, parent=current)
				current.children[l] = baby
				self.index.append(baby)
			current = current.children[l]
		if current.data:
			current.data.append(data[1] + current.data[-1])
			current.data_indices.append(data[0])
		else:
			current.data = [data[1]]
			current.data_indices = [data[0]]

	def build_suffix(self):
		stack = deque(self.start.children.values())
		while stack:
			node = stack.popleft()
			current = node.parent
			node.suffix = self.start
			while current.suffix:
				current = current.suffix
				if node.char in current.children:
					node.suffix = current.children[node.char]
					break
			for (l, child) in node.children.items():
				stack.append(child)

	def build_dict_suffix(self):
		for node in self.index[1:]:
			current = node.suffix
			while True:
				if not current.id:
					break
				elif current.data:
					node.dict_suffix = current
					break
				current = current.suffix

	def finditer(self, s, start, end):
		current = self.start
		memory = {}
		for (i, l) in enumerate(s):
			transition = current
			while True:
				if l in transition.children:
					current = transition.children[l]
					break
				elif not transition.suffix:
					current = transition
					break
				else:
					transition = transition.suffix
			key = current
			health = 0
			while key:
				if key.data:
					x0 = bisect_left(key.data_indices, start) - 1
					x1 = bisect_right(key.data_indices, end) - 1
					if x1 >= 0:
						health += key.data[x1]
					if x0 >= 0:
						health -= key.data[x0]
				key = key.dict_suffix
			if health:
				yield health

def DNA_healthcheck_ACA(genes, healths, strands):
	(min_health, max_health) = (None, None)
	max_strand_length = max([len(x[2]) for x in strands])
	trie = aca_trie()
	for (i, (gene, health)) in enumerate(zip(genes, healths)):
		if len(gene) > max_strand_length:
			continue
		trie.add(gene, (i, health))
	trie.build_suffix()
	trie.build_dict_suffix()
	for (start, end, strand) in strands:
		strand_health = sum(trie.finditer(strand, start, end))
		if min_health is None:
			min_health = strand_health
		else:
			min_health = min(min_health, strand_health)
		if max_health is None:
			max_health = strand_health
		else:
			max_health = max(max_health, strand_health)
	return [min_health, max_health]

def DNA_healthcheck_strings(genes, healths, strands):
	(min_health, max_health) = (None, None)
	max_strand_length = max([len(x[2]) for x in strands])
	gene_health = defaultdict(list)
	gene_lengths = {}
	for (i, (gene, health)) in enumerate(zip(genes, healths)):
		lg = len(gene)
		if lg > max_strand_length:
			continue
		gene_lengths[lg] = 1
		for j in range(1, len(gene)):
			gene_health[gene[0:j]]
		sofar = gene_health[gene][-1][1] if gene_health[gene] else 0
		gene_health[gene].append((i, sofar + health))
	gene_lengths = sorted(gene_lengths.keys())
	for (start, end, strand) in strands:
		strand_health = 0
		memory = defaultdict(int)
		for i in range(len(strand)):
			gl = 0
			j = gene_lengths[gl]
			while i + j <= len(strand) and strand[i:i + j] in gene_health:
				piece = strand[i:i + j]
				if gene_health[piece] and piece in memory:
					strand_health += memory[piece]
				else:
					data = gene_health[piece]
					x0 = bisect_left(data, (start, 0)) - 1
					x1 = bisect_right(data, (end + 0.1, 0)) - 1
					health = 0
					if x1 >= 0:
						health = data[x1][1]
					if x0 >= 0:
						health -= data[x0][1]
					strand_health += health
					memory[piece] += health
				gl += 1
				if gl == len(gene_lengths):
					break
				j = gene_lengths[gl]
		if min_health is None:
			min_health = strand_health
		else:
			min_health = min(min_health, strand_health)
		if max_health is None:
			max_health = strand_health
		else:
			max_health = max(max_health, strand_health)
	return [min_health, max_health]

def DNA_healthcheck(genes, healths, strands):
	max_strand_length = max([len(x[2]) for x in strands])
	gene_lengths = len([x for x in Counter([len(x) for x in genes]).keys() if x <= max_strand_length])
	result = DNA_healthcheck_strings(genes, healths, strands) if gene_lengths <= 2 else DNA_healthcheck_ACA(genes, healths, strands)
	return result
import array
n = int(input())
genes = input().rstrip().split()
health = list(map(int, input().rstrip().split()))
s = int(input())
strands = []
for s_itr in range(s):
	firstLastd = input().split()
	first = int(firstLastd[0])
	last = int(firstLastd[1])
	d = firstLastd[2]
	strands.append((first, last, d))
result = DNA_healthcheck(genes, health, strands)
print('%d %d' % tuple(result))


import math
import os
import random
import re
import sys
import string
import bisect
n = int(sys.stdin.readline())
genes = sys.stdin.readline().split()
health = list(map(int, sys.stdin.readline().split()))
s = int(sys.stdin.readline())
(mx, mn) = (0, sys.maxsize)
healthDict = {}
sumDict = {}
root = [{}, None, set()]
root[1] = root
for j in range(len(genes)):
	gene = genes[j]
	state = root
	for c in gene:
		if c not in state[0]:
			state[0][c] = [{}, root, '']
		state = state[0][c]
	state[2] = gene
	if gene not in healthDict:
		healthDict[gene] = ([], [])
		sumDict[gene] = 0
	sumDict[gene] += health[j]
	healthDict[gene][0].append(j)
	healthDict[gene][1].append(sumDict[gene])
queue = [root[0][char] for char in root[0]]
while queue:
	newQueue = []
	for state in queue:
		for char in state[0]:
			child = state[0][char]
			fail = state[1]
			while True:
				if char in fail[0] or fail == root:
					break
				fail = fail[1]
			child[1] = fail[0].get(char, root)
			newQueue.append(child)
	queue = newQueue
seen = {}
for s_itr in range(s):
	firstLastd = sys.stdin.readline().split()
	first = int(firstLastd[0])
	last = int(firstLastd[1])
	d = firstLastd[2]
	totalHealth = 0
	matchGene = {}
	state = root
	for c in d:
		while c not in state[0] and state != root:
			state = state[1]
		state = state[0].get(c, root)
		tmp = state
		while tmp != root:
			if tmp[2]:
				matchGene[tmp[2]] = matchGene.get(tmp[2], 0) + 1
			tmp = tmp[1]
	for gene in matchGene:
		(ll1, ll2) = (healthDict[gene][0], healthDict[gene][1])
		first0 = bisect.bisect_left(ll1, first)
		last0 = bisect.bisect_right(ll1, last, first0) - 1
		if first0 > last0:
			continue
		totalHealth += matchGene[gene] * (ll2[last0] - ll2[first0 - 1] if first0 else ll2[last0])
	mx = max(mx, totalHealth)
	mn = min(mn, totalHealth)
print(mn, mx)


from collections import deque
from bisect import bisect_left, bisect_right
n = int(input())
g = [[ord(c) - 97 for c in w] for w in input().split()]
h = list(map(int, input().split()))
t = {}
o = {}
m = {}
v = 1
for (i, w) in enumerate(g):
	x = 0
	for c in w:
		if (x, c) not in t:
			t[x, c] = v
			v += 1
		x = t[x, c]
	if x not in o:
		o[x] = []
	o[x].append(i)
for i in range(26):
	if (0, i) not in t:
		t[0, i] = 0
for (u, v) in o.items():
	z = [0] * (len(v) + 1)
	for (i, x) in enumerate(v):
		z[i + 1] = z[i] + h[x]
	m[u] = z
e = {}
for (u, v) in t.keys():
	if u not in e:
		e[u] = []
	e[u].append(v)
f = {}
q = deque()
for a in range(26):
	s = t[0, a]
	if s != 0:
		q.append(s)
		f[s] = 0
while q:
	r = q.popleft()
	if r in e:
		for a in e[r]:
			s = t[r, a]
			q.append(s)
			x = f[r]
			while (x, a) not in t:
				x = f[x]
			f[s] = t[x, a]
worst = float('inf')
best = float('-inf')
s = int(input())
for _ in range(s):
	(start, end, d) = input().split()
	start = int(start)
	end = int(end)
	d = [ord(c) - 97 for c in d]
	z = 0
	x = 0
	for c in d:
		while (x, c) not in t:
			x = f[x]
		x = t[x, c]
		y = x
		while y != 0:
			if y in o:
				u = bisect_left(o[y], start)
				v = bisect_right(o[y], end)
				z += m[y][v] - m[y][u]
			y = f[y]
	worst = min(worst, z)
	best = max(best, z)
print(worst, best)


from math import inf
from collections import defaultdict
from bisect import bisect_left as bLeft, bisect_right as bRight

def how(strand, shortRange):
	global gMap, subs, largest, check
	(h, ls) = (0, len(strand))
	for f in range(ls):
		for j in range(1, largest + 1):
			if f + j > ls:
				break
			sub = strand[f:f + j]
			if check and sub not in subs:
				break
			if sub not in gMap:
				continue
			(ids, hts, ht) = gMap[sub]
			(bl, br) = (bLeft(ids, first), bRight(ids, last))
			h += sum(hts[bl:br]) if shortRange else ht - sum(hts[:bl]) - sum(hts[br:])
	return h
global gMap, subs, largest, check
n = int(input())
genes = input().rstrip().split()
healths = list(map(int, input().rstrip().split()))
gMap = defaultdict(lambda : [[], [], 0])
subs = set()
for (i, g) in enumerate(genes):
	h = healths[i]
	gMap[g][0].append(i)
	gMap[g][1].append(h)
	gMap[g][2] += h
	for j in range(1, min(len(g), 500) + 1):
		subs.add(g[:j])
largest = max(list(map(len, genes)))
del genes, healths
(MIN, MAX) = (inf, -inf)
check = len(subs) > 2 * len(gMap)
for _ in range(int(input())):
	firstLastd = input().split()
	first = int(firstLastd[0])
	last = int(firstLastd[1])
	strand = firstLastd[2]
	h = how(strand, last - first + 1 < n / 2)
	if h < MIN:
		MIN = h
	if h > MAX:
		MAX = h
print(MIN, MAX)


from math import inf
from bisect import bisect_left as bLeft, bisect_right as bRight
from collections import defaultdict

def getHealth(seq, first, last, largest):
	(h, ls) = (0, len(seq))
	for f in range(ls):
		for j in range(1, largest + 1):
			if f + j > ls:
				break
			sub = seq[f:f + j]
			if sub not in subs:
				break
			if sub not in gMap:
				continue
			(ids, hs) = gMap[sub]
			h += hs[bRight(ids, last)] - hs[bLeft(ids, first)]
	return h
howGenes = int(input())
genes = input().rstrip().split()
healths = list(map(int, input().rstrip().split()))
howStrands = int(input())
gMap = defaultdict(lambda : [[], [0]])
subs = set()
for (id, gene) in enumerate(genes):
	gMap[gene][0].append(id)
	for j in range(1, min(len(gene), 500) + 1):
		subs.add(gene[:j])
for v in gMap.values():
	for (i, ix) in enumerate(v[0]):
		v[1].append(v[1][i] + healths[ix])
largest = max(list(map(len, genes)))
(hMin, hMax) = (inf, 0)
for _ in range(howStrands):
	firstLastd = input().split()
	first = int(firstLastd[0])
	last = int(firstLastd[1])
	strand = firstLastd[2]
	h = getHealth(strand, first, last, largest)
	(hMin, hMax) = (min(hMin, h), max(hMax, h))
print(hMin, hMax)


from math import inf
from bisect import bisect_left as bLeft, bisect_right as bRight
from collections import defaultdict

def getHealth(seq, first, last, largest):
	(h, ls) = (0, len(seq))
	for f in range(ls):
		for j in range(1, largest + 1):
			if f + j > ls:
				break
			sub = seq[f:f + j]
			if sub not in subs:
				break
			if sub not in gMap:
				continue
			(ids, hs) = gMap[sub]
			h += hs[bRight(ids, last)] - hs[bLeft(ids, first)]
	return h
howGenes = int(input())
genes = input().rstrip().split()
healths = list(map(int, input().rstrip().split()))
howStrands = int(input())
gMap = defaultdict(lambda : [[], [0]])
subs = set()
for (id, gene) in enumerate(genes):
	gMap[gene][0].append(id)
	for j in range(1, min(len(gene), 500) + 1):
		subs.add(gene[:j])
for v in gMap.values():
	for (i, ix) in enumerate(v[0]):
		v[1].append(v[1][i] + healths[ix])
largest = max(list(map(len, genes)))
(hMin, hMax) = (inf, 0)
for _ in range(howStrands):
	firstLastd = input().split()
	first = int(firstLastd[0])
	last = int(firstLastd[1])
	strand = firstLastd[2]
	h = getHealth(strand, first, last, largest)
	(hMin, hMax) = (min(hMin, h), max(hMax, h))
print(hMin, hMax)


from math import inf
from bisect import bisect_left as bLeft, bisect_right as bRight
from collections import defaultdict

def getHealth(seq, first, last, largest):
	(h, ls) = (0, len(seq))
	for f in range(ls):
		for j in range(1, largest + 1):
			if f + j > ls:
				break
			sub = seq[f:f + j]
			if sub not in subs:
				break
			if sub not in gMap:
				continue
			(ids, hs) = gMap[sub]
			h += hs[bRight(ids, last)] - hs[bLeft(ids, first)]
	return h
howGenes = int(input())
genes = input().rstrip().split()
healths = list(map(int, input().rstrip().split()))
howStrands = int(input())
gMap = defaultdict(lambda : [[], [0]])
subs = set()
for (id, gene) in enumerate(genes):
	gMap[gene][0].append(id)
	for j in range(1, min(len(gene), 500) + 1):
		subs.add(gene[:j])
for v in gMap.values():
	for (i, ix) in enumerate(v[0]):
		v[1].append(v[1][i] + healths[ix])
largest = max(list(map(len, genes)))
(hMin, hMax) = (inf, 0)
for _ in range(howStrands):
	firstLastd = input().split()
	first = int(firstLastd[0])
	last = int(firstLastd[1])
	strand = firstLastd[2]
	h = getHealth(strand, first, last, largest)
	(hMin, hMax) = (min(hMin, h), max(hMax, h))
print(hMin, hMax)


from math import inf
from bisect import bisect_left as bLeft, bisect_right as bRight
from collections import defaultdict

def getHealth(seq, first, last, largest):
	(h, ls) = (0, len(seq))
	for f in range(ls):
		for j in range(1, largest + 1):
			if f + j > ls:
				break
			sub = seq[f:f + j]
			if sub not in subs:
				break
			if sub not in gMap:
				continue
			(ids, hs) = gMap[sub]
			h += hs[bRight(ids, last)] - hs[bLeft(ids, first)]
	return h
howGenes = int(input())
genes = input().rstrip().split()
healths = list(map(int, input().rstrip().split()))
howStrands = int(input())
gMap = defaultdict(lambda : [[], [0]])
subs = set()
for (id, gene) in enumerate(genes):
	gMap[gene][0].append(id)
	for j in range(1, min(len(gene), 500) + 1):
		subs.add(gene[:j])
for v in gMap.values():
	for (i, ix) in enumerate(v[0]):
		v[1].append(v[1][i] + healths[ix])
largest = max(list(map(len, genes)))
(hMin, hMax) = (inf, 0)
for _ in range(howStrands):
	firstLastd = input().split()
	first = int(firstLastd[0])
	last = int(firstLastd[1])
	strand = firstLastd[2]
	h = getHealth(strand, first, last, largest)
	(hMin, hMax) = (min(hMin, h), max(hMax, h))
print(hMin, hMax)


from math import inf
from bisect import bisect_left as bLeft, bisect_right as bRight
from collections import defaultdict

def getHealth(seq, first, last, largest):
	(h, ls) = (0, len(seq))
	for f in range(ls):
		for j in range(1, largest + 1):
			if f + j > ls:
				break
			sub = seq[f:f + j]
			if sub not in subs:
				break
			if sub not in gMap:
				continue
			(ids, hs) = gMap[sub]
			h += hs[bRight(ids, last)] - hs[bLeft(ids, first)]
	return h
howGenes = int(input())
genes = input().rstrip().split()
healths = list(map(int, input().rstrip().split()))
howStrands = int(input())
gMap = defaultdict(lambda : [[], [0]])
subs = set()
for (id, gene) in enumerate(genes):
	gMap[gene][0].append(id)
	for j in range(1, min(len(gene), 500) + 1):
		subs.add(gene[:j])
for v in gMap.values():
	for (i, ix) in enumerate(v[0]):
		v[1].append(v[1][i] + healths[ix])
largest = max(list(map(len, genes)))
(hMin, hMax) = (inf, 0)
for _ in range(howStrands):
	firstLastd = input().split()
	first = int(firstLastd[0])
	last = int(firstLastd[1])
	strand = firstLastd[2]
	h = getHealth(strand, first, last, largest)
	(hMin, hMax) = (min(hMin, h), max(hMax, h))
print(hMin, hMax)


from math import inf
from bisect import bisect_left as bLeft, bisect_right as bRight
from collections import defaultdict

def getHealth(seq, first, last, largest):
	(h, ls) = (0, len(seq))
	for f in range(ls):
		for j in range(1, largest + 1):
			if f + j > ls:
				break
			sub = seq[f:f + j]
			if sub not in subs:
				break
			if sub not in gMap:
				continue
			(ids, hs) = gMap[sub]
			h += hs[bRight(ids, last)] - hs[bLeft(ids, first)]
	return h
howGenes = int(input())
genes = input().rstrip().split()
healths = list(map(int, input().rstrip().split()))
howStrands = int(input())
gMap = defaultdict(lambda : [[], [0]])
subs = set()
for (id, gene) in enumerate(genes):
	gMap[gene][0].append(id)
	for j in range(1, min(len(gene), 500) + 1):
		subs.add(gene[:j])
for v in gMap.values():
	for (i, ix) in enumerate(v[0]):
		v[1].append(v[1][i] + healths[ix])
largest = max(list(map(len, genes)))
(hMin, hMax) = (inf, 0)
for _ in range(howStrands):
	firstLastd = input().split()
	first = int(firstLastd[0])
	last = int(firstLastd[1])
	strand = firstLastd[2]
	h = getHealth(strand, first, last, largest)
	(hMin, hMax) = (min(hMin, h), max(hMax, h))
print(hMin, hMax)


from math import inf
from bisect import bisect_left as bLeft, bisect_right as bRight
from collections import defaultdict

def getHealth(seq, first, last, largest):
	(h, ls) = (0, len(seq))
	for f in range(ls):
		for j in range(1, largest + 1):
			if f + j > ls:
				break
			sub = seq[f:f + j]
			if sub not in subs:
				break
			if sub not in gMap:
				continue
			(ids, hs) = gMap[sub]
			h += hs[bRight(ids, last)] - hs[bLeft(ids, first)]
	return h
howGenes = int(input())
genes = input().rstrip().split()
healths = list(map(int, input().rstrip().split()))
howStrands = int(input())
gMap = defaultdict(lambda : [[], [0]])
subs = set()
for (id, gene) in enumerate(genes):
	gMap[gene][0].append(id)
	for j in range(1, min(len(gene), 500) + 1):
		subs.add(gene[:j])
for v in gMap.values():
	for (i, ix) in enumerate(v[0]):
		v[1].append(v[1][i] + healths[ix])
largest = max(list(map(len, genes)))
(hMin, hMax) = (inf, 0)
for _ in range(howStrands):
	firstLastd = input().split()
	first = int(firstLastd[0])
	last = int(firstLastd[1])
	strand = firstLastd[2]
	h = getHealth(strand, first, last, largest)
	(hMin, hMax) = (min(hMin, h), max(hMax, h))
print(hMin, hMax)


from math import inf
from bisect import bisect_left as bLeft, bisect_right as bRight
from collections import defaultdict

def getHealth(seq, first, last, largest):
	(h, ls) = (0, len(seq))
	for f in range(ls):
		for j in range(1, largest + 1):
			if f + j > ls:
				break
			sub = seq[f:f + j]
			if sub not in subs:
				break
			if sub not in gMap:
				continue
			(ids, hs) = gMap[sub]
			h += hs[bRight(ids, last)] - hs[bLeft(ids, first)]
	return h
howGenes = int(input())
genes = input().rstrip().split()
healths = list(map(int, input().rstrip().split()))
howStrands = int(input())
gMap = defaultdict(lambda : [[], [0]])
subs = set()
for (id, gene) in enumerate(genes):
	gMap[gene][0].append(id)
	for j in range(1, min(len(gene), 500) + 1):
		subs.add(gene[:j])
for v in gMap.values():
	for (i, ix) in enumerate(v[0]):
		v[1].append(v[1][i] + healths[ix])
largest = max(list(map(len, genes)))
(hMin, hMax) = (inf, 0)
for _ in range(howStrands):
	firstLastd = input().split()
	first = int(firstLastd[0])
	last = int(firstLastd[1])
	strand = firstLastd[2]
	h = getHealth(strand, first, last, largest)
	(hMin, hMax) = (min(hMin, h), max(hMax, h))
print(hMin, hMax)


from math import inf
from bisect import bisect_left as bLeft, bisect_right as bRight
from collections import defaultdict

def getHealth(seq, first, last, largest):
	(h, ls) = (0, len(seq))
	for f in range(ls):
		for j in range(1, largest + 1):
			if f + j > ls:
				break
			sub = seq[f:f + j]
			if sub not in subs:
				break
			if sub not in gMap:
				continue
			(ids, hs) = gMap[sub]
			h += hs[bRight(ids, last)] - hs[bLeft(ids, first)]
	return h
howGenes = int(input())
genes = input().rstrip().split()
healths = list(map(int, input().rstrip().split()))
howStrands = int(input())
gMap = defaultdict(lambda : [[], [0]])
subs = set()
for (id, gene) in enumerate(genes):
	gMap[gene][0].append(id)
	for j in range(1, min(len(gene), 500) + 1):
		subs.add(gene[:j])
for v in gMap.values():
	for (i, ix) in enumerate(v[0]):
		v[1].append(v[1][i] + healths[ix])
largest = max(list(map(len, genes)))
(hMin, hMax) = (inf, 0)
for _ in range(howStrands):
	firstLastd = input().split()
	first = int(firstLastd[0])
	last = int(firstLastd[1])
	strand = firstLastd[2]
	h = getHealth(strand, first, last, largest)
	(hMin, hMax) = (min(hMin, h), max(hMax, h))
print(hMin, hMax)


from math import inf
from bisect import bisect_left as bLeft, bisect_right as bRight
from collections import defaultdict

def getHealth(seq, first, last, largest):
	(h, ls) = (0, len(seq))
	for f in range(ls):
		for j in range(1, largest + 1):
			if f + j > ls:
				break
			sub = seq[f:f + j]
			if sub not in subs:
				break
			if sub not in gMap:
				continue
			(ids, hs) = gMap[sub]
			h += hs[bRight(ids, last)] - hs[bLeft(ids, first)]
	return h
howGenes = int(input())
genes = input().rstrip().split()
healths = list(map(int, input().rstrip().split()))
howStrands = int(input())
gMap = defaultdict(lambda : [[], [0]])
subs = set()
for (id, gene) in enumerate(genes):
	gMap[gene][0].append(id)
	for j in range(1, min(len(gene), 500) + 1):
		subs.add(gene[:j])
for v in gMap.values():
	for (i, ix) in enumerate(v[0]):
		v[1].append(v[1][i] + healths[ix])
largest = max(list(map(len, genes)))
(hMin, hMax) = (inf, 0)
for _ in range(howStrands):
	firstLastd = input().split()
	first = int(firstLastd[0])
	last = int(firstLastd[1])
	strand = firstLastd[2]
	h = getHealth(strand, first, last, largest)
	(hMin, hMax) = (min(hMin, h), max(hMax, h))
print(hMin, hMax)


from math import inf
from bisect import bisect_left as bLeft, bisect_right as bRight
from collections import defaultdict

def getHealth(seq, first, last, largest):
	(h, ls) = (0, len(seq))
	for f in range(ls):
		for j in range(1, largest + 1):
			if f + j > ls:
				break
			sub = seq[f:f + j]
			if sub not in subs:
				break
			if sub not in gMap:
				continue
			(ids, hs) = gMap[sub]
			h += hs[bRight(ids, last)] - hs[bLeft(ids, first)]
	return h
howGenes = int(input())
genes = input().rstrip().split()
healths = list(map(int, input().rstrip().split()))
howStrands = int(input())
gMap = defaultdict(lambda : [[], [0]])
subs = set()
for (id, gene) in enumerate(genes):
	gMap[gene][0].append(id)
	for j in range(1, min(len(gene), 500) + 1):
		subs.add(gene[:j])
for v in gMap.values():
	for (i, ix) in enumerate(v[0]):
		v[1].append(v[1][i] + healths[ix])
largest = max(list(map(len, genes)))
(hMin, hMax) = (inf, 0)
for _ in range(howStrands):
	firstLastd = input().split()
	first = int(firstLastd[0])
	last = int(firstLastd[1])
	strand = firstLastd[2]
	h = getHealth(strand, first, last, largest)
	(hMin, hMax) = (min(hMin, h), max(hMax, h))
print(hMin, hMax)


from math import inf
from bisect import bisect_left as bLeft, bisect_right as bRight
from collections import defaultdict

def getHealth(seq, first, last, largest):
	(h, ls) = (0, len(seq))
	for f in range(ls):
		for j in range(1, largest + 1):
			if f + j > ls:
				break
			sub = seq[f:f + j]
			if sub not in subs:
				break
			if sub not in gMap:
				continue
			(ids, hs) = gMap[sub]
			h += hs[bRight(ids, last)] - hs[bLeft(ids, first)]
	return h
howGenes = int(input())
genes = input().rstrip().split()
healths = list(map(int, input().rstrip().split()))
howStrands = int(input())
gMap = defaultdict(lambda : [[], [0]])
subs = set()
for (id, gene) in enumerate(genes):
	gMap[gene][0].append(id)
	for j in range(1, min(len(gene), 500) + 1):
		subs.add(gene[:j])
for v in gMap.values():
	for (i, ix) in enumerate(v[0]):
		v[1].append(v[1][i] + healths[ix])
largest = max(list(map(len, genes)))
(hMin, hMax) = (inf, 0)
for _ in range(howStrands):
	firstLastd = input().split()
	first = int(firstLastd[0])
	last = int(firstLastd[1])
	strand = firstLastd[2]
	h = getHealth(strand, first, last, largest)
	(hMin, hMax) = (min(hMin, h), max(hMax, h))
print(hMin, hMax)


from math import inf
from bisect import bisect_left as bLeft, bisect_right as bRight
from collections import defaultdict

def getHealth(seq, first, last, largest):
	(h, ls) = (0, len(seq))
	for f in range(ls):
		for j in range(1, largest + 1):
			if f + j > ls:
				break
			sub = seq[f:f + j]
			if sub not in subs:
				break
			if sub not in gMap:
				continue
			(ids, hs) = gMap[sub]
			h += hs[bRight(ids, last)] - hs[bLeft(ids, first)]
	return h
howGenes = int(input())
genes = input().rstrip().split()
healths = list(map(int, input().rstrip().split()))
howStrands = int(input())
gMap = defaultdict(lambda : [[], [0]])
subs = set()
for (id, gene) in enumerate(genes):
	gMap[gene][0].append(id)
	for j in range(1, min(len(gene), 500) + 1):
		subs.add(gene[:j])
for v in gMap.values():
	for (i, ix) in enumerate(v[0]):
		v[1].append(v[1][i] + healths[ix])
largest = max(list(map(len, genes)))
(hMin, hMax) = (inf, 0)
for _ in range(howStrands):
	firstLastd = input().split()
	first = int(firstLastd[0])
	last = int(firstLastd[1])
	strand = firstLastd[2]
	h = getHealth(strand, first, last, largest)
	(hMin, hMax) = (min(hMin, h), max(hMax, h))
print(hMin, hMax)


from math import inf
from bisect import bisect_left as bLeft, bisect_right as bRight
from collections import defaultdict

def getHealth(seq, first, last, largest):
	(h, ls) = (0, len(seq))
	for f in range(ls):
		for j in range(1, largest + 1):
			if f + j > ls:
				break
			sub = seq[f:f + j]
			if sub not in subs:
				break
			if sub not in gMap:
				continue
			(ids, hs) = gMap[sub]
			h += hs[bRight(ids, last)] - hs[bLeft(ids, first)]
	return h
howGenes = int(input())
genes = input().rstrip().split()
healths = list(map(int, input().rstrip().split()))
howStrands = int(input())
gMap = defaultdict(lambda : [[], [0]])
subs = set()
for (id, gene) in enumerate(genes):
	gMap[gene][0].append(id)
	for j in range(1, min(len(gene), 500) + 1):
		subs.add(gene[:j])
for v in gMap.values():
	for (i, ix) in enumerate(v[0]):
		v[1].append(v[1][i] + healths[ix])
largest = max(list(map(len, genes)))
(hMin, hMax) = (inf, 0)
for _ in range(howStrands):
	firstLastd = input().split()
	first = int(firstLastd[0])
	last = int(firstLastd[1])
	strand = firstLastd[2]
	h = getHealth(strand, first, last, largest)
	(hMin, hMax) = (min(hMin, h), max(hMax, h))
print(hMin, hMax)


import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

def dna_health(start, end, s):
	(h, lens) = (0, len(s))
	for i in range(lens):
		for j in range(1, maxglen + 1):
			if i + j > lens:
				break
			seq = s[i:i + j]
			if seq not in subs:
				break
			if seq not in gh:
				continue
			(ids, hs) = gh[seq]
			h += hs[bisect_right(ids, end)] - hs[bisect_left(ids, start)]
	return h
n = int(input())
genes = input().split()
health = list(map(int, input().split()))
subs = set()
gh = defaultdict(lambda : [[], [0]])
maxglen = 0
for (id, gene) in enumerate(genes):
	gh[gene][0].append(id)
	maxglen = max(maxglen, len(gene))
	for j in range(1, min(500, len(gene)) + 1):
		subs.add(gene[:j])
for v in gh.values():
	for (i, id) in enumerate(v[0]):
		v[1].append(v[1][i] + health[id])
s = int(input())
(minh, maxh) = (math.inf, 0)
for _ in range(s):
	(start, end, strand) = input().split()
	(start, end) = (int(start), int(end))
	hval = dna_health(start, end, strand)
	minh = min(hval, minh)
	maxh = max(hval, maxh)
print(minh, maxh, sep=' ')


from math import inf
from bisect import bisect_left as bLeft, bisect_right as bRight
from collections import defaultdict

def getHealth(seq, first, last, largest):
	(h, ls) = (0, len(seq))
	for f in range(ls):
		for j in range(1, largest + 1):
			if f + j > ls:
				break
			sub = seq[f:f + j]
			if sub not in subs:
				break
			if sub not in gMap:
				continue
			(ids, hs) = gMap[sub]
			h += hs[bRight(ids, last)] - hs[bLeft(ids, first)]
	return h
howGenes = int(input())
genes = input().rstrip().split()
healths = list(map(int, input().rstrip().split()))
howStrands = int(input())
gMap = defaultdict(lambda : [[], [0]])
subs = set()
for (id, gene) in enumerate(genes):
	gMap[gene][0].append(id)
	for j in range(1, min(len(gene), 500) + 1):
		subs.add(gene[:j])
for v in gMap.values():
	for (i, ix) in enumerate(v[0]):
		v[1].append(v[1][i] + healths[ix])
largest = max(list(map(len, genes)))
(hMin, hMax) = (inf, 0)
for _ in range(howStrands):
	firstLastd = input().split()
	first = int(firstLastd[0])
	last = int(firstLastd[1])
	strand = firstLastd[2]
	h = getHealth(strand, first, last, largest)
	(hMin, hMax) = (min(hMin, h), max(hMax, h))
print(hMin, hMax)


import math
import os
import random
import re
import sys
from math import inf
from bisect import bisect_left as bLeft, bisect_right as bRight
from collections import defaultdict

def getHealth(seq, first, last, largest):
	(h, ls) = (0, len(seq))
	for f in range(ls):
		for j in range(1, largest + 1):
			if f + j > ls:
				break
			sub = seq[f:f + j]
			if sub not in subs:
				break
			if sub not in gMap:
				continue
			(ids, hs) = gMap[sub]
			h += hs[bRight(ids, last)] - hs[bLeft(ids, first)]
	return h
howGenes = int(input())
genes = input().rstrip().split()
healths = list(map(int, input().rstrip().split()))
howStrands = int(input())
gMap = defaultdict(lambda : [[], [0]])
subs = set()
for (id, gene) in enumerate(genes):
	gMap[gene][0].append(id)
	for j in range(1, min(len(gene), 500) + 1):
		subs.add(gene[:j])
for v in gMap.values():
	for (i, ix) in enumerate(v[0]):
		v[1].append(v[1][i] + healths[ix])
largest = max(list(map(len, genes)))
(hMin, hMax) = (inf, 0)
for _ in range(howStrands):
	firstLastd = input().split()
	first = int(firstLastd[0])
	last = int(firstLastd[1])
	strand = firstLastd[2]
	h = getHealth(strand, first, last, largest)
	(hMin, hMax) = (min(hMin, h), max(hMax, h))
print(hMin, hMax)


from math import inf
from bisect import bisect_left as bLeft, bisect_right as bRight
from collections import defaultdict

def getHealth(seq, first, last, largest):
	(h, ls) = (0, len(seq))
	for f in range(ls):
		for j in range(1, largest + 1):
			if f + j > ls:
				break
			sub = seq[f:f + j]
			if sub not in subs:
				break
			if sub not in gMap:
				continue
			(ids, hs) = gMap[sub]
			h += hs[bRight(ids, last)] - hs[bLeft(ids, first)]
	return h
howGenes = int(input())
genes = input().rstrip().split()
healths = list(map(int, input().rstrip().split()))
howStrands = int(input())
gMap = defaultdict(lambda : [[], [0]])
subs = set()
for (id, gene) in enumerate(genes):
	gMap[gene][0].append(id)
	for j in range(1, min(len(gene), 500) + 1):
		subs.add(gene[:j])
for v in gMap.values():
	for (i, ix) in enumerate(v[0]):
		v[1].append(v[1][i] + healths[ix])
largest = max(list(map(len, genes)))
(hMin, hMax) = (inf, 0)
for _ in range(howStrands):
	firstLastd = input().split()
	first = int(firstLastd[0])
	last = int(firstLastd[1])
	strand = firstLastd[2]
	h = getHealth(strand, first, last, largest)
	(hMin, hMax) = (min(hMin, h), max(hMax, h))
print(hMin, hMax)


from math import inf
from bisect import bisect_left as bLeft, bisect_right as bRight
from collections import defaultdict

def getHealth(seq, first, last, largest):
	(h, ls) = (0, len(seq))
	for f in range(ls):
		for j in range(1, largest + 1):
			if f + j > ls:
				break
			sub = seq[f:f + j]
			if sub not in subs:
				break
			if sub not in gMap:
				continue
			(ids, hs) = gMap[sub]
			h += hs[bRight(ids, last)] - hs[bLeft(ids, first)]
	return h
howGenes = int(input())
genes = input().rstrip().split()
healths = list(map(int, input().rstrip().split()))
howStrands = int(input())
gMap = defaultdict(lambda : [[], [0]])
subs = set()
for (id, gene) in enumerate(genes):
	gMap[gene][0].append(id)
	for j in range(1, min(len(gene), 500) + 1):
		subs.add(gene[:j])
for v in gMap.values():
	for (i, ix) in enumerate(v[0]):
		v[1].append(v[1][i] + healths[ix])
largest = max(list(map(len, genes)))
(hMin, hMax) = (inf, 0)
for _ in range(howStrands):
	firstLastd = input().split()
	first = int(firstLastd[0])
	last = int(firstLastd[1])
	strand = firstLastd[2]
	h = getHealth(strand, first, last, largest)
	(hMin, hMax) = (min(hMin, h), max(hMax, h))
print(hMin, hMax)


from math import inf
from bisect import bisect_left as bLeft, bisect_right as bRight
from collections import defaultdict

def getHealth(seq, first, last, largest):
	(h, ls) = (0, len(seq))
	for f in range(ls):
		for j in range(1, largest + 1):
			if f + j > ls:
				break
			sub = seq[f:f + j]
			if sub not in subs:
				break
			if sub not in gMap:
				continue
			(ids, hs) = gMap[sub]
			h += hs[bRight(ids, last)] - hs[bLeft(ids, first)]
	return h
howGenes = int(input())
genes = input().rstrip().split()
healths = list(map(int, input().rstrip().split()))
howStrands = int(input())
gMap = defaultdict(lambda : [[], [0]])
subs = set()
for (id, gene) in enumerate(genes):
	gMap[gene][0].append(id)
	for j in range(1, min(len(gene), 500) + 1):
		subs.add(gene[:j])
for v in gMap.values():
	for (i, ix) in enumerate(v[0]):
		v[1].append(v[1][i] + healths[ix])
largest = max(list(map(len, genes)))
(hMin, hMax) = (inf, 0)
for _ in range(howStrands):
	firstLastd = input().split()
	first = int(firstLastd[0])
	last = int(firstLastd[1])
	strand = firstLastd[2]
	h = getHealth(strand, first, last, largest)
	(hMin, hMax) = (min(hMin, h), max(hMax, h))
print(hMin, hMax)


from math import inf
from bisect import bisect_left as bLeft, bisect_right as bRight
from collections import defaultdict

def getHealth(seq, first, last, largest):
	(h, ls) = (0, len(seq))
	for f in range(ls):
		for j in range(1, largest + 1):
			if f + j > ls:
				break
			sub = seq[f:f + j]
			if sub not in subs:
				break
			if sub not in gMap:
				continue
			(ids, hs) = gMap[sub]
			h += hs[bRight(ids, last)] - hs[bLeft(ids, first)]
	return h
howGenes = int(input())
genes = input().rstrip().split()
healths = list(map(int, input().rstrip().split()))
howStrands = int(input())
gMap = defaultdict(lambda : [[], [0]])
subs = set()
for (id, gene) in enumerate(genes):
	gMap[gene][0].append(id)
	for j in range(1, min(len(gene), 500) + 1):
		subs.add(gene[:j])
for v in gMap.values():
	for (i, ix) in enumerate(v[0]):
		v[1].append(v[1][i] + healths[ix])
largest = max(list(map(len, genes)))
(hMin, hMax) = (inf, 0)
for _ in range(howStrands):
	firstLastd = input().split()
	first = int(firstLastd[0])
	last = int(firstLastd[1])
	strand = firstLastd[2]
	h = getHealth(strand, first, last, largest)
	(hMin, hMax) = (min(hMin, h), max(hMax, h))
print(hMin, hMax)


import math
import os
import random
import re
import sys
from bisect import bisect_left as biL, bisect_right as biR
n = int(input())
genes = input().rstrip().split()
health = list(map(int, input().rstrip().split()))
s = int(input())
geneDict = {}
for i in range(len(genes)):
	x = geneDict
	for j in range(len(genes[i])):
		if not genes[i][j] in x:
			x[genes[i][j]] = {} if j < len(genes[i]) - 1 else {'-': [i], '#': [health[i]]}
			x = x[genes[i][j]]
		else:
			x = x[genes[i][j]]
			if j == len(genes[i]) - 1:
				if '-' in x:
					insIdx = biL(x['-'], i)
					x['-'].insert(insIdx, i)
					x['#'].insert(insIdx, health[i])
				else:
					x['-'] = [i]
					x['#'] = [health[i]]
maxHealth = -1
minHealth = -1
for s_itr in range(s):
	firstLastd = input().split()
	first = int(firstLastd[0])
	last = int(firstLastd[1])
	d = firstLastd[2]
	tempHealth = 0
	for i in range(len(d)):
		x = geneDict
		pos = i
		while pos < len(d) and d[pos] in x:
			x = x[d[pos]]
			if '-' in x:
				if not '+' in x:
					x['+'] = [k for k in x['#']]
					for k in range(1, len(x['+'])):
						x['+'][k] += x['+'][k - 1]
				lIndex = biL(x['-'], first)
				uIndex = biR(x['-'], last)
				if lIndex < uIndex and lIndex <= len(x['+']) - 1 and (uIndex > 0):
					tempHealth += x['+'][uIndex - 1] - (x['+'][lIndex - 1] if lIndex > 0 else 0)
			pos = pos + 1
	if maxHealth == -1:
		maxHealth = tempHealth
		minHealth = tempHealth
	if tempHealth > maxHealth:
		maxHealth = tempHealth
	if tempHealth < minHealth:
		minHealth = tempHealth
print(' '.join([str(minHealth), str(maxHealth)]))


from math import inf
from bisect import bisect_left as bLeft, bisect_right as bRight
from collections import defaultdict

def getHealth(seq, first, last, largest):
	(h, ls) = (0, len(seq))
	for f in range(ls):
		for j in range(1, largest + 1):
			if f + j > ls:
				break
			sub = seq[f:f + j]
			if sub not in subs:
				break
			if sub not in gMap:
				continue
			(ids, hs) = gMap[sub]
			h += hs[bRight(ids, last)] - hs[bLeft(ids, first)]
	return h
howGenes = int(input())
genes = input().rstrip().split()
healths = list(map(int, input().rstrip().split()))
howStrands = int(input())
gMap = defaultdict(lambda : [[], [0]])
subs = set()
for (id, gene) in enumerate(genes):
	gMap[gene][0].append(id)
	for j in range(1, min(len(gene), 500) + 1):
		subs.add(gene[:j])
for v in gMap.values():
	for (i, ix) in enumerate(v[0]):
		v[1].append(v[1][i] + healths[ix])
largest = max(list(map(len, genes)))
(hMin, hMax) = (inf, 0)
for _ in range(howStrands):
	firstLastd = input().split()
	first = int(firstLastd[0])
	last = int(firstLastd[1])
	strand = firstLastd[2]
	h = getHealth(strand, first, last, largest)
	(hMin, hMax) = (min(hMin, h), max(hMax, h))
print(hMin, hMax)


from math import inf
from bisect import bisect_left as bLeft, bisect_right as bRight
from collections import defaultdict

def getHealth(seq, first, last, largest):
	(h, ls) = (0, len(seq))
	for f in range(ls):
		for j in range(1, largest + 1):
			if f + j > ls:
				break
			sub = seq[f:f + j]
			if sub not in subs:
				break
			if sub not in gMap:
				continue
			(ids, hs) = gMap[sub]
			h += hs[bRight(ids, last)] - hs[bLeft(ids, first)]
	return h
howGenes = int(input())
genes = input().rstrip().split()
healths = list(map(int, input().rstrip().split()))
howStrands = int(input())
gMap = defaultdict(lambda : [[], [0]])
subs = set()
for (id, gene) in enumerate(genes):
	gMap[gene][0].append(id)
	for j in range(1, min(len(gene), 500) + 1):
		subs.add(gene[:j])
for v in gMap.values():
	for (i, ix) in enumerate(v[0]):
		v[1].append(v[1][i] + healths[ix])
largest = max(list(map(len, genes)))
(hMin, hMax) = (inf, 0)
for _ in range(howStrands):
	firstLastd = input().split()
	first = int(firstLastd[0])
	last = int(firstLastd[1])
	strand = firstLastd[2]
	h = getHealth(strand, first, last, largest)
	(hMin, hMax) = (min(hMin, h), max(hMax, h))
print(hMin, hMax)


from math import inf
from bisect import bisect_left as bLeft, bisect_right as bRight
from collections import defaultdict

def getHealth(seq, first, last, largest):
	(h, ls) = (0, len(seq))
	for f in range(ls):
		for j in range(1, largest + 1):
			if f + j > ls:
				break
			sub = seq[f:f + j]
			if sub not in subs:
				break
			if sub not in gMap:
				continue
			(ids, hs) = gMap[sub]
			h += hs[bRight(ids, last)] - hs[bLeft(ids, first)]
	return h
howGenes = int(input())
genes = input().rstrip().split()
healths = list(map(int, input().rstrip().split()))
howStrands = int(input())
gMap = defaultdict(lambda : [[], [0]])
subs = set()
for (id, gene) in enumerate(genes):
	gMap[gene][0].append(id)
	for j in range(1, min(len(gene), 500) + 1):
		subs.add(gene[:j])
for v in gMap.values():
	for (i, ix) in enumerate(v[0]):
		v[1].append(v[1][i] + healths[ix])
largest = max(list(map(len, genes)))
(hMin, hMax) = (inf, 0)
for _ in range(howStrands):
	firstLastd = input().split()
	first = int(firstLastd[0])
	last = int(firstLastd[1])
	strand = firstLastd[2]
	h = getHealth(strand, first, last, largest)
	(hMin, hMax) = (min(hMin, h), max(hMax, h))
print(hMin, hMax)


from bisect import bisect_left, bisect_right
from collections import defaultdict
from sys import stdin

def get_health(Trie, subs, seq, first, last, largest):
	ans = 0
	seq_len = len(seq)
	for i in range(seq_len):
		for j in range(1, largest + 1):
			if i + j > seq_len:
				break
			sub = seq[i:i + j]
			if sub not in subs:
				break
			if sub not in Trie:
				continue
			(idx, prefix) = Trie[sub]
			ans += prefix[bisect_right(idx, last)] - prefix[bisect_left(idx, first)]
	return ans

def solve():
	_ = int(stdin.readline())
	genes = stdin.readline().rstrip().split()
	health = [int(k) for k in stdin.readline().split()]
	Trie = defaultdict(list)
	subs = set()
	i = 0
	largest = 0
	for g in genes:
		if g not in Trie:
			Trie[g] = [[], []]
		Trie[g][0].append(i)
		i += 1
		l = len(g)
		for j in range(1, l + 1):
			subs.add(g[:j])
		if l > largest:
			largest = l
	for (indexes, prefix) in Trie.values():
		sm = 0
		prefix.append(sm)
		for x in indexes:
			sm += health[x]
			prefix.append(sm)
	(Min, Max) = (10 ** 20, 0)
	for _ in range(int(stdin.readline())):
		firstLastd = stdin.readline().split()
		first = int(firstLastd[0])
		last = int(firstLastd[1])
		strand = firstLastd[2]
		ans = get_health(Trie, subs, strand, first, last, largest)
		(Min, Max) = (min(Min, ans), max(Max, ans))
	print(Min, Max)
solve()


from math import inf
from bisect import bisect_left as bLeft, bisect_right as bRight
from collections import defaultdict

def getHealth(seq, first, last, largest):
	(h, ls) = (0, len(seq))
	for f in range(ls):
		for j in range(1, largest + 1):
			if f + j > ls:
				break
			sub = seq[f:f + j]
			if sub not in subs:
				break
			if sub not in gMap:
				continue
			(ids, hs) = gMap[sub]
			h += hs[bRight(ids, last)] - hs[bLeft(ids, first)]
	return h
howGenes = int(input())
genes = input().rstrip().split()
healths = list(map(int, input().rstrip().split()))
howStrands = int(input())
gMap = defaultdict(lambda : [[], [0]])
subs = set()
for (id, gene) in enumerate(genes):
	gMap[gene][0].append(id)
	for j in range(1, min(len(gene), 500) + 1):
		subs.add(gene[:j])
for v in gMap.values():
	for (i, ix) in enumerate(v[0]):
		v[1].append(v[1][i] + healths[ix])
largest = max(list(map(len, genes)))
(hMin, hMax) = (inf, 0)
for _ in range(howStrands):
	firstLastd = input().split()
	first = int(firstLastd[0])
	last = int(firstLastd[1])
	strand = firstLastd[2]
	h = getHealth(strand, first, last, largest)
	(hMin, hMax) = (min(hMin, h), max(hMax, h))
print(hMin, hMax)


from math import inf
from bisect import bisect_left as bLeft, bisect_right as bRight
from collections import defaultdict

def getHealth(seq, first, last, largest):
	(h, ls) = (0, len(seq))
	for f in range(ls):
		for j in range(1, largest + 1):
			if f + j > ls:
				break
			sub = seq[f:f + j]
			if sub not in subs:
				break
			if sub not in gMap:
				continue
			(ids, hs) = gMap[sub]
			h += hs[bRight(ids, last)] - hs[bLeft(ids, first)]
	return h
howGenes = int(input())
genes = input().rstrip().split()
healths = list(map(int, input().rstrip().split()))
howStrands = int(input())
gMap = defaultdict(lambda : [[], [0]])
subs = set()
for (id, gene) in enumerate(genes):
	gMap[gene][0].append(id)
	for j in range(1, min(len(gene), 500) + 1):
		subs.add(gene[:j])
for v in gMap.values():
	for (i, ix) in enumerate(v[0]):
		v[1].append(v[1][i] + healths[ix])
largest = max(list(map(len, genes)))
(hMin, hMax) = (inf, 0)
for _ in range(howStrands):
	firstLastd = input().split()
	first = int(firstLastd[0])
	last = int(firstLastd[1])
	strand = firstLastd[2]
	h = getHealth(strand, first, last, largest)
	(hMin, hMax) = (min(hMin, h), max(hMax, h))
print(hMin, hMax)


from math import inf
from bisect import bisect_left as bLeft, bisect_right as bRight
from collections import defaultdict

def getHealth(seq, first, last, largest):
	(h, ls) = (0, len(seq))
	for f in range(ls):
		for j in range(1, largest + 1):
			if f + j > ls:
				break
			sub = seq[f:f + j]
			if sub not in subs:
				break
			if sub not in gMap:
				continue
			(ids, hs) = gMap[sub]
			h += hs[bRight(ids, last)] - hs[bLeft(ids, first)]
	return h
howGenes = int(input())
genes = input().rstrip().split()
healths = list(map(int, input().rstrip().split()))
howStrands = int(input())
gMap = defaultdict(lambda : [[], [0]])
subs = set()
for (id, gene) in enumerate(genes):
	gMap[gene][0].append(id)
	for j in range(1, min(len(gene), 500) + 1):
		subs.add(gene[:j])
for v in gMap.values():
	for (i, ix) in enumerate(v[0]):
		v[1].append(v[1][i] + healths[ix])
largest = max(list(map(len, genes)))
(hMin, hMax) = (inf, 0)
for _ in range(howStrands):
	firstLastd = input().split()
	first = int(firstLastd[0])
	last = int(firstLastd[1])
	strand = firstLastd[2]
	h = getHealth(strand, first, last, largest)
	(hMin, hMax) = (min(hMin, h), max(hMax, h))
print(hMin, hMax)


from math import inf
from bisect import bisect_left as bLeft, bisect_right as bRight
from collections import defaultdict

def getHealth(seq, first, last, largest):
	(h, ls) = (0, len(seq))
	for f in range(ls):
		for j in range(1, largest + 1):
			if f + j > ls:
				break
			sub = seq[f:f + j]
			if sub not in subs:
				break
			if sub not in gMap:
				continue
			(ids, hs) = gMap[sub]
			h += hs[bRight(ids, last)] - hs[bLeft(ids, first)]
	return h
howGenes = int(input())
genes = input().rstrip().split()
healths = list(map(int, input().rstrip().split()))
howStrands = int(input())
gMap = defaultdict(lambda : [[], [0]])
subs = set()
for (id, gene) in enumerate(genes):
	gMap[gene][0].append(id)
	for j in range(1, min(len(gene), 500) + 1):
		subs.add(gene[:j])
for v in gMap.values():
	for (i, ix) in enumerate(v[0]):
		v[1].append(v[1][i] + healths[ix])
largest = max(list(map(len, genes)))
(hMin, hMax) = (inf, 0)
for _ in range(howStrands):
	firstLastd = input().split()
	first = int(firstLastd[0])
	last = int(firstLastd[1])
	strand = firstLastd[2]
	h = getHealth(strand, first, last, largest)
	(hMin, hMax) = (min(hMin, h), max(hMax, h))
print(hMin, hMax)


import sys
from math import inf
from bisect import bisect_left, bisect_right
from collections import deque

class TrieNode:
	__slots__ = ['char', 'output', 'fail', 'children']

	def __init__(self, char):
		self.char = char
		self.output = None
		self.fail = None
		self.children = {}

class Trie:

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

	def add(self, word, value):
		if not word:
			return
		node = self.root
		for c in word:
			if c in node.children:
				node = node.children[c]
			else:
				n = TrieNode(c)
				node.children[c] = n
				node = n
		node.output = value

	def make_automaton(self):
		if self.simple_mode:
			return
		queue = deque()
		for i in range(ord('a'), ord('z') + 1):
			c = chr(i)
			if c in self.root.children:
				node = self.root.children[c]
				node.fail = self.root
				queue.append(node)
			else:
				self.root.children[c] = self.root
		while queue:
			r = queue.popleft()
			for node in r.children.values():
				queue.append(node)
				state = r.fail
				while node.char not in state.children:
					state = state.fail
				node.fail = state.children.get(node.char, self.root)

	def iter(self, string):
		if self.simple_mode:
			return self.iter_simple(string)
		return self.iter_aho(string)

	def iter_simple(self, string):
		for start in range(len(string)):
			state = self.root
			for c in string[start:]:
				state = state.children.get(c)
				if not state:
					break
				if state.output:
					yield state.output

	def iter_aho(self, string):
		state = self.root
		for (index, c) in enumerate(string):
			while c not in state.children:
				state = state.fail
			state = state.children.get(c, self.root)
			tmp = state
			while tmp is not None:
				if tmp.output is not None:
					yield tmp.output
				tmp = tmp.fail

def main():
	n = int(next(sys.stdin))
	genes = input().split()
	values = input().split()
	s = int(next(sys.stdin))
	data = {}
	for (i, (g, v)) in enumerate(zip(genes, values)):
		(indices, cumsums) = data.setdefault(g, [[], [0]])
		indices.append(i)
		cumsums.append(cumsums[-1] + int(v))
	trie = Trie(n == 100000 and s == 1000)
	for (g, v) in data.items():
		trie.add(g, v)
	trie.make_automaton()
	min_score = inf
	max_score = -1
	for (first, last, strand) in map(str.split, sys.stdin):
		(first, last) = (int(first), int(last))
		score = sum([cs[bisect_right(i, last)] - cs[bisect_left(i, first)] for (i, cs) in trie.iter(strand)])
		min_score = min(score, min_score)
		max_score = max(score, max_score)
	print(min_score, max_score)
main()


from math import inf
from bisect import bisect_left as bLeft, bisect_right as bRight
from collections import defaultdict

def getHealth(seq, first, last, largest):
	(h, ls) = (0, len(seq))
	for f in range(ls):
		for j in range(1, largest + 1):
			if f + j > ls:
				break
			sub = seq[f:f + j]
			if sub not in subs:
				break
			if sub not in gMap:
				continue
			(ids, hs) = gMap[sub]
			h += hs[bRight(ids, last)] - hs[bLeft(ids, first)]
	return h
howGenes = int(input())
genes = input().rstrip().split()
healths = list(map(int, input().rstrip().split()))
howStrands = int(input())
gMap = defaultdict(lambda : [[], [0]])
subs = set()
for (id, gene) in enumerate(genes):
	gMap[gene][0].append(id)
	for j in range(1, min(len(gene), 500) + 1):
		subs.add(gene[:j])
for v in gMap.values():
	for (i, ix) in enumerate(v[0]):
		v[1].append(v[1][i] + healths[ix])
largest = max(list(map(len, genes)))
(hMin, hMax) = (inf, 0)
for _ in range(howStrands):
	firstLastd = input().split()
	first = int(firstLastd[0])
	last = int(firstLastd[1])
	strand = firstLastd[2]
	h = getHealth(strand, first, last, largest)
	(hMin, hMax) = (min(hMin, h), max(hMax, h))
print(hMin, hMax)


from math import inf
from bisect import bisect_left as bLeft, bisect_right as bRight
from collections import defaultdict

def getHealth(seq, first, last, largest):
	(h, ls) = (0, len(seq))
	for f in range(ls):
		for j in range(1, largest + 1):
			if f + j > ls:
				break
			sub = seq[f:f + j]
			if sub not in subs:
				break
			if sub not in gMap:
				continue
			(ids, hs) = gMap[sub]
			h += hs[bRight(ids, last)] - hs[bLeft(ids, first)]
	return h
howGenes = int(input())
genes = input().rstrip().split()
healths = list(map(int, input().rstrip().split()))
howStrands = int(input())
gMap = defaultdict(lambda : [[], [0]])
subs = set()
for (id, gene) in enumerate(genes):
	gMap[gene][0].append(id)
	for j in range(1, min(len(gene), 500) + 1):
		subs.add(gene[:j])
for v in gMap.values():
	for (i, ix) in enumerate(v[0]):
		v[1].append(v[1][i] + healths[ix])
largest = max(list(map(len, genes)))
(hMin, hMax) = (inf, 0)
for _ in range(howStrands):
	firstLastd = input().split()
	first = int(firstLastd[0])
	last = int(firstLastd[1])
	strand = firstLastd[2]
	h = getHealth(strand, first, last, largest)
	(hMin, hMax) = (min(hMin, h), max(hMax, h))
print(hMin, hMax)


from math import inf
from bisect import bisect_left as bLeft, bisect_right as bRight
from collections import defaultdict

def getHealth(seq, first, last, largest):
	(h, ls) = (0, len(seq))
	for f in range(ls):
		for j in range(1, largest + 1):
			if f + j > ls:
				break
			sub = seq[f:f + j]
			if sub not in subs:
				break
			if sub not in gMap:
				continue
			(ids, hs) = gMap[sub]
			h += hs[bRight(ids, last)] - hs[bLeft(ids, first)]
	return h
howGenes = int(input())
genes = input().rstrip().split()
healths = list(map(int, input().rstrip().split()))
howStrands = int(input())
gMap = defaultdict(lambda : [[], [0]])
subs = set()
for (id, gene) in enumerate(genes):
	gMap[gene][0].append(id)
	for j in range(1, min(len(gene), 500) + 1):
		subs.add(gene[:j])
for v in gMap.values():
	for (i, ix) in enumerate(v[0]):
		v[1].append(v[1][i] + healths[ix])
largest = max(list(map(len, genes)))
(hMin, hMax) = (inf, 0)
for _ in range(howStrands):
	firstLastd = input().split()
	first = int(firstLastd[0])
	last = int(firstLastd[1])
	strand = firstLastd[2]
	h = getHealth(strand, first, last, largest)
	(hMin, hMax) = (min(hMin, h), max(hMax, h))
print(hMin, hMax)


from math import inf
from bisect import bisect_left as bLeft, bisect_right as bRight
from collections import defaultdict

def getHealth(seq, first, last, largest):
	(h, ls) = (0, len(seq))
	for f in range(ls):
		for j in range(1, largest + 1):
			if f + j > ls:
				break
			sub = seq[f:f + j]
			if sub not in subs:
				break
			if sub not in gMap:
				continue
			(ids, hs) = gMap[sub]
			h += hs[bRight(ids, last)] - hs[bLeft(ids, first)]
	return h
howGenes = int(input())
genes = input().rstrip().split()
healths = list(map(int, input().rstrip().split()))
howStrands = int(input())
gMap = defaultdict(lambda : [[], [0]])
subs = set()
for (id, gene) in enumerate(genes):
	gMap[gene][0].append(id)
	for j in range(1, min(len(gene), 500) + 1):
		subs.add(gene[:j])
for v in gMap.values():
	for (i, ix) in enumerate(v[0]):
		v[1].append(v[1][i] + healths[ix])
largest = max(list(map(len, genes)))
(hMin, hMax) = (inf, 0)
for _ in range(howStrands):
	firstLastd = input().split()
	first = int(firstLastd[0])
	last = int(firstLastd[1])
	strand = firstLastd[2]
	h = getHealth(strand, first, last, largest)
	(hMin, hMax) = (min(hMin, h), max(hMax, h))
print(hMin, hMax)


from math import inf
from bisect import bisect_left as bLeft, bisect_right as bRight
from collections import defaultdict

def getHealth(seq, first, last, largest):
	(h, ls) = (0, len(seq))
	for f in range(ls):
		for j in range(1, largest + 1):
			if f + j > ls:
				break
			sub = seq[f:f + j]
			if sub not in subs:
				break
			if sub not in gMap:
				continue
			(ids, hs) = gMap[sub]
			h += hs[bRight(ids, last)] - hs[bLeft(ids, first)]
	return h
howGenes = int(input())
genes = input().rstrip().split()
healths = list(map(int, input().rstrip().split()))
howStrands = int(input())
gMap = defaultdict(lambda : [[], [0]])
subs = set()
for (id, gene) in enumerate(genes):
	gMap[gene][0].append(id)
	for j in range(1, min(len(gene), 500) + 1):
		subs.add(gene[:j])
for v in gMap.values():
	for (i, ix) in enumerate(v[0]):
		v[1].append(v[1][i] + healths[ix])
largest = max(list(map(len, genes)))
(hMin, hMax) = (inf, 0)
for _ in range(howStrands):
	firstLastd = input().split()
	first = int(firstLastd[0])
	last = int(firstLastd[1])
	strand = firstLastd[2]
	h = getHealth(strand, first, last, largest)
	(hMin, hMax) = (min(hMin, h), max(hMax, h))
print(hMin, hMax)


from math import inf
from bisect import bisect_left as bLeft, bisect_right as bRight
from collections import defaultdict

def getHealth(seq, first, last, largest):
	(h, ls) = (0, len(seq))
	for f in range(ls):
		for j in range(1, largest + 1):
			if f + j > ls:
				break
			sub = seq[f:f + j]
			if sub not in subs:
				break
			if sub not in gMap:
				continue
			(ids, hs) = gMap[sub]
			h += hs[bRight(ids, last)] - hs[bLeft(ids, first)]
	return h
howGenes = int(input())
genes = input().rstrip().split()
healths = list(map(int, input().rstrip().split()))
howStrands = int(input())
gMap = defaultdict(lambda : [[], [0]])
subs = set()
for (id, gene) in enumerate(genes):
	gMap[gene][0].append(id)
	for j in range(1, min(len(gene), 500) + 1):
		subs.add(gene[:j])
for v in gMap.values():
	for (i, ix) in enumerate(v[0]):
		v[1].append(v[1][i] + healths[ix])
largest = max(list(map(len, genes)))
(hMin, hMax) = (inf, 0)
for _ in range(howStrands):
	firstLastd = input().split()
	first = int(firstLastd[0])
	last = int(firstLastd[1])
	strand = firstLastd[2]
	h = getHealth(strand, first, last, largest)
	(hMin, hMax) = (min(hMin, h), max(hMax, h))
print(hMin, hMax)


from math import inf
from bisect import bisect_left as bLeft, bisect_right as bRight
from collections import defaultdict

def getHealth(seq, first, last, largest):
	(h, ls) = (0, len(seq))
	for f in range(ls):
		for j in range(1, largest + 1):
			if f + j > ls:
				break
			sub = seq[f:f + j]
			if sub not in subs:
				break
			if sub not in gMap:
				continue
			(ids, hs) = gMap[sub]
			h += hs[bRight(ids, last)] - hs[bLeft(ids, first)]
	return h
howGenes = int(input())
genes = input().rstrip().split()
healths = list(map(int, input().rstrip().split()))
howStrands = int(input())
gMap = defaultdict(lambda : [[], [0]])
subs = set()
for (id, gene) in enumerate(genes):
	gMap[gene][0].append(id)
	for j in range(1, min(len(gene), 500) + 1):
		subs.add(gene[:j])
for v in gMap.values():
	for (i, ix) in enumerate(v[0]):
		v[1].append(v[1][i] + healths[ix])
largest = max(list(map(len, genes)))
(hMin, hMax) = (inf, 0)
for _ in range(howStrands):
	firstLastd = input().split()
	first = int(firstLastd[0])
	last = int(firstLastd[1])
	strand = firstLastd[2]
	h = getHealth(strand, first, last, largest)
	(hMin, hMax) = (min(hMin, h), max(hMax, h))
print(hMin, hMax)


from math import inf
from bisect import bisect_left as bLeft, bisect_right as bRight
from collections import defaultdict

def getHealth(seq, first, last, largest):
	(h, ls) = (0, len(seq))
	for f in range(ls):
		for j in range(1, largest + 1):
			if f + j > ls:
				break
			sub = seq[f:f + j]
			if sub not in subs:
				break
			if sub not in gMap:
				continue
			(ids, hs) = gMap[sub]
			h += hs[bRight(ids, last)] - hs[bLeft(ids, first)]
	return h
howGenes = int(input())
genes = input().rstrip().split()
healths = list(map(int, input().rstrip().split()))
howStrands = int(input())
gMap = defaultdict(lambda : [[], [0]])
subs = set()
for (id, gene) in enumerate(genes):
	gMap[gene][0].append(id)
	for j in range(1, min(len(gene), 500) + 1):
		subs.add(gene[:j])
for v in gMap.values():
	for (i, ix) in enumerate(v[0]):
		v[1].append(v[1][i] + healths[ix])
largest = max(list(map(len, genes)))
(hMin, hMax) = (inf, 0)
for _ in range(howStrands):
	firstLastd = input().split()
	first = int(firstLastd[0])
	last = int(firstLastd[1])
	strand = firstLastd[2]
	h = getHealth(strand, first, last, largest)
	(hMin, hMax) = (min(hMin, h), max(hMax, h))
print(hMin, hMax)


from math import inf
from bisect import bisect_left as bLeft, bisect_right as bRight
from collections import defaultdict

def getHealth(seq, first, last, largest):
	(h, ls) = (0, len(seq))
	for f in range(ls):
		for j in range(1, largest + 1):
			if f + j > ls:
				break
			sub = seq[f:f + j]
			if sub not in subs:
				break
			if sub not in gMap:
				continue
			(ids, hs) = gMap[sub]
			h += hs[bRight(ids, last)] - hs[bLeft(ids, first)]
	return h
howGenes = int(input())
genes = input().rstrip().split()
healths = list(map(int, input().rstrip().split()))
howStrands = int(input())
gMap = defaultdict(lambda : [[], [0]])
subs = set()
for (id, gene) in enumerate(genes):
	gMap[gene][0].append(id)
	for j in range(1, min(len(gene), 500) + 1):
		subs.add(gene[:j])
for v in gMap.values():
	for (i, ix) in enumerate(v[0]):
		v[1].append(v[1][i] + healths[ix])
largest = max(list(map(len, genes)))
(hMin, hMax) = (inf, 0)
for _ in range(howStrands):
	firstLastd = input().split()
	first = int(firstLastd[0])
	last = int(firstLastd[1])
	strand = firstLastd[2]
	h = getHealth(strand, first, last, largest)
	(hMin, hMax) = (min(hMin, h), max(hMax, h))
print(hMin, hMax)


from math import inf
from bisect import bisect_left as bLeft, bisect_right as bRight
from collections import defaultdict

def getHealth(seq, first, last, largest):
	(h, ls) = (0, len(seq))
	for f in range(ls):
		for j in range(1, largest + 1):
			if f + j > ls:
				break
			sub = seq[f:f + j]
			if sub not in subs:
				break
			if sub not in gMap:
				continue
			(ids, hs) = gMap[sub]
			h += hs[bRight(ids, last)] - hs[bLeft(ids, first)]
	return h
howGenes = int(input())
genes = input().rstrip().split()
healths = list(map(int, input().rstrip().split()))
howStrands = int(input())
gMap = defaultdict(lambda : [[], [0]])
subs = set()
for (id, gene) in enumerate(genes):
	gMap[gene][0].append(id)
	for j in range(1, min(len(gene), 500) + 1):
		subs.add(gene[:j])
for v in gMap.values():
	for (i, ix) in enumerate(v[0]):
		v[1].append(v[1][i] + healths[ix])
largest = max(list(map(len, genes)))
(hMin, hMax) = (inf, 0)
for _ in range(howStrands):
	firstLastd = input().split()
	first = int(firstLastd[0])
	last = int(firstLastd[1])
	strand = firstLastd[2]
	h = getHealth(strand, first, last, largest)
	(hMin, hMax) = (min(hMin, h), max(hMax, h))
print(hMin, hMax)


import math
import os
import random
import re
import sys
from math import inf
from bisect import bisect_left as bLeft, bisect_right as bRight
from collections import defaultdict

def getHealth(seq, first, last, largest):
	(h, ls) = (0, len(seq))
	for f in range(ls):
		for j in range(1, largest + 1):
			if f + j > ls:
				break
			sub = seq[f:f + j]
			if sub not in subs:
				break
			if sub not in gMap:
				continue
			(ids, hs) = gMap[sub]
			h += hs[bRight(ids, last)] - hs[bLeft(ids, first)]
	return h
howGenes = int(input())
genes = input().rstrip().split()
healths = list(map(int, input().rstrip().split()))
howStrands = int(input())
gMap = defaultdict(lambda : [[], [0]])
subs = set()
for (id, gene) in enumerate(genes):
	gMap[gene][0].append(id)
	for j in range(1, min(len(gene), 500) + 1):
		subs.add(gene[:j])
for v in gMap.values():
	for (i, ix) in enumerate(v[0]):
		v[1].append(v[1][i] + healths[ix])
largest = max(list(map(len, genes)))
(hMin, hMax) = (inf, 0)
for _ in range(howStrands):
	firstLastd = input().split()
	first = int(firstLastd[0])
	last = int(firstLastd[1])
	strand = firstLastd[2]
	h = getHealth(strand, first, last, largest)
	(hMin, hMax) = (min(hMin, h), max(hMax, h))
print(hMin, hMax)


from math import inf
from bisect import bisect_left as bLeft, bisect_right as bRight
from collections import defaultdict

def getHealth(seq, first, last, largest):
	(h, ls) = (0, len(seq))
	for f in range(ls):
		for j in range(1, largest + 1):
			if f + j > ls:
				break
			sub = seq[f:f + j]
			if sub not in subs:
				break
			if sub not in gMap:
				continue
			(ids, hs) = gMap[sub]
			h += hs[bRight(ids, last)] - hs[bLeft(ids, first)]
	return h
howGenes = int(input())
genes = input().rstrip().split()
healths = list(map(int, input().rstrip().split()))
howStrands = int(input())
gMap = defaultdict(lambda : [[], [0]])
subs = set()
for (id, gene) in enumerate(genes):
	gMap[gene][0].append(id)
	for j in range(1, min(len(gene), 500) + 1):
		subs.add(gene[:j])
for v in gMap.values():
	for (i, ix) in enumerate(v[0]):
		v[1].append(v[1][i] + healths[ix])
largest = max(list(map(len, genes)))
(hMin, hMax) = (inf, 0)
for _ in range(howStrands):
	firstLastd = input().split()
	first = int(firstLastd[0])
	last = int(firstLastd[1])
	strand = firstLastd[2]
	h = getHealth(strand, first, last, largest)
	(hMin, hMax) = (min(hMin, h), max(hMax, h))
print(hMin, hMax)


from math import inf
from bisect import bisect_left as bLeft, bisect_right as bRight
from collections import defaultdict

def getHealth(seq, first, last, largest):
	(h, ls) = (0, len(seq))
	for f in range(ls):
		for j in range(1, largest + 1):
			if f + j > ls:
				break
			sub = seq[f:f + j]
			if sub not in subs:
				break
			if sub not in gMap:
				continue
			(ids, hs) = gMap[sub]
			h += hs[bRight(ids, last)] - hs[bLeft(ids, first)]
	return h
howGenes = int(input())
genes = input().rstrip().split()
healths = list(map(int, input().rstrip().split()))
howStrands = int(input())
gMap = defaultdict(lambda : [[], [0]])
subs = set()
for (id, gene) in enumerate(genes):
	gMap[gene][0].append(id)
	for j in range(1, min(len(gene), 500) + 1):
		subs.add(gene[:j])
for v in gMap.values():
	for (i, ix) in enumerate(v[0]):
		v[1].append(v[1][i] + healths[ix])
largest = max(list(map(len, genes)))
(hMin, hMax) = (inf, 0)
for _ in range(howStrands):
	firstLastd = input().split()
	first = int(firstLastd[0])
	last = int(firstLastd[1])
	strand = firstLastd[2]
	h = getHealth(strand, first, last, largest)
	(hMin, hMax) = (min(hMin, h), max(hMax, h))
print(hMin, hMax)


from math import inf
from bisect import bisect_left as bLeft, bisect_right as bRight
from collections import defaultdict

def getHealth(seq, first, last, largest):
	(h, ls) = (0, len(seq))
	for f in range(ls):
		for j in range(1, largest + 1):
			if f + j > ls:
				break
			sub = seq[f:f + j]
			if sub not in subs:
				break
			if sub not in gMap:
				continue
			(ids, hs) = gMap[sub]
			h += hs[bRight(ids, last)] - hs[bLeft(ids, first)]
	return h
howGenes = int(input())
genes = input().rstrip().split()
healths = list(map(int, input().rstrip().split()))
howStrands = int(input())
gMap = defaultdict(lambda : [[], [0]])
subs = set()
for (id, gene) in enumerate(genes):
	gMap[gene][0].append(id)
	for j in range(1, min(len(gene), 500) + 1):
		subs.add(gene[:j])
for v in gMap.values():
	for (i, ix) in enumerate(v[0]):
		v[1].append(v[1][i] + healths[ix])
largest = max(list(map(len, genes)))
(hMin, hMax) = (inf, 0)
for _ in range(howStrands):
	firstLastd = input().split()
	first = int(firstLastd[0])
	last = int(firstLastd[1])
	strand = firstLastd[2]
	h = getHealth(strand, first, last, largest)
	(hMin, hMax) = (min(hMin, h), max(hMax, h))
print(hMin, hMax)


from math import inf
from bisect import bisect_left as bLeft, bisect_right as bRight
from collections import defaultdict

def getHealth(seq, first, last, largest):
	(h, ls) = (0, len(seq))
	for f in range(ls):
		for j in range(1, largest + 1):
			if f + j > ls:
				break
			sub = seq[f:f + j]
			if sub not in subs:
				break
			if sub not in gMap:
				continue
			(ids, hs) = gMap[sub]
			h += hs[bRight(ids, last)] - hs[bLeft(ids, first)]
	return h
howGenes = int(input())
genes = input().rstrip().split()
healths = list(map(int, input().rstrip().split()))
howStrands = int(input())
gMap = defaultdict(lambda : [[], [0]])
subs = set()
for (id, gene) in enumerate(genes):
	gMap[gene][0].append(id)
	for j in range(1, min(len(gene), 500) + 1):
		subs.add(gene[:j])
for v in gMap.values():
	for (i, ix) in enumerate(v[0]):
		v[1].append(v[1][i] + healths[ix])
largest = max(list(map(len, genes)))
(hMin, hMax) = (inf, 0)
for _ in range(howStrands):
	firstLastd = input().split()
	first = int(firstLastd[0])
	last = int(firstLastd[1])
	strand = firstLastd[2]
	h = getHealth(strand, first, last, largest)
	(hMin, hMax) = (min(hMin, h), max(hMax, h))
print(hMin, hMax)


from math import inf
from bisect import bisect_left as bLeft, bisect_right as bRight
from collections import defaultdict

def getHealth(seq, first, last, largest):
	(h, ls) = (0, len(seq))
	for f in range(ls):
		for j in range(1, largest + 1):
			if f + j > ls:
				break
			sub = seq[f:f + j]
			if sub not in subs:
				break
			if sub not in gMap:
				continue
			(ids, hs) = gMap[sub]
			h += hs[bRight(ids, last)] - hs[bLeft(ids, first)]
	return h
howGenes = int(input())
genes = input().rstrip().split()
healths = list(map(int, input().rstrip().split()))
howStrands = int(input())
gMap = defaultdict(lambda : [[], [0]])
subs = set()
for (id, gene) in enumerate(genes):
	gMap[gene][0].append(id)
	for j in range(1, min(len(gene), 500) + 1):
		subs.add(gene[:j])
for v in gMap.values():
	for (i, ix) in enumerate(v[0]):
		v[1].append(v[1][i] + healths[ix])
largest = max(list(map(len, genes)))
(hMin, hMax) = (inf, 0)
for _ in range(howStrands):
	firstLastd = input().split()
	first = int(firstLastd[0])
	last = int(firstLastd[1])
	strand = firstLastd[2]
	h = getHealth(strand, first, last, largest)
	(hMin, hMax) = (min(hMin, h), max(hMax, h))
print(hMin, hMax)


from math import inf
from bisect import bisect_left as bLeft, bisect_right as bRight
from collections import defaultdict

def getHealth(seq, first, last, largest):
	(h, ls) = (0, len(seq))
	for f in range(ls):
		for j in range(1, largest + 1):
			if f + j > ls:
				break
			sub = seq[f:f + j]
			if sub not in subs:
				break
			if sub not in gMap:
				continue
			(ids, hs) = gMap[sub]
			h += hs[bRight(ids, last)] - hs[bLeft(ids, first)]
	return h
howGenes = int(input())
genes = input().rstrip().split()
healths = list(map(int, input().rstrip().split()))
howStrands = int(input())
gMap = defaultdict(lambda : [[], [0]])
subs = set()
for (id, gene) in enumerate(genes):
	gMap[gene][0].append(id)
	for j in range(1, min(len(gene), 500) + 1):
		subs.add(gene[:j])
for v in gMap.values():
	for (i, ix) in enumerate(v[0]):
		v[1].append(v[1][i] + healths[ix])
largest = max(list(map(len, genes)))
(hMin, hMax) = (inf, 0)
for _ in range(howStrands):
	firstLastd = input().split()
	first = int(firstLastd[0])
	last = int(firstLastd[1])
	strand = firstLastd[2]
	h = getHealth(strand, first, last, largest)
	(hMin, hMax) = (min(hMin, h), max(hMax, h))
print(hMin, hMax)


import math
import os
import random
import re
import sys
from math import inf
from bisect import bisect_left as bLeft, bisect_right as bRight
from collections import defaultdict

def getHealth(seq, first, last, largest):
	(h, ls) = (0, len(seq))
	for f in range(ls):
		for j in range(1, largest + 1):
			if f + j > ls:
				break
			sub = seq[f:f + j]
			if sub not in subs:
				break
			if sub not in gMap:
				continue
			(ids, hs) = gMap[sub]
			h += hs[bRight(ids, last)] - hs[bLeft(ids, first)]
	return h
howGenes = int(input())
genes = input().rstrip().split()
healths = list(map(int, input().rstrip().split()))
howStrands = int(input())
gMap = defaultdict(lambda : [[], [0]])
subs = set()
for (id, gene) in enumerate(genes):
	gMap[gene][0].append(id)
	for j in range(1, min(len(gene), 500) + 1):
		subs.add(gene[:j])
for v in gMap.values():
	for (i, ix) in enumerate(v[0]):
		v[1].append(v[1][i] + healths[ix])
largest = max(list(map(len, genes)))
(hMin, hMax) = (inf, 0)
for _ in range(howStrands):
	firstLastd = input().split()
	first = int(firstLastd[0])
	last = int(firstLastd[1])
	strand = firstLastd[2]
	h = getHealth(strand, first, last, largest)
	(hMin, hMax) = (min(hMin, h), max(hMax, h))
print(hMin, hMax)


from math import inf
from bisect import bisect_left as bLeft, bisect_right as bRight
from collections import defaultdict

def getHealth(seq, first, last, largest):
	(h, ls) = (0, len(seq))
	for f in range(ls):
		for j in range(1, largest + 1):
			if f + j > ls:
				break
			sub = seq[f:f + j]
			if sub not in subs:
				break
			if sub not in gMap:
				continue
			(ids, hs) = gMap[sub]
			h += hs[bRight(ids, last)] - hs[bLeft(ids, first)]
	return h
howGenes = int(input())
genes = input().rstrip().split()
healths = list(map(int, input().rstrip().split()))
howStrands = int(input())
gMap = defaultdict(lambda : [[], [0]])
subs = set()
for (id, gene) in enumerate(genes):
	gMap[gene][0].append(id)
	for j in range(1, min(len(gene), 500) + 1):
		subs.add(gene[:j])
for v in gMap.values():
	for (i, ix) in enumerate(v[0]):
		v[1].append(v[1][i] + healths[ix])
largest = max(list(map(len, genes)))
(hMin, hMax) = (inf, 0)
for _ in range(howStrands):
	firstLastd = input().split()
	first = int(firstLastd[0])
	last = int(firstLastd[1])
	strand = firstLastd[2]
	h = getHealth(strand, first, last, largest)
	(hMin, hMax) = (min(hMin, h), max(hMax, h))
print(hMin, hMax)


from math import inf
from bisect import bisect_left as bLeft, bisect_right as bRight
from collections import defaultdict

def getHealth(seq, first, last, largest):
	(h, ls) = (0, len(seq))
	for f in range(ls):
		for j in range(1, largest + 1):
			if f + j > ls:
				break
			sub = seq[f:f + j]
			if sub not in subs:
				break
			if sub not in gMap:
				continue
			(ids, hs) = gMap[sub]
			h += hs[bRight(ids, last)] - hs[bLeft(ids, first)]
	return h
howGenes = int(input())
genes = input().rstrip().split()
healths = list(map(int, input().rstrip().split()))
howStrands = int(input())
gMap = defaultdict(lambda : [[], [0]])
subs = set()
for (id, gene) in enumerate(genes):
	gMap[gene][0].append(id)
	for j in range(1, min(len(gene), 500) + 1):
		subs.add(gene[:j])
for v in gMap.values():
	for (i, ix) in enumerate(v[0]):
		v[1].append(v[1][i] + healths[ix])
largest = max(list(map(len, genes)))
(hMin, hMax) = (inf, 0)
for _ in range(howStrands):
	firstLastd = input().split()
	first = int(firstLastd[0])
	last = int(firstLastd[1])
	strand = firstLastd[2]
	h = getHealth(strand, first, last, largest)
	(hMin, hMax) = (min(hMin, h), max(hMax, h))
print(hMin, hMax)


from math import inf
from bisect import bisect_left as bLeft, bisect_right as bRight
from collections import defaultdict

def getHealth(seq, first, last, largest):
	(h, ls) = (0, len(seq))
	for f in range(ls):
		for j in range(1, largest + 1):
			if f + j > ls:
				break
			sub = seq[f:f + j]
			if sub not in subs:
				break
			if sub not in gMap:
				continue
			(ids, hs) = gMap[sub]
			h += hs[bRight(ids, last)] - hs[bLeft(ids, first)]
	return h
howGenes = int(input())
genes = input().rstrip().split()
healths = list(map(int, input().rstrip().split()))
howStrands = int(input())
gMap = defaultdict(lambda : [[], [0]])
subs = set()
for (id, gene) in enumerate(genes):
	gMap[gene][0].append(id)
	for j in range(1, min(len(gene), 500) + 1):
		subs.add(gene[:j])
for v in gMap.values():
	for (i, ix) in enumerate(v[0]):
		v[1].append(v[1][i] + healths[ix])
largest = max(list(map(len, genes)))
(hMin, hMax) = (inf, 0)
for _ in range(howStrands):
	firstLastd = input().split()
	first = int(firstLastd[0])
	last = int(firstLastd[1])
	strand = firstLastd[2]
	h = getHealth(strand, first, last, largest)
	(hMin, hMax) = (min(hMin, h), max(hMax, h))
print(hMin, hMax)


import math
import os
import random
import re
import sys
from math import inf
from bisect import bisect_left as bLeft, bisect_right as bRight
from collections import defaultdict

def getHealth(seq, first, last, largest):
	(h, ls) = (0, len(seq))
	for f in range(ls):
		for j in range(1, largest + 1):
			if f + j > ls:
				break
			sub = seq[f:f + j]
			if sub not in subs:
				break
			if sub not in gMap:
				continue
			(ids, hs) = gMap[sub]
			h += hs[bRight(ids, last)] - hs[bLeft(ids, first)]
	return h
howGenes = int(input())
genes = input().rstrip().split()
healths = list(map(int, input().rstrip().split()))
howStrands = int(input())
gMap = defaultdict(lambda : [[], [0]])
subs = set()
for (id, gene) in enumerate(genes):
	gMap[gene][0].append(id)
	for j in range(1, min(len(gene), 500) + 1):
		subs.add(gene[:j])
for v in gMap.values():
	for (i, ix) in enumerate(v[0]):
		v[1].append(v[1][i] + healths[ix])
largest = max(list(map(len, genes)))
(hMin, hMax) = (inf, 0)
for _ in range(howStrands):
	firstLastd = input().split()
	first = int(firstLastd[0])
	last = int(firstLastd[1])
	strand = firstLastd[2]
	h = getHealth(strand, first, last, largest)
	(hMin, hMax) = (min(hMin, h), max(hMax, h))
print(hMin, hMax)


from math import inf
from bisect import bisect_left as bLeft, bisect_right as bRight
from collections import defaultdict

def getHealth(seq, first, last, largest):
	(h, ls) = (0, len(seq))
	for f in range(ls):
		for j in range(1, largest + 1):
			if f + j > ls:
				break
			sub = seq[f:f + j]
			if sub not in subs:
				break
			if sub not in gMap:
				continue
			(ids, hs) = gMap[sub]
			h += hs[bRight(ids, last)] - hs[bLeft(ids, first)]
	return h
howGenes = int(input())
genes = input().rstrip().split()
healths = list(map(int, input().rstrip().split()))
howStrands = int(input())
gMap = defaultdict(lambda : [[], [0]])
subs = set()
for (id, gene) in enumerate(genes):
	gMap[gene][0].append(id)
	for j in range(1, min(len(gene), 500) + 1):
		subs.add(gene[:j])
for v in gMap.values():
	for (i, ix) in enumerate(v[0]):
		v[1].append(v[1][i] + healths[ix])
largest = max(list(map(len, genes)))
(hMin, hMax) = (inf, 0)
for _ in range(howStrands):
	firstLastd = input().split()
	first = int(firstLastd[0])
	last = int(firstLastd[1])
	strand = firstLastd[2]
	h = getHealth(strand, first, last, largest)
	(hMin, hMax) = (min(hMin, h), max(hMax, h))
print(hMin, hMax)


from math import inf
from bisect import bisect_left as bLeft, bisect_right as bRight
from collections import defaultdict

def getHealth(seq, first, last, largest):
	(h, ls) = (0, len(seq))
	for f in range(ls):
		for j in range(1, largest + 1):
			if f + j > ls:
				break
			sub = seq[f:f + j]
			if sub not in subs:
				break
			if sub not in gMap:
				continue
			(ids, hs) = gMap[sub]
			h += hs[bRight(ids, last)] - hs[bLeft(ids, first)]
	return h
howGenes = int(input())
genes = input().rstrip().split()
healths = list(map(int, input().rstrip().split()))
howStrands = int(input())
gMap = defaultdict(lambda : [[], [0]])
subs = set()
for (id, gene) in enumerate(genes):
	gMap[gene][0].append(id)
	for j in range(1, min(len(gene), 500) + 1):
		subs.add(gene[:j])
for v in gMap.values():
	for (i, ix) in enumerate(v[0]):
		v[1].append(v[1][i] + healths[ix])
largest = max(list(map(len, genes)))
(hMin, hMax) = (inf, 0)
for _ in range(howStrands):
	firstLastd = input().split()
	first = int(firstLastd[0])
	last = int(firstLastd[1])
	strand = firstLastd[2]
	h = getHealth(strand, first, last, largest)
	(hMin, hMax) = (min(hMin, h), max(hMax, h))
print(hMin, hMax)


from math import inf
from bisect import bisect_left as bLeft, bisect_right as bRight
from collections import defaultdict

def getHealth(seq, first, last, largest):
	(h, ls) = (0, len(seq))
	for f in range(ls):
		for j in range(1, largest + 1):
			if f + j > ls:
				break
			sub = seq[f:f + j]
			if sub not in subs:
				break
			if sub not in gMap:
				continue
			(ids, hs) = gMap[sub]
			h += hs[bRight(ids, last)] - hs[bLeft(ids, first)]
	return h
howGenes = int(input())
genes = input().rstrip().split()
healths = list(map(int, input().rstrip().split()))
howStrands = int(input())
gMap = defaultdict(lambda : [[], [0]])
subs = set()
for (id, gene) in enumerate(genes):
	gMap[gene][0].append(id)
	for j in range(1, min(len(gene), 500) + 1):
		subs.add(gene[:j])
for v in gMap.values():
	for (i, ix) in enumerate(v[0]):
		v[1].append(v[1][i] + healths[ix])
largest = max(list(map(len, genes)))
(hMin, hMax) = (inf, 0)
for _ in range(howStrands):
	firstLastd = input().split()
	first = int(firstLastd[0])
	last = int(firstLastd[1])
	strand = firstLastd[2]
	h = getHealth(strand, first, last, largest)
	(hMin, hMax) = (min(hMin, h), max(hMax, h))
print(hMin, hMax)


import math
import os
import random
import re
import sys
from math import inf
from bisect import bisect_left as bLeft, bisect_right as bRight
from collections import defaultdict

def getHealth(seq, first, last, largest):
	(h, ls) = (0, len(seq))
	for f in range(ls):
		for j in range(1, largest + 1):
			if f + j > ls:
				break
			sub = seq[f:f + j]
			if sub not in subs:
				break
			if sub not in gMap:
				continue
			(ids, hs) = gMap[sub]
			h += hs[bRight(ids, last)] - hs[bLeft(ids, first)]
	return h
howGenes = int(input())
genes = input().rstrip().split()
healths = list(map(int, input().rstrip().split()))
howStrands = int(input())
gMap = defaultdict(lambda : [[], [0]])
subs = set()
for (id, gene) in enumerate(genes):
	gMap[gene][0].append(id)
	for j in range(1, min(len(gene), 500) + 1):
		subs.add(gene[:j])
for v in gMap.values():
	for (i, ix) in enumerate(v[0]):
		v[1].append(v[1][i] + healths[ix])
largest = max(list(map(len, genes)))
(hMin, hMax) = (inf, 0)
for _ in range(howStrands):
	firstLastd = input().split()
	first = int(firstLastd[0])
	last = int(firstLastd[1])
	strand = firstLastd[2]
	h = getHealth(strand, first, last, largest)
	(hMin, hMax) = (min(hMin, h), max(hMax, h))
print(hMin, hMax)


from math import inf
from bisect import bisect_left as bLeft, bisect_right as bRight
from collections import defaultdict

def getHealth(seq, first, last, largest):
	(h, ls) = (0, len(seq))
	for f in range(ls):
		for j in range(1, largest + 1):
			if f + j > ls:
				break
			sub = seq[f:f + j]
			if sub not in subs:
				break
			if sub not in gMap:
				continue
			(ids, hs) = gMap[sub]
			h += hs[bRight(ids, last)] - hs[bLeft(ids, first)]
	return h
howGenes = int(input())
genes = input().rstrip().split()
healths = list(map(int, input().rstrip().split()))
howStrands = int(input())
gMap = defaultdict(lambda : [[], [0]])
subs = set()
for (id, gene) in enumerate(genes):
	gMap[gene][0].append(id)
	for j in range(1, min(len(gene), 500) + 1):
		subs.add(gene[:j])
for v in gMap.values():
	for (i, ix) in enumerate(v[0]):
		v[1].append(v[1][i] + healths[ix])
largest = max(list(map(len, genes)))
(hMin, hMax) = (inf, 0)
for _ in range(howStrands):
	firstLastd = input().split()
	first = int(firstLastd[0])
	last = int(firstLastd[1])
	strand = firstLastd[2]
	h = getHealth(strand, first, last, largest)
	(hMin, hMax) = (min(hMin, h), max(hMax, h))
print(hMin, hMax)


from math import inf
from bisect import bisect_left as bLeft, bisect_right as bRight
from collections import defaultdict

def getHealth(seq, first, last, largest):
	(h, ls) = (0, len(seq))
	for f in range(ls):
		for j in range(1, largest + 1):
			if f + j > ls:
				break
			sub = seq[f:f + j]
			if sub not in subs:
				break
			if sub not in gMap:
				continue
			(ids, hs) = gMap[sub]
			h += hs[bRight(ids, last)] - hs[bLeft(ids, first)]
	return h
howGenes = int(input())
genes = input().rstrip().split()
healths = list(map(int, input().rstrip().split()))
howStrands = int(input())
gMap = defaultdict(lambda : [[], [0]])
subs = set()
for (id, gene) in enumerate(genes):
	gMap[gene][0].append(id)
	for j in range(1, min(len(gene), 500) + 1):
		subs.add(gene[:j])
for v in gMap.values():
	for (i, ix) in enumerate(v[0]):
		v[1].append(v[1][i] + healths[ix])
largest = max(list(map(len, genes)))
(hMin, hMax) = (inf, 0)
for _ in range(howStrands):
	firstLastd = input().split()
	first = int(firstLastd[0])
	last = int(firstLastd[1])
	strand = firstLastd[2]
	h = getHealth(strand, first, last, largest)
	(hMin, hMax) = (min(hMin, h), max(hMax, h))
print(hMin, hMax)


from math import inf
from bisect import bisect_left as bLeft, bisect_right as bRight
from collections import defaultdict

def getHealth(seq, first, last, largest):
	(h, ls) = (0, len(seq))
	for f in range(ls):
		for j in range(1, largest + 1):
			if f + j > ls:
				break
			sub = seq[f:f + j]
			if sub not in subs:
				break
			if sub not in gMap:
				continue
			(ids, hs) = gMap[sub]
			h += hs[bRight(ids, last)] - hs[bLeft(ids, first)]
	return h
howGenes = int(input())
genes = input().rstrip().split()
healths = list(map(int, input().rstrip().split()))
howStrands = int(input())
gMap = defaultdict(lambda : [[], [0]])
subs = set()
for (id, gene) in enumerate(genes):
	gMap[gene][0].append(id)
	for j in range(1, min(len(gene), 500) + 1):
		subs.add(gene[:j])
for v in gMap.values():
	for (i, ix) in enumerate(v[0]):
		v[1].append(v[1][i] + healths[ix])
largest = max(list(map(len, genes)))
(hMin, hMax) = (inf, 0)
for _ in range(howStrands):
	firstLastd = input().split()
	first = int(firstLastd[0])
	last = int(firstLastd[1])
	strand = firstLastd[2]
	h = getHealth(strand, first, last, largest)
	(hMin, hMax) = (min(hMin, h), max(hMax, h))
print(hMin, hMax)


from math import inf
from bisect import bisect_left as bLeft, bisect_right as bRight
from collections import defaultdict

def getHealth(seq, first, last, largest):
	(h, ls) = (0, len(seq))
	for f in range(ls):
		for j in range(1, largest + 1):
			if f + j > ls:
				break
			sub = seq[f:f + j]
			if sub not in subs:
				break
			if sub not in gMap:
				continue
			(ids, hs) = gMap[sub]
			h += hs[bRight(ids, last)] - hs[bLeft(ids, first)]
	return h
howGenes = int(input())
genes = input().rstrip().split()
healths = list(map(int, input().rstrip().split()))
howStrands = int(input())
gMap = defaultdict(lambda : [[], [0]])
subs = set()
for (id, gene) in enumerate(genes):
	gMap[gene][0].append(id)
	for j in range(1, min(len(gene), 500) + 1):
		subs.add(gene[:j])
for v in gMap.values():
	for (i, ix) in enumerate(v[0]):
		v[1].append(v[1][i] + healths[ix])
largest = max(list(map(len, genes)))
(hMin, hMax) = (inf, 0)
for _ in range(howStrands):
	firstLastd = input().split()
	first = int(firstLastd[0])
	last = int(firstLastd[1])
	strand = firstLastd[2]
	h = getHealth(strand, first, last, largest)
	(hMin, hMax) = (min(hMin, h), max(hMax, h))
print(hMin, hMax)


from math import inf
from bisect import bisect_left as bLeft, bisect_right as bRight
from collections import defaultdict

def getHealth(seq, first, last, largest):
	(h, ls) = (0, len(seq))
	for f in range(ls):
		for j in range(1, largest + 1):
			if f + j > ls:
				break
			sub = seq[f:f + j]
			if sub not in subs:
				break
			if sub not in gMap:
				continue
			(ids, hs) = gMap[sub]
			h += hs[bRight(ids, last)] - hs[bLeft(ids, first)]
	return h
howGenes = int(input())
genes = input().rstrip().split()
healths = list(map(int, input().rstrip().split()))
howStrands = int(input())
gMap = defaultdict(lambda : [[], [0]])
subs = set()
for (id, gene) in enumerate(genes):
	gMap[gene][0].append(id)
	for j in range(1, min(len(gene), 500) + 1):
		subs.add(gene[:j])
for v in gMap.values():
	for (i, ix) in enumerate(v[0]):
		v[1].append(v[1][i] + healths[ix])
largest = max(list(map(len, genes)))
(hMin, hMax) = (inf, 0)
for _ in range(howStrands):
	firstLastd = input().split()
	first = int(firstLastd[0])
	last = int(firstLastd[1])
	strand = firstLastd[2]
	h = getHealth(strand, first, last, largest)
	(hMin, hMax) = (min(hMin, h), max(hMax, h))
print(hMin, hMax)


from math import inf
from bisect import bisect_left as bLeft, bisect_right as bRight
from collections import defaultdict

def getHealth(seq, first, last, largest):
	(h, ls) = (0, len(seq))
	for f in range(ls):
		for j in range(1, largest + 1):
			if f + j > ls:
				break
			sub = seq[f:f + j]
			if sub not in subs:
				break
			if sub not in gMap:
				continue
			(ids, hs) = gMap[sub]
			h += hs[bRight(ids, last)] - hs[bLeft(ids, first)]
	return h
howGenes = int(input())
genes = input().rstrip().split()
healths = list(map(int, input().rstrip().split()))
howStrands = int(input())
gMap = defaultdict(lambda : [[], [0]])
subs = set()
for (id, gene) in enumerate(genes):
	gMap[gene][0].append(id)
	for j in range(1, min(len(gene), 500) + 1):
		subs.add(gene[:j])
for v in gMap.values():
	for (i, ix) in enumerate(v[0]):
		v[1].append(v[1][i] + healths[ix])
largest = max(list(map(len, genes)))
(hMin, hMax) = (inf, 0)
for _ in range(howStrands):
	firstLastd = input().split()
	first = int(firstLastd[0])
	last = int(firstLastd[1])
	strand = firstLastd[2]
	h = getHealth(strand, first, last, largest)
	(hMin, hMax) = (min(hMin, h), max(hMax, h))
print(hMin, hMax)


from math import inf
from bisect import bisect_left as bLeft, bisect_right as bRight
from collections import defaultdict

def getHealth(seq, first, last, largest):
	(h, ls) = (0, len(seq))
	for f in range(ls):
		for j in range(1, largest + 1):
			if f + j > ls:
				break
			sub = seq[f:f + j]
			if sub not in subs:
				break
			if sub not in gMap:
				continue
			(ids, hs) = gMap[sub]
			h += hs[bRight(ids, last)] - hs[bLeft(ids, first)]
	return h
howGenes = int(input())
genes = input().rstrip().split()
healths = list(map(int, input().rstrip().split()))
howStrands = int(input())
gMap = defaultdict(lambda : [[], [0]])
subs = set()
for (id, gene) in enumerate(genes):
	gMap[gene][0].append(id)
	for j in range(1, min(len(gene), 500) + 1):
		subs.add(gene[:j])
for v in gMap.values():
	for (i, ix) in enumerate(v[0]):
		v[1].append(v[1][i] + healths[ix])
largest = max(list(map(len, genes)))
(hMin, hMax) = (inf, 0)
for _ in range(howStrands):
	firstLastd = input().split()
	first = int(firstLastd[0])
	last = int(firstLastd[1])
	strand = firstLastd[2]
	h = getHealth(strand, first, last, largest)
	(hMin, hMax) = (min(hMin, h), max(hMax, h))
print(hMin, hMax)


from math import inf
from bisect import bisect_left as bLeft, bisect_right as bRight
from collections import defaultdict

def getHealth(seq, first, last, largest):
	(h, ls) = (0, len(seq))
	for f in range(ls):
		for j in range(1, largest + 1):
			if f + j > ls:
				break
			sub = seq[f:f + j]
			if sub not in subs:
				break
			if sub not in gMap:
				continue
			(ids, hs) = gMap[sub]
			h += hs[bRight(ids, last)] - hs[bLeft(ids, first)]
	return h
howGenes = int(input())
genes = input().rstrip().split()
healths = list(map(int, input().rstrip().split()))
howStrands = int(input())
gMap = defaultdict(lambda : [[], [0]])
subs = set()
for (id, gene) in enumerate(genes):
	gMap[gene][0].append(id)
	for j in range(1, min(len(gene), 500) + 1):
		subs.add(gene[:j])
for v in gMap.values():
	for (i, ix) in enumerate(v[0]):
		v[1].append(v[1][i] + healths[ix])
largest = max(list(map(len, genes)))
(hMin, hMax) = (inf, 0)
for _ in range(howStrands):
	firstLastd = input().split()
	first = int(firstLastd[0])
	last = int(firstLastd[1])
	strand = firstLastd[2]
	h = getHealth(strand, first, last, largest)
	(hMin, hMax) = (min(hMin, h), max(hMax, h))
print(hMin, hMax)


from math import inf
from bisect import bisect_left as bLeft, bisect_right as bRight
from collections import defaultdict

def getHealth(seq, first, last, largest):
	(h, ls) = (0, len(seq))
	for f in range(ls):
		for j in range(1, largest + 1):
			if f + j > ls:
				break
			sub = seq[f:f + j]
			if sub not in subs:
				break
			if sub not in gMap:
				continue
			(ids, hs) = gMap[sub]
			h += hs[bRight(ids, last)] - hs[bLeft(ids, first)]
	return h
howGenes = int(input())
genes = input().rstrip().split()
healths = list(map(int, input().rstrip().split()))
howStrands = int(input())
gMap = defaultdict(lambda : [[], [0]])
subs = set()
for (id, gene) in enumerate(genes):
	gMap[gene][0].append(id)
	for j in range(1, min(len(gene), 500) + 1):
		subs.add(gene[:j])
for v in gMap.values():
	for (i, ix) in enumerate(v[0]):
		v[1].append(v[1][i] + healths[ix])
largest = max(list(map(len, genes)))
(hMin, hMax) = (inf, 0)
for _ in range(howStrands):
	firstLastd = input().split()
	first = int(firstLastd[0])
	last = int(firstLastd[1])
	strand = firstLastd[2]
	h = getHealth(strand, first, last, largest)
	(hMin, hMax) = (min(hMin, h), max(hMax, h))
print(hMin, hMax)


from math import inf
from bisect import bisect_left as bLeft, bisect_right as bRight
from collections import defaultdict

def getHealth(seq, first, last, largest):
	(h, ls) = (0, len(seq))
	for f in range(ls):
		for j in range(1, largest + 1):
			if f + j > ls:
				break
			sub = seq[f:f + j]
			if sub not in subs:
				break
			if sub not in gMap:
				continue
			(ids, hs) = gMap[sub]
			h += hs[bRight(ids, last)] - hs[bLeft(ids, first)]
	return h
howGenes = int(input())
genes = input().rstrip().split()
healths = list(map(int, input().rstrip().split()))
howStrands = int(input())
gMap = defaultdict(lambda : [[], [0]])
subs = set()
for (id, gene) in enumerate(genes):
	gMap[gene][0].append(id)
	for j in range(1, min(len(gene), 500) + 1):
		subs.add(gene[:j])
for v in gMap.values():
	for (i, ix) in enumerate(v[0]):
		v[1].append(v[1][i] + healths[ix])
largest = max(list(map(len, genes)))
(hMin, hMax) = (inf, 0)
for _ in range(howStrands):
	firstLastd = input().split()
	first = int(firstLastd[0])
	last = int(firstLastd[1])
	strand = firstLastd[2]
	h = getHealth(strand, first, last, largest)
	(hMin, hMax) = (min(hMin, h), max(hMax, h))
print(hMin, hMax)


from math import inf
from bisect import bisect_left as bLeft, bisect_right as bRight
from collections import defaultdict

def getHealth(seq, first, last, largest):
	(h, ls) = (0, len(seq))
	for f in range(ls):
		for j in range(1, largest + 1):
			if f + j > ls:
				break
			sub = seq[f:f + j]
			if sub not in subs:
				break
			if sub not in gMap:
				continue
			(ids, hs) = gMap[sub]
			h += hs[bRight(ids, last)] - hs[bLeft(ids, first)]
	return h
howGenes = int(input())
genes = input().rstrip().split()
healths = list(map(int, input().rstrip().split()))
howStrands = int(input())
gMap = defaultdict(lambda : [[], [0]])
subs = set()
for (id, gene) in enumerate(genes):
	gMap[gene][0].append(id)
	for j in range(1, min(len(gene), 500) + 1):
		subs.add(gene[:j])
for v in gMap.values():
	for (i, ix) in enumerate(v[0]):
		v[1].append(v[1][i] + healths[ix])
largest = max(list(map(len, genes)))
(hMin, hMax) = (inf, 0)
for _ in range(howStrands):
	firstLastd = input().split()
	first = int(firstLastd[0])
	last = int(firstLastd[1])
	strand = firstLastd[2]
	h = getHealth(strand, first, last, largest)
	(hMin, hMax) = (min(hMin, h), max(hMax, h))
print(hMin, hMax)


from math import inf
from bisect import bisect_left as bLeft, bisect_right as bRight
from collections import defaultdict

def getHealth(seq, first, last, largest):
	(h, ls) = (0, len(seq))
	for f in range(ls):
		for j in range(1, largest + 1):
			if f + j > ls:
				break
			sub = seq[f:f + j]
			if sub not in subs:
				break
			if sub not in gMap:
				continue
			(ids, hs) = gMap[sub]
			h += hs[bRight(ids, last)] - hs[bLeft(ids, first)]
	return h
howGenes = int(input())
genes = input().rstrip().split()
healths = list(map(int, input().rstrip().split()))
howStrands = int(input())
gMap = defaultdict(lambda : [[], [0]])
subs = set()
for (id, gene) in enumerate(genes):
	gMap[gene][0].append(id)
	for j in range(1, min(len(gene), 500) + 1):
		subs.add(gene[:j])
for v in gMap.values():
	for (i, ix) in enumerate(v[0]):
		v[1].append(v[1][i] + healths[ix])
largest = max(list(map(len, genes)))
(hMin, hMax) = (inf, 0)
for _ in range(howStrands):
	firstLastd = input().split()
	first = int(firstLastd[0])
	last = int(firstLastd[1])
	strand = firstLastd[2]
	h = getHealth(strand, first, last, largest)
	(hMin, hMax) = (min(hMin, h), max(hMax, h))
print(hMin, hMax)


from math import inf
from bisect import bisect_left as bLeft, bisect_right as bRight
from collections import defaultdict

def getHealth(seq, first, last, largest):
	(h, ls) = (0, len(seq))
	for f in range(ls):
		for j in range(1, largest + 1):
			if f + j > ls:
				break
			sub = seq[f:f + j]
			if sub not in subs:
				break
			if sub not in gMap:
				continue
			(ids, hs) = gMap[sub]
			h += hs[bRight(ids, last)] - hs[bLeft(ids, first)]
	return h
howGenes = int(input())
genes = input().rstrip().split()
healths = list(map(int, input().rstrip().split()))
howStrands = int(input())
gMap = defaultdict(lambda : [[], [0]])
subs = set()
for (id, gene) in enumerate(genes):
	gMap[gene][0].append(id)
	for j in range(1, min(len(gene), 500) + 1):
		subs.add(gene[:j])
for v in gMap.values():
	for (i, ix) in enumerate(v[0]):
		v[1].append(v[1][i] + healths[ix])
largest = max(list(map(len, genes)))
(hMin, hMax) = (inf, 0)
for _ in range(howStrands):
	firstLastd = input().split()
	first = int(firstLastd[0])
	last = int(firstLastd[1])
	strand = firstLastd[2]
	h = getHealth(strand, first, last, largest)
	(hMin, hMax) = (min(hMin, h), max(hMax, h))
print(hMin, hMax)


from math import inf
from bisect import bisect_left as bLeft, bisect_right as bRight
from collections import defaultdict

def getHealth(seq, first, last, largest):
	(h, ls) = (0, len(seq))
	for f in range(ls):
		for j in range(1, largest + 1):
			if f + j > ls:
				break
			sub = seq[f:f + j]
			if sub not in subs:
				break
			if sub not in gMap:
				continue
			(ids, hs) = gMap[sub]
			h += hs[bRight(ids, last)] - hs[bLeft(ids, first)]
	return h
howGenes = int(input())
genes = input().rstrip().split()
healths = list(map(int, input().rstrip().split()))
howStrands = int(input())
gMap = defaultdict(lambda : [[], [0]])
subs = set()
for (id, gene) in enumerate(genes):
	gMap[gene][0].append(id)
	for j in range(1, min(len(gene), 500) + 1):
		subs.add(gene[:j])
for v in gMap.values():
	for (i, ix) in enumerate(v[0]):
		v[1].append(v[1][i] + healths[ix])
largest = max(list(map(len, genes)))
(hMin, hMax) = (inf, 0)
for _ in range(howStrands):
	firstLastd = input().split()
	first = int(firstLastd[0])
	last = int(firstLastd[1])
	strand = firstLastd[2]
	h = getHealth(strand, first, last, largest)
	(hMin, hMax) = (min(hMin, h), max(hMax, h))
print(hMin, hMax)


from math import inf
from bisect import bisect_left as bLeft, bisect_right as bRight
from collections import defaultdict

def getHealth(seq, first, last, largest):
	(h, ls) = (0, len(seq))
	for f in range(ls):
		for j in range(1, largest + 1):
			if f + j > ls:
				break
			sub = seq[f:f + j]
			if sub not in subs:
				break
			if sub not in gMap:
				continue
			(ids, hs) = gMap[sub]
			h += hs[bRight(ids, last)] - hs[bLeft(ids, first)]
	return h
howGenes = int(input())
genes = input().rstrip().split()
healths = list(map(int, input().rstrip().split()))
howStrands = int(input())
gMap = defaultdict(lambda : [[], [0]])
subs = set()
for (id, gene) in enumerate(genes):
	gMap[gene][0].append(id)
	for j in range(1, min(len(gene), 500) + 1):
		subs.add(gene[:j])
for v in gMap.values():
	for (i, ix) in enumerate(v[0]):
		v[1].append(v[1][i] + healths[ix])
largest = max(list(map(len, genes)))
(hMin, hMax) = (inf, 0)
for _ in range(howStrands):
	firstLastd = input().split()
	first = int(firstLastd[0])
	last = int(firstLastd[1])
	strand = firstLastd[2]
	h = getHealth(strand, first, last, largest)
	(hMin, hMax) = (min(hMin, h), max(hMax, h))
print(hMin, hMax)


import math
import os
import random
import re
import sys
from collections import defaultdict
from math import inf
from bisect import bisect_left as bLeft, bisect_right as bRight

def getHealth(seq, first, last, largest):
	(h, ls) = (0, len(seq))
	for f in range(ls):
		for j in range(1, largest + 1):
			if f + j > ls:
				break
			sub = seq[f:f + j]
			if sub not in subs:
				break
			if sub not in gMap:
				continue
			(ids, hs) = gMap[sub]
			h += hs[bRight(ids, last)] - hs[bLeft(ids, first)]
	return h
howGenes = int(input())
genes = input().rstrip().split()
healths = list(map(int, input().rstrip().split()))
howStrands = int(input())
gMap = defaultdict(lambda : [[], [0]])
subs = set()
for (id, gene) in enumerate(genes):
	gMap[gene][0].append(id)
	for j in range(1, min(len(gene), 500) + 1):
		subs.add(gene[:j])
for v in gMap.values():
	for (i, ix) in enumerate(v[0]):
		v[1].append(v[1][i] + healths[ix])
largest = max(list(map(len, genes)))
(hMin, hMax) = (inf, 0)
for _ in range(howStrands):
	firstLastd = input().split()
	first = int(firstLastd[0])
	last = int(firstLastd[1])
	strand = firstLastd[2]
	h = getHealth(strand, first, last, largest)
	(hMin, hMax) = (min(hMin, h), max(hMax, h))
print(hMin, hMax)


from math import inf
from bisect import bisect_left as bLeft, bisect_right as bRight
from collections import defaultdict

def getHealth(seq, first, last, largest):
	(h, ls) = (0, len(seq))
	for f in range(ls):
		for j in range(1, largest + 1):
			if f + j > ls:
				break
			sub = seq[f:f + j]
			if sub not in subs:
				break
			if sub not in gMap:
				continue
			(ids, hs) = gMap[sub]
			h += hs[bRight(ids, last)] - hs[bLeft(ids, first)]
	return h
howGenes = int(input())
genes = input().rstrip().split()
healths = list(map(int, input().rstrip().split()))
howStrands = int(input())
gMap = defaultdict(lambda : [[], [0]])
subs = set()
for (id, gene) in enumerate(genes):
	gMap[gene][0].append(id)
	for j in range(1, min(len(gene), 500) + 1):
		subs.add(gene[:j])
for v in gMap.values():
	for (i, ix) in enumerate(v[0]):
		v[1].append(v[1][i] + healths[ix])
largest = max(list(map(len, genes)))
(hMin, hMax) = (inf, 0)
for _ in range(howStrands):
	firstLastd = input().split()
	first = int(firstLastd[0])
	last = int(firstLastd[1])
	strand = firstLastd[2]
	h = getHealth(strand, first, last, largest)
	(hMin, hMax) = (min(hMin, h), max(hMax, h))
print(hMin, hMax)


from math import inf
from bisect import bisect_left as bLeft, bisect_right as bRight
from collections import defaultdict

def getHealth(seq, first, last, largest):
	(h, ls) = (0, len(seq))
	for f in range(ls):
		for j in range(1, largest + 1):
			if f + j > ls:
				break
			sub = seq[f:f + j]
			if sub not in subs:
				break
			if sub not in gMap:
				continue
			(ids, hs) = gMap[sub]
			h += hs[bRight(ids, last)] - hs[bLeft(ids, first)]
	return h
howGenes = int(input())
genes = input().rstrip().split()
healths = list(map(int, input().rstrip().split()))
howStrands = int(input())
gMap = defaultdict(lambda : [[], [0]])
subs = set()
for (id, gene) in enumerate(genes):
	gMap[gene][0].append(id)
	for j in range(1, min(len(gene), 500) + 1):
		subs.add(gene[:j])
for v in gMap.values():
	for (i, ix) in enumerate(v[0]):
		v[1].append(v[1][i] + healths[ix])
largest = max(list(map(len, genes)))
(hMin, hMax) = (inf, 0)
for _ in range(howStrands):
	firstLastd = input().split()
	first = int(firstLastd[0])
	last = int(firstLastd[1])
	strand = firstLastd[2]
	h = getHealth(strand, first, last, largest)
	(hMin, hMax) = (min(hMin, h), max(hMax, h))
print(hMin, hMax)


from math import inf
from bisect import bisect_left as bLeft, bisect_right as bRight
from collections import defaultdict

def getHealth(seq, first, last, largest):
	(h, ls) = (0, len(seq))
	for f in range(ls):
		for j in range(1, largest + 1):
			if f + j > ls:
				break
			sub = seq[f:f + j]
			if sub not in subs:
				break
			if sub not in gMap:
				continue
			(ids, hs) = gMap[sub]
			h += hs[bRight(ids, last)] - hs[bLeft(ids, first)]
	return h
howGenes = int(input())
genes = input().rstrip().split()
healths = list(map(int, input().rstrip().split()))
howStrands = int(input())
gMap = defaultdict(lambda : [[], [0]])
subs = set()
for (id, gene) in enumerate(genes):
	gMap[gene][0].append(id)
	for j in range(1, min(len(gene), 500) + 1):
		subs.add(gene[:j])
for v in gMap.values():
	for (i, ix) in enumerate(v[0]):
		v[1].append(v[1][i] + healths[ix])
largest = max(list(map(len, genes)))
(hMin, hMax) = (inf, 0)
for _ in range(howStrands):
	firstLastd = input().split()
	first = int(firstLastd[0])
	last = int(firstLastd[1])
	strand = firstLastd[2]
	h = getHealth(strand, first, last, largest)
	(hMin, hMax) = (min(hMin, h), max(hMax, h))
print(hMin, hMax)


from math import inf
from bisect import bisect_left as bLeft, bisect_right as bRight
from collections import defaultdict

def getHealth(seq, first, last, largest):
	(h, ls) = (0, len(seq))
	for f in range(ls):
		for j in range(1, largest + 1):
			if f + j > ls:
				break
			sub = seq[f:f + j]
			if sub not in subs:
				break
			if sub not in gMap:
				continue
			(ids, hs) = gMap[sub]
			h += hs[bRight(ids, last)] - hs[bLeft(ids, first)]
	return h
howGenes = int(input())
genes = input().rstrip().split()
healths = list(map(int, input().rstrip().split()))
howStrands = int(input())
gMap = defaultdict(lambda : [[], [0]])
subs = set()
for (id, gene) in enumerate(genes):
	gMap[gene][0].append(id)
	for j in range(1, min(len(gene), 500) + 1):
		subs.add(gene[:j])
for v in gMap.values():
	for (i, ix) in enumerate(v[0]):
		v[1].append(v[1][i] + healths[ix])
largest = max(list(map(len, genes)))
(hMin, hMax) = (inf, 0)
for _ in range(howStrands):
	firstLastd = input().split()
	first = int(firstLastd[0])
	last = int(firstLastd[1])
	strand = firstLastd[2]
	h = getHealth(strand, first, last, largest)
	(hMin, hMax) = (min(hMin, h), max(hMax, h))
print(hMin, hMax)


from math import inf
from bisect import bisect_left as bLeft, bisect_right as bRight
from collections import defaultdict

def getHealth(seq, first, last, largest):
	(h, ls) = (0, len(seq))
	for f in range(ls):
		for j in range(1, largest + 1):
			if f + j > ls:
				break
			sub = seq[f:f + j]
			if sub not in subs:
				break
			if sub not in gMap:
				continue
			(ids, hs) = gMap[sub]
			h += hs[bRight(ids, last)] - hs[bLeft(ids, first)]
	return h
howGenes = int(input())
genes = input().rstrip().split()
healths = list(map(int, input().rstrip().split()))
howStrands = int(input())
gMap = defaultdict(lambda : [[], [0]])
subs = set()
for (id, gene) in enumerate(genes):
	gMap[gene][0].append(id)
	for j in range(1, min(len(gene), 500) + 1):
		subs.add(gene[:j])
for v in gMap.values():
	for (i, ix) in enumerate(v[0]):
		v[1].append(v[1][i] + healths[ix])
largest = max(list(map(len, genes)))
(hMin, hMax) = (inf, 0)
for _ in range(howStrands):
	firstLastd = input().split()
	first = int(firstLastd[0])
	last = int(firstLastd[1])
	strand = firstLastd[2]
	h = getHealth(strand, first, last, largest)
	(hMin, hMax) = (min(hMin, h), max(hMax, h))
print(hMin, hMax)


from math import inf
from bisect import bisect_left as bLeft, bisect_right as bRight
from collections import defaultdict

def getHealth(seq, first, last, largest):
	(h, ls) = (0, len(seq))
	for f in range(ls):
		for j in range(1, largest + 1):
			if f + j > ls:
				break
			sub = seq[f:f + j]
			if sub not in subs:
				break
			if sub not in gMap:
				continue
			(ids, hs) = gMap[sub]
			h += hs[bRight(ids, last)] - hs[bLeft(ids, first)]
	return h
howGenes = int(input())
genes = input().rstrip().split()
healths = list(map(int, input().rstrip().split()))
howStrands = int(input())
gMap = defaultdict(lambda : [[], [0]])
subs = set()
for (id, gene) in enumerate(genes):
	gMap[gene][0].append(id)
	for j in range(1, min(len(gene), 500) + 1):
		subs.add(gene[:j])
for v in gMap.values():
	for (i, ix) in enumerate(v[0]):
		v[1].append(v[1][i] + healths[ix])
largest = max(list(map(len, genes)))
(hMin, hMax) = (inf, 0)
for _ in range(howStrands):
	firstLastd = input().split()
	first = int(firstLastd[0])
	last = int(firstLastd[1])
	strand = firstLastd[2]
	h = getHealth(strand, first, last, largest)
	(hMin, hMax) = (min(hMin, h), max(hMax, h))
print(hMin, hMax)


from math import inf
from bisect import bisect_left as bLeft, bisect_right as bRight
from collections import defaultdict

def getHealth(seq, first, last, largest):
	(h, ls) = (0, len(seq))
	for f in range(ls):
		for j in range(1, largest + 1):
			if f + j > ls:
				break
			sub = seq[f:f + j]
			if sub not in subs:
				break
			if sub not in gMap:
				continue
			(ids, hs) = gMap[sub]
			h += hs[bRight(ids, last)] - hs[bLeft(ids, first)]
	return h
howGenes = int(input())
genes = input().rstrip().split()
healths = list(map(int, input().rstrip().split()))
howStrands = int(input())
gMap = defaultdict(lambda : [[], [0]])
subs = set()
for (id, gene) in enumerate(genes):
	gMap[gene][0].append(id)
	for j in range(1, min(len(gene), 500) + 1):
		subs.add(gene[:j])
for v in gMap.values():
	for (i, ix) in enumerate(v[0]):
		v[1].append(v[1][i] + healths[ix])
largest = max(list(map(len, genes)))
(hMin, hMax) = (inf, 0)
for _ in range(howStrands):
	firstLastd = input().split()
	first = int(firstLastd[0])
	last = int(firstLastd[1])
	strand = firstLastd[2]
	h = getHealth(strand, first, last, largest)
	(hMin, hMax) = (min(hMin, h), max(hMax, h))
print(hMin, hMax)


from math import inf
from bisect import bisect_left as bLeft, bisect_right as bRight
from collections import defaultdict

def getHealth(seq, first, last, largest):
	(h, ls) = (0, len(seq))
	for f in range(ls):
		for j in range(1, largest + 1):
			if f + j > ls:
				break
			sub = seq[f:f + j]
			if sub not in subs:
				break
			if sub not in gMap:
				continue
			(ids, hs) = gMap[sub]
			h += hs[bRight(ids, last)] - hs[bLeft(ids, first)]
	return h
howGenes = int(input())
genes = input().rstrip().split()
healths = list(map(int, input().rstrip().split()))
howStrands = int(input())
gMap = defaultdict(lambda : [[], [0]])
subs = set()
for (id, gene) in enumerate(genes):
	gMap[gene][0].append(id)
	for j in range(1, min(len(gene), 500) + 1):
		subs.add(gene[:j])
for v in gMap.values():
	for (i, ix) in enumerate(v[0]):
		v[1].append(v[1][i] + healths[ix])
largest = max(list(map(len, genes)))
(hMin, hMax) = (inf, 0)
for _ in range(howStrands):
	firstLastd = input().split()
	first = int(firstLastd[0])
	last = int(firstLastd[1])
	strand = firstLastd[2]
	h = getHealth(strand, first, last, largest)
	(hMin, hMax) = (min(hMin, h), max(hMax, h))
print(hMin, hMax)


from math import inf
from bisect import bisect_left as bLeft, bisect_right as bRight
from collections import defaultdict

def getHealth(seq, first, last, largest):
	(h, ls) = (0, len(seq))
	for f in range(ls):
		for j in range(1, largest + 1):
			if f + j > ls:
				break
			sub = seq[f:f + j]
			if sub not in subs:
				break
			if sub not in gMap:
				continue
			(ids, hs) = gMap[sub]
			h += hs[bRight(ids, last)] - hs[bLeft(ids, first)]
	return h
howGenes = int(input())
genes = input().rstrip().split()
healths = list(map(int, input().rstrip().split()))
howStrands = int(input())
gMap = defaultdict(lambda : [[], [0]])
subs = set()
for (id, gene) in enumerate(genes):
	gMap[gene][0].append(id)
	for j in range(1, min(len(gene), 500) + 1):
		subs.add(gene[:j])
for v in gMap.values():
	for (i, ix) in enumerate(v[0]):
		v[1].append(v[1][i] + healths[ix])
largest = max(list(map(len, genes)))
(hMin, hMax) = (inf, 0)
for _ in range(howStrands):
	firstLastd = input().split()
	first = int(firstLastd[0])
	last = int(firstLastd[1])
	strand = firstLastd[2]
	h = getHealth(strand, first, last, largest)
	(hMin, hMax) = (min(hMin, h), max(hMax, h))
print(hMin, hMax)


import math
import os
import random
import re
import sys
from bisect import bisect_left, bisect_right
from collections import defaultdict

def getHealth(seq, first, last, largest):
	(h, ls) = (0, len(seq))
	for f in range(ls):
		for j in range(1, largest + 1):
			if f + j > ls:
				break
			sub = seq[f:f + j]
			if sub not in subs:
				break
			if sub not in genesMap:
				continue
			(ids, hs) = genesMap[sub]
			h += hs[bisect_right(ids, last)] - hs[bisect_left(ids, first)]
	return h
n = int(input())
genes = input().rstrip().split()
health = list(map(int, input().rstrip().split()))
genesMap = defaultdict(lambda : [[], [0]])
subs = set()
for (i, gene) in enumerate(genes):
	genesMap[gene][0].append(i)
	for j in range(1, len(gene) + 1):
		subs.add(gene[:j])
for v in genesMap.values():
	for (i, ix) in enumerate(v[0]):
		v[1].append(v[1][i] + health[ix])
largest = max(list(map(len, genes)))
(hMin, hMax) = (float('inf'), 0)
s = int(input())
for s_itr in range(s):
	firstLastd = input().split()
	first = int(firstLastd[0])
	last = int(firstLastd[1])
	d = firstLastd[2]
	h = getHealth(d, first, last, largest)
	(hMin, hMax) = (min(hMin, h), max(hMax, h))
print(hMin, hMax)


from bisect import bisect_left as bLeft, bisect_right as bRight
from collections import defaultdict

def getHealth(seq, first, last, largest):
	(h, ls) = (0, len(seq))
	for f in range(ls):
		for j in range(1, largest + 1):
			if f + j > ls:
				break
			sub = seq[f:f + j]
			if sub not in subs:
				break
			if sub not in gMap:
				continue
			(ids, hs) = gMap[sub]
			h += hs[bRight(ids, last)] - hs[bLeft(ids, first)]
	return h
howGenes = int(input())
genes = input().split()
healths = list(map(int, input().split()))
howStrands = int(input())
gMap = defaultdict(lambda : [[], [0]])
subs = set()
for (id, gene) in enumerate(genes):
	gMap[gene][0].append(id)
	for j in range(1, min(len(gene), 500) + 1):
		subs.add(gene[:j])
for v in gMap.values():
	for (i, ix) in enumerate(v[0]):
		v[1].append(v[1][i] + healths[ix])
(largest, h) = (max(map(len, genes)), [])
for _ in range(howStrands):
	firstLastd = input().split()
	first = int(firstLastd[0])
	last = int(firstLastd[1])
	strand = firstLastd[2]
	h += [getHealth(strand, first, last, largest)]
print(min(h), max(h))


from math import inf
from bisect import bisect_left as bLeft, bisect_right as bRight
from collections import defaultdict

def getHealth(seq, first, last, largest):
	(h, ls) = (0, len(seq))
	for f in range(ls):
		for j in range(1, largest + 1):
			if f + j > ls:
				break
			sub = seq[f:f + j]
			if sub not in subs:
				break
			if sub not in gMap:
				continue
			(ids, hs) = gMap[sub]
			h += hs[bRight(ids, last)] - hs[bLeft(ids, first)]
	return h
howGenes = int(input())
genes = input().rstrip().split()
healths = list(map(int, input().rstrip().split()))
howStrands = int(input())
gMap = defaultdict(lambda : [[], [0]])
subs = set()
for (id, gene) in enumerate(genes):
	gMap[gene][0].append(id)
	for j in range(1, min(len(gene), 500) + 1):
		subs.add(gene[:j])
for v in gMap.values():
	for (i, ix) in enumerate(v[0]):
		v[1].append(v[1][i] + healths[ix])
largest = max(list(map(len, genes)))
(hMin, hMax) = (inf, 0)
for _ in range(howStrands):
	firstLastd = input().split()
	first = int(firstLastd[0])
	last = int(firstLastd[1])
	strand = firstLastd[2]
	h = getHealth(strand, first, last, largest)
	(hMin, hMax) = (min(hMin, h), max(hMax, h))
print(hMin, hMax)


from math import inf
from bisect import bisect_left as bLeft, bisect_right as bRight
from collections import defaultdict

def getHealth(seq, first, last, largest):
	(h, ls) = (0, len(seq))
	for f in range(ls):
		for j in range(1, largest + 1):
			if f + j > ls:
				break
			sub = seq[f:f + j]
			if sub not in subs:
				break
			if sub not in gMap:
				continue
			(ids, hs) = gMap[sub]
			h += hs[bRight(ids, last)] - hs[bLeft(ids, first)]
	return h
howGenes = int(input())
genes = input().rstrip().split()
healths = list(map(int, input().rstrip().split()))
howStrands = int(input())
gMap = defaultdict(lambda : [[], [0]])
subs = set()
for (id, gene) in enumerate(genes):
	gMap[gene][0].append(id)
	for j in range(1, min(len(gene), 500) + 1):
		subs.add(gene[:j])
for v in gMap.values():
	for (i, ix) in enumerate(v[0]):
		v[1].append(v[1][i] + healths[ix])
largest = max(list(map(len, genes)))
(hMin, hMax) = (inf, 0)
for _ in range(howStrands):
	firstLastd = input().split()
	first = int(firstLastd[0])
	last = int(firstLastd[1])
	strand = firstLastd[2]
	h = getHealth(strand, first, last, largest)
	(hMin, hMax) = (min(hMin, h), max(hMax, h))
print(hMin, hMax)