A boy named Ayrat lives on planet AMI-1511. Each inhabitant of this planet has a talent. Specifically, Ayrat loves running, moreover, just running is not enough for him. He is dreaming of making running a real art.

First, he wants to construct the running track with coating t. On planet AMI-1511 the coating of the track is the sequence of colored blocks, where each block is denoted as the small English letter. Therefore, every coating can be treated as a string.

Unfortunately, blocks aren't freely sold to non-business customers, but Ayrat found an infinite number of coatings s. Also, he has scissors and glue. Ayrat is going to buy some coatings s, then cut out from each of them exactly one continuous piece (substring) and glue it to the end of his track coating. Moreover, he may choose to flip this block before glueing it. Ayrat want's to know the minimum number of coating s he needs to buy in order to get the coating t for his running track. Of course, he also want's to know some way to achieve the answer.


-----Input-----

First line of the input contains the string s — the coating that is present in the shop. Second line contains the string t — the coating Ayrat wants to obtain. Both strings are non-empty, consist of only small English letters and their length doesn't exceed 2100.


-----Output-----

The first line should contain the minimum needed number of coatings n or -1 if it's impossible to create the desired coating.

If the answer is not -1, then the following n lines should contain two integers x_{i} and y_{i} — numbers of ending blocks in the corresponding piece. If x_{i} ≤ y_{i} then this piece is used in the regular order, and if x_{i} > y_{i} piece is used in the reversed order. Print the pieces in the order they should be glued to get the string t.


-----Examples-----
Input
abc
cbaabc

Output
2
3 1
1 3

Input
aaabrytaaa
ayrat

Output
3
1 1
6 5
8 7

Input
ami
no

Output
-1



-----Note-----

In the first sample string "cbaabc" = "cba" + "abc".

In the second sample: "ayrat" = "a" + "yr" + "at".

Difficulty: HARD
Tags: Greedy algorithms

Tree algorithms

Dynamic programming

String algorithms
Skill types: Dynamic programming

Greedy algorithms

Starter code:

Solutions:
(s, t) = (input(), input())
(p, d) = ([], [[] for i in range(26)])
for (i, q) in enumerate(s):
	d[ord(q) - 97].append(i)
(i, n) = (0, len(t))
s += '+'
t += '-'
while i < n:
	q = t[i]
	a = b = c = 0
	for j in d[ord(q) - 97]:
		k = 1
		while t[i + k] == s[j + k]:
			k += 1
		if k > a:
			(a, b, c) = (k, j + 1, 1)
		k = 1
		while t[i + k] == s[j - k]:
			k += 1
		if k > a:
			(a, b, c) = (k, j + 1, -1)
	if not a:
		print(-1)
		return
	i += a
	p.append((b, b + c * a - c))
print(len(p))
for (i, j) in p:
	print(i, j)


s1 = input()
s = input() + '.'
s2 = s1[::-1]
l = len(s)
ll = len(s1)
a = ''
lis = []
for i in range(l):
	v = a + s[i]
	if v in s1 or v in s2:
		a = a + s[i]
	else:
		if a in s1:
			k = s1.index(a) + 1
			lis.append([k, k + len(a) - 1])
		elif a in s2:
			k = s2.index(a)
			lis.append([ll - k, ll - k - (len(a) - 1)])
		else:
			print(-1)
			exit()
		a = s[i]
print(len(lis))
for i in lis:
	print(*i)


import sys
s = input()
l = len(s)
s_r = s[::-1]
t = input()
lent = len(t)
res = 0
tracks = []
step = 0
while step < lent:
	if t[step:step + 1] not in s:
		print(-1)
		return
	plus = 1
	while (t[step:step + plus] in s or t[step:step + plus] in s_r) and step + plus < lent + 1:
		plus += 1
	if t[step:step + plus - 1] in s:
		x = s.find(t[step:step + plus - 1])
		tracks.append((x + 1, x + plus - 1))
	else:
		x = s_r.find(t[step:step + plus - 1])
		tracks.append((l - x, l - x - plus + 2))
	res += 1
	step += plus - 1
print(res)
for (a, b) in tracks:
	print(a, b)


import sys
s = input()
s_reverse = s[::-1]
t = input()
first = []
second = []
pos = 0

def find_str(st, char):
	index = 0
	if char in st:
		c = char[0]
		for ch in st:
			if ch == c:
				if st[index:index + len(char)] == char:
					return index
			index += 1
	return -1
