You are given some text $t$ and a set of $n$ strings $s_1, s_2, \dots, s_n$.

In one step, you can choose any occurrence of any string $s_i$ in the text $t$ and color the corresponding characters of the text in red. For example, if $t={bababa}$ and $s_1={ba}$, $s_2={aba}$, you can get $t={{ba}}{baba}$, $t={b}{{aba}}{ba}$ or $t={bab}{{aba}}$ in one step.

You want to color all the letters of the text $t$ in red. When you color a letter in red again, it stays red.

In the example above, three steps are enough:

Let's color $t[2 \dots 4]=s_2={aba}$ in red, we get $t={b}{{aba}}{ba}$;

Let's color $t[1 \dots 2]=s_1={ba}$ in red, we get $t={{baba}}{ba}$;

Let's color $t[4 \dots 6]=s_2={aba}$ in red, we get $t={{bababa}}$.

Each string $s_i$ can be applied any number of times (or not at all). Occurrences for coloring can intersect arbitrarily.

Determine the minimum number of steps needed to color all letters $t$ in red and how to do it. If it is impossible to color all letters of the text $t$ in red, output -1.


-----Input-----

The first line of the input contains an integer $q$ ($1 \le q \le 100$) —the number of test cases in the test.

The descriptions of the test cases follow.

The first line of each test case contains the text $t$ ($1 \le |t| \le 100$), consisting only of lowercase Latin letters, where $|t|$ is the length of the text $t$.

The second line of each test case contains a single integer $n$ ($1 \le n \le 10$) — the number of strings in the set.

This is followed by $n$ lines, each containing a string $s_i$ ($1 \le |s_i| \le 10$) consisting only of lowercase Latin letters, where $|s_i|$ — the length of string $s_i$.


-----Output-----

For each test case, print the answer on a separate line.

If it is impossible to color all the letters of the text in red, print a single line containing the number -1.

Otherwise, on the first line, print the number $m$ — the minimum number of steps it will take to turn all the letters $t$ red.

Then in the next $m$ lines print pairs of indices: $w_j$ and $p_j$ ($1 \le j \le m$), which denote that the string with index $w_j$ was used as a substring to cover the occurrences starting in the text $t$ from position $p_j$. The pairs can be output in any order.

If there are several answers, output any of them.


-----Examples-----

Input
6
bababa
2
ba
aba
caba
2
bac
acab
abacabaca
3
aba
bac
aca
baca
3
a
c
b
codeforces
4
def
code
efo
forces
aaaabbbbcccceeee
4
eeee
cccc
aaaa
bbbb
Output
3
2 2
1 1
2 4
-1
4
1 1
2 6
3 3
3 7
4
3 1
1 2
2 3
1 4
2
4 5
2 1
4
3 1
4 5
2 9
1 13


-----Note-----

The first test case is explained in the problem statement.

In the second test case, it is impossible to color all the letters of the text in red.

Difficulty: MEDIUM_HARD
Tags: String algorithms

Greedy algorithms

Complete search

Dynamic programming

Data structures
Skill types: Dynamic programming

Data structures

Complete search

Greedy algorithms

Starter code:

Solutions:
def solve():
	t = input()
	n = int(input())
	strings = []
	for i in range(n):
		strings.append(input())
	intervals = []
	for i in range(n):
		for j in range(len(t)):
			if t[j:j + len(strings[i])] == strings[i]:
				intervals.append((j, j + len(strings[i]), i))
	intervals.sort()
	if len(intervals) == 0:
		return -1
	(s, e, ind) = intervals[0]
	if s != 0:
		return -1
	mmax = 0
	used = []
	ec = -1
	for (s, e, ind) in intervals:
		if s <= mmax:
			if e > ec:
				(sc, ec, indc) = (s, e, ind)
		else:
			used.append((sc, ec, indc))
			mmax = ec
			(sc, ec, indc) = (s, e, ind)
	if mmax != len(t):
		for (s, e, ind) in intervals:
			if e == len(t):
				used.append((s, e, ind))
				break
	covered = [0 for _ in range(len(t))]
	for (s, e, ind) in used:
		for i in range(s, e):
			covered[i] = 1
	if sum(covered) == len(t):
		return used
	else:
		return -1