while pos < len(t):
	substr = t[pos:pos + 1]
	if substr not in s and substr not in s_reverse:
		print('-1')
		sys.exit()
	step = 1
	while substr in s or substr in s_reverse:
		step += 1
		substr = t[pos:pos + step]
		if pos + step > len(t):
			break
	step -= 1
	substr = t[pos:pos + step]
	start = find_str(s, substr)
	if start == -1:
		start = find_str(s_reverse, substr)
		first.append(len(s) - start)
		second.append(len(s) - (start + step - 1))
	else:
		first.append(start + 1)
		second.append(start + step)
	pos = pos + step
print(len(first))
for (a, b) in zip(first, second):
	print('%d %d' % (a, b))


s = input()
t = input()
revS = s[::-1]
n = len(s)
cur = 1
start = -1
end = -1
revFlag = 0
errFlag = 0
i = 0
res = []
while i < len(t):
	if s.find(t[i:i + cur]) != -1 and i + cur <= len(t) and (s.find(t[i:i + cur]) + cur <= n):
		start = s.find(t[i:i + cur]) + 1
		end = start + cur - 1
		cur += 1
	elif revS.find(t[i:i + cur]) != -1 and i + cur <= len(t) and (revS.find(t[i:i + cur]) + cur <= n):
		start = n - revS.find(t[i:i + cur])
		end = start - cur + 1
		cur += 1
	else:
		if (start == -1 and end == -1) and (s.find(t[i:i + cur]) == -1 and revS.find(t[i:i + cur]) == -1):
			errFlag = 1
			break
		i += cur - 1
		cur = 1
		res.append(str(start) + ' ' + str(end))
		start = -1
		end = -1
if errFlag != 1:
	print(len(res))
	for p in res:
		print(p)
else:
	print(-1)


def find_max_substr(t, s):
	(l, r) = (0, len(t))
	while l != r:
		m = (l + r) // 2
		if t[:m + 1] in s:
			l = m + 1
		else:
			r = m
	l1 = l
	rs = s[::-1]
	(l, r) = (0, len(t))
	while l != r:
		m = (l + r) // 2
		if t[:m + 1] in rs:
			l = m + 1
		else:
			r = m
	l2 = l
	if l1 >= l2:
		return (s.find(t[:l1]) + 1, s.find(t[:l1]) + l1)
	else:
		return (s.find(t[:l2][::-1]) + l2, s.find(t[:l2][::-1]) + 1)
s = input()
t = input()
if not set(t).issubset(set(s)):
	print(-1)
	return
a = []
while t:
	(l, r) = find_max_substr(t, s)
	a.append((l, r))
	t = t[abs(r - l) + 1:]
print(len(a))
for (l, r) in a:
	print(l, r)


s = input()
len_s = len(s)
reversed_s = s[::-1]
t = input()
len_t = len(t)
res = 0
tracks = []
step = 0
while step < len_t:
	if t[step:step + 1] not in s:
		print(-1)
		exit()
	plus = 1
	while (t[step:step + plus] in s or t[step:step + plus] in reversed_s) and step + plus < len_t + 1:
		plus += 1
	if t[step:step + plus - 1] in s:
		x = s.find(t[step:step + plus - 1])
		tracks.append((x + 1, x + plus - 1))
	else:
		x = reversed_s.find(t[step:step + plus - 1])
		tracks.append((len_s - x, len_s - x - plus + 2))
	res += 1
	step += plus - 1
print(res)
for (a, b) in tracks:
	print(a, b)


s = input()
t = input()
rs = s[::-1]
a = t[0]
t += '.'
li = []
for i in range(1, len(t)):
	b = a + t[i]
	if b in s or b in rs:
		a = b
	else:
		if a in s:
			li.append([s.find(a) + 1, s.find(a) + len(a)])
		elif a in rs:
			li.append([len(s) - rs.find(a), len(s) - rs.find(a) - len(a) + 1])
		else:
			(print(-1), exit(0))
		a = t[i]
print(len(li))
for i in li:
	print(i[0], i[1])