q = int(input())
sol = []
for _ in range(q):
	sol.append(solve())
for so in sol:
	if so == -1:
		print(-1)
	else:
		print(len(so))
		for (s, e, ind) in so:
			print(ind + 1, s + 1)


def find(a, b, t, strs, ans):
	(maxi, id, pos) = (0, -1, -1)
	for i in range(a, b + 1):
		for j in range(len(strs)):
			s = strs[j]
			c = i + len(s)
			if c > len(t) or c <= b:
				continue
			if t[i:c] == s and c > maxi:
				maxi = c
				id = j
				pos = i
	if id == -1:
		return []
	else:
		ans.append((id, pos))
		if maxi == len(t):
			return ans
		else:
			return find(max(pos + 1, b + 1), maxi, t, strs, ans)
T = int(input())
for _ in range(T):
	t = input()
	n = int(input())
	strs = []
	for _ in range(n):
		s = input()
		strs.append(s)
	ans = find(0, 0, t, strs, [])
	if len(ans) == 0:
		print(-1)
	else:
		print(len(ans))
		for (a, b) in ans:
			print('{} {}'.format(a + 1, b + 1))


q = int(input())

def find(index, text, arr, n):
	id = -1
	mx_length = 0
	for i in range(n):
		if text[index:].find(arr[i]) == 0 and len(arr[i]) > mx_length:
			mx_length = len(arr[i])
			id = i + 1
	return id

def solve():
	t = input()
	n = int(input())
	arr = []
	for i in range(n):
		arr += [input()]
	start = 0
	ans = 0
	result = []
	idx = find(start, t, arr, n)
	if idx == -1:
		print(-1)
	else:
		ans += 1
		result += [[idx, start + 1]]
		right_most_colored = len(arr[idx - 1]) - 1
		while right_most_colored < len(t) - 1:
			idx = -1
			cnt = -1
			for i in range(start + 1, right_most_colored + 2):
				longest_covering_string = find(i, t, arr, n)
				if longest_covering_string != -1:
					if i + len(arr[longest_covering_string - 1]) - 1 > right_most_colored:
						right_most_colored = i + len(arr[longest_covering_string - 1]) - 1
						idx = longest_covering_string
						cnt = i
			if idx == -1:
				print(-1)
				return
			ans += 1
			result += [[idx, cnt + 1]]
			start = cnt
		print(ans)
		for i in range(ans):
			print(*result[i])
while q:
	solve()
	q -= 1


q = int(input())
for _ in range(q):
	t = input()
	n = int(input())
	S = [input() for i in range(n)]
	cur = 0
	mx = -1
	ans = []
	mxid = 0
	flag_bad = False
	for i in range(len(t)):
		for ids in range(len(S)):
			if i + len(S[ids]) <= len(t) and t[i:i + len(S[ids])] == S[ids]:
				if i + len(S[ids]) - 1 > mx:
					mx = i + len(S[ids]) - 1
					mxid = ids
		if cur == i:
			if mx < i:
				print(-1)
				flag_bad = True
				break
			else:
				ans.append((mxid + 1, mx - len(S[mxid]) + 2))
				cur = mx + 1
	if not flag_bad:
		print(len(ans))
		for el in ans:
			print(el[0], el[1])


ans = 0
ok = True

def Find(a, b, t, s_list, match):
	global ans, ok
	(Max, id, pos) = (0, -1, -1)
	for i in range(a, b + 1):
		for j in range(len(s_list)):
			s = s_list[j]
			if i + len(s) > len(t) or i + len(s) <= b:
				continue
			if t[i:i + len(s)] == s:
				if i + len(s) > Max:
					Max = i + len(s)
					id = j
					pos = i
	if id == -1:
		ok = False
		return
	else:
		match.append((id, pos))
		ans += 1
		if Max == len(t):
			return
		else:
			Find(b + 1, Max, t, s_list, match)

def solve():
	global ans, ok
	ans = 0
	ok = True
	t = input()
	n = int(input())
	s_list = []
	match = []
	for _ in range(n):
		s_list.append(input())
	Find(0, 0, t, s_list, match)
	if not ok:
		print(-1)
	else:
		print(ans)
		for p in match:
			print(p[0] + 1, p[1] + 1)