(a, t) = (input(), input() + ' ')
b = a[::-1]
(s, p) = ('', [])
for q in t:
	d = s
	s += q
	if s in a or s in b:
		continue
	if d in a:
		k = a.find(d)
		p += [(k + 1, k + len(d))]
	elif d in b:
		k = b.rfind(d)
		p += [(len(a) - k, len(a) - k - len(d) + 1)]
	else:
		print(-1)
		exit()
	s = q
print(len(p))
for (i, j) in p:
	print(i, j)


s = input()
t = input() + '.'
(rs, a, res) = (s[::-1], t[0], [])
for i in range(1, len(t)):
	b = a + t[i]
	if b in s or b in rs:
		a = b
		continue
	if a in s:
		x = s.find(a)
		res.append([x + 1, x + len(a)])
	elif a in rs:
		x = rs.find(a)
		res.append([len(s) - x, len(s) - x - len(a) + 1])
	else:
		print(-1)
		exit()
	a = t[i]
print(len(res))
for i in res:
	print(i[0], i[1])


from bisect import bisect_left
from functools import cmp_to_key

def mp():
	return map(int, input().split())

def lt():
	return list(map(int, input().split()))

def pt(x):
	print(x)

def ip():
	return input()

def it():
	return int(input())

def sl(x):
	return [t for t in x]

def spl(x):
	return x.split()

def aj(liste, item):
	liste.append(item)

def bin(x):
	return '{0:b}'.format(x)

def printlist(l):
	print(''.join([str(x) for x in l]))

def listring(l):
	return ''.join([str(x) for x in l])
s = input()
t = input()
s_rev = s[::-1]

def check(st, substr):
	index = 0
	if substr in st:
		c = substr[0]
		while index < len(st) - len(substr) + 1:
			if st[index] == c:
				if st[index:index + len(substr)] == substr:
					return index
			index += 1
	return -1
pos = 0
L = []
while pos < len(t):
	substr = t[pos:pos + 1]
	if substr not in s and substr not in s_rev:
		print(-1)
		exit()
	index = 1
	while t[pos:pos + index] in s or t[pos:pos + index] in s_rev:
		index += 1
		if pos + index > len(t):
			break
	index -= 1
	substr = t[pos:pos + index]
	if check(s, substr) == -1:
		start = len(s) - 1 - check(s_rev, substr)
		end = start - index + 1
	else:
		start = check(s, substr)
		end = start + index - 1
	L.append((start + 1, end + 1))
	pos += index
print(len(L))
for i in L:
	print('%d %d' % (i[0], i[1]))


s = input()
t = input()
len_s = len(s)
reversed_s = s[::-1]
len_t = len(t)
res = 0
pairs = []
indx = 0
while indx < len_t:
	if t[indx:indx + 1] not in s:
		print(-1)
		exit()
	i = 1
	while (t[indx:indx + i] in s or t[indx:indx + i] in reversed_s) and indx + i < len_t + 1:
		i += 1
	prev_i = i - 1
	if t[indx:indx + prev_i] in s:
		x = s.find(t[indx:indx + prev_i])
		pairs.append((x + 1, x + prev_i))
	else:
		x = reversed_s.find(t[indx:indx + prev_i])
		pairs.append((len_s - x, len_s - x - i + 2))
	res += 1
	indx += prev_i
print(res)
for (a, b) in pairs:
	print(a, b)


def solve(s, t):
	hash_s = [False] * 256
	hash_t = [False] * 256
	arr = []
	n = len(s)
	for c in s:
		hash_s[ord(c)] = True
	for c in t:
		hash_t[ord(c)] = True
	for i in range(256):
		if not hash_s[i] and hash_t[i]:
			print(-1)
			return
	rev = s[::-1]
	(i, j) = (0, 0)
	while i < len(t):
		flag = True
		temp = t[i]
		j = i + 1
		while j < len(t):
			temp += t[j]
			if temp not in s and temp not in rev:
				flag = False
				break
			j += 1
		if flag:
			x = s.find(temp)
			if x != -1:
				arr.append((x + 1, x + len(temp)))
			else:
				y = rev.find(temp)
				arr.append((n - y, n - y - len(temp) + 1))
		else:
			x = s.find(temp[:-1])
			if x != -1:
				arr.append((x + 1, x + len(temp) - 1))
			else:
				x = rev.find(temp[:-1])
				arr.append((n - x, n - x - len(temp) + 2))
		i = j
	print(len(arr))
	for (x, y) in arr:
		print(x, y)
s = input()
t = input()
solve(s, t)