t = int(input())
for _ in range(t):
	solve()


from itertools import islice
t = int(input())
for i in range(t):
	text = input()
	m = int(input())
	strings = []
	indexes = {}
	for i in range(m):
		strings.append(input())
	indices = [-1] * (len(text) + 1)
	for (index, string) in enumerate(strings):
		i = 0
		while i + len(string) <= len(text):
			if text[i:i + len(string)] == string:
				if indices[i] < i + len(string):
					indices[i] = i + len(string)
					indexes[i] = index
			i += 1
	i = 0
	ans = []
	while i < len(text):
		(max_index, max_value) = max(enumerate(islice(indices, i + 1)), key=lambda k: k[1])
		if max_value <= i:
			print(-1)
			break
		else:
			ans.append((indexes[max_index], max_index))
			i = max_value
	else:
		print(len(ans))
		for (a, b) in ans:
			print(a + 1, b + 1)


from heapq import heappush, heappop

def main():
	for _ in range(int(input())):
		problem()

def problem():
	word = input().rstrip()
	num_piece = int(input())
	pieces = [input().rstrip() for _ in range(num_piece)]
	matches = [[] for _ in range(len(word))]
	for (pi, piece) in enumerate(pieces):
		for i in range(len(word)):
			if i + len(piece) > len(word):
				break
			if word[i:i + len(piece)] == piece:
				starts_at = i
				piece_no = pi
				ends_at = starts_at + len(piece)
				matches[i].append((ends_at, starts_at, piece_no))
	last_painted_until = -1
	painted_until = 0
	heap = []
	history = []
	while painted_until < len(word):
		for k in range(last_painted_until + 1, painted_until + 1):
			for match in matches[k]:
				(ends_at, starts_at, piece_no) = match
				heappush(heap, (-ends_at, starts_at, piece_no))
		if len(heap) == 0:
			print('-1')
			return
		(ends_at, starts_at, piece_no) = heappop(heap)
		ends_at = -ends_at
		history.append((piece_no, starts_at))
		last_painted_until = painted_until
		painted_until = ends_at
	print(len(history))
	for (i, j) in history:
		print(i + 1, j + 1)
import sys
input = sys.stdin.readline
sys.exit(main())


def main():
	t = input()
	n = len(t)
	ans = []
	ok = True
	substrings = []
	for _ in range(int(input())):
		substrings.append(input())
	s = sorted(substrings, key=len, reverse=True)
	i = 0
	while i < n:
		max_len = i
		index = 0
		pos = 0
		for w in s:
			lw = len(w)
			for j in range(lw):
				start = i - j
				end = i - j + lw
				if start > -1 and end <= n and (t[start:end] == w):
					if end > max_len:
						max_len = end
						index = substrings.index(w)
						pos = i - j
		if max_len == i:
			ok = False
			break
		ans.append([index, pos])
		i = max_len
	if ok:
		print(len(ans))
		for l in ans:
			print(f'{l[0] + 1} {l[1] + 1}')
	else:
		print(-1)
n = int(input())
for _ in range(n):
	main()


for _ in range(int(input())):
	st = input()
	case = []
	length = len(st)
	for i in range(int(input())):
		case.append(input())
	tas = []
	dp = [0] + [float('inf')] * length
	dic = {}
	dic2 = {}
	bre = False
	for i in range(0, length):
		for x in range(len(case)):
			leng = len(case[x])
			if i + leng <= length:
				sub = st[i:i + leng]
				if st[i:i + leng] == case[x]:
					for y in range(i, i + leng):
						mini = min(dp[y + 1], dp[i] + 1)
						dp[y + 1] = mini
					if mini <= dp[i + leng]:
						if mini in dic2:
							if i + leng > dic2[mini]:
								dic[mini] = [str(x + 1), str(i + 1)]
								dic2[mini] = i + leng
						else:
							dic[mini] = [str(x + 1), str(i + 1)]
							dic2[mini] = i + leng
	if dp[-1] != float('inf'):
		print(dp[-1])
		for x in dic.values():
			print(' '.join(x))
	else:
		print(-1)