Let’s define a grid to be a set of tiles with 2 rows and 13 columns. Each tile has an English letter written in it. The letters don't have to be unique: there might be two or more tiles with the same letter written on them. Here is an example of a grid: ABCDEFGHIJKLM

NOPQRSTUVWXYZ 

We say that two tiles are adjacent if they share a side or a corner. In the example grid above, the tile with the letter 'A' is adjacent only to the tiles with letters 'B', 'N', and 'O'. A tile is not adjacent to itself.

A sequence of tiles is called a path if each tile in the sequence is adjacent to the tile which follows it (except for the last tile in the sequence, which of course has no successor). In this example, "ABC" is a path, and so is "KXWIHIJK". "MAB" is not a path because 'M' is not adjacent to 'A'. A single tile can be used more than once by a path (though the tile cannot occupy two consecutive places in the path because no tile is adjacent to itself).

You’re given a string s which consists of 27 upper-case English letters. Each English letter occurs at least once in s. Find a grid that contains a path whose tiles, viewed in the order that the path visits them, form the string s. If there’s no solution, print "Impossible" (without the quotes).


-----Input-----

The only line of the input contains the string s, consisting of 27 upper-case English letters. Each English letter occurs at least once in s.


-----Output-----

Output two lines, each consisting of 13 upper-case English characters, representing the rows of the grid. If there are multiple solutions, print any of them. If there is no solution print "Impossible".


-----Examples-----
Input
ABCDEFGHIJKLMNOPQRSGTUVWXYZ

Output
YXWVUTGHIJKLM
ZABCDEFSRQPON

Input
BUVTYZFQSNRIWOXXGJLKACPEMDH

Output
Impossible

Difficulty: MEDIUM_HARD
Tags: String algorithms

Complete search

Implementation

Constructive algorithms
Skill types: Complete search

Starter code:

Solutions:
3
s = input()
n = len(s)
(a, b) = (0, 0)
d = dict()
for i in range(len(s)):
	if s[i] in d:
		a = d[s[i]]
		b = i
	d[s[i]] = i
if a == b - 1:
	print('Impossible')
else:
	ans = [[' '] * 13 for i in range(2)]
	if (b - a) % 2 == 1:
		for i in range((b - a) // 2):
			ans[0][-(b - a) // 2 + i + 1] = s[a + i + 1]
			ans[1][-i - 1] = s[a + i + (b - a) // 2 + 1]
		x = -(b - a) // 2
		y = 0
		for i in range(b, n):
			ans[y][x] = s[i]
			if y == 0:
				x -= 1
			else:
				x += 1
			if x == -14:
				y = 1
				x = 0
		for i in range(a):
			ans[y][x] = s[i]
			if y == 0:
				x -= 1
			else:
				x += 1
			if x == -14:
				y = 1
				x = 0
		print(''.join(ans[0]))
		print(''.join(ans[1]))
	else:
		for i in range((b - a) // 2):
			ans[0][-(b - a) // 2 + i + 1] = s[a + i + 1]
			ans[1][-i - 1] = s[a + i + (b - a) // 2]
		x = -(b - a) // 2
		y = 0
		for i in range(b, n):
			ans[y][x] = s[i]
			if y == 0:
				x -= 1
			else:
				x += 1
			if x == -14:
				y = 1
				x = 0
		for i in range(a):
			ans[y][x] = s[i]
			if y == 0:
				x -= 1
			else:
				x += 1
			if x == -14:
				y = 1
				x = 0
		print(''.join(ans[0]))
		print(''.join(ans[1]))


from collections import *
S = list(input())
D = defaultdict(list)
for i in range(27):
	D[S[i]].append(i)
ok = False
for (k, v) in D.items():
	if v[-1] - v[0] > 1:
		l = v[-1] - v[0]
		del S[v[-1]]
		A = [' '] * 13
		B = [' '] * 13
		for i in range(0, 13):
			A[i] = S[(-i + v[0] + (l - 1) // 2) % 26]
		for i in range(0, 13):
			B[i] = S[(v[0] + (l - 1) // 2 + 1 + i) % 26]
		print(''.join(A))
		print(''.join(B))
		ok = True
		break
if not ok:
	print('Impossible')


def lanjut(last):
	if last[0] == 1:
		if last[1] == 0:
			last[0] = 0
		else:
			last[1] -= 1
	elif last[1] == 12:
		last[0] = 1
	else:
		last[1] += 1
hasil = []
hasil.append(list(13 * '1'))
hasil.append(list(13 * '1'))
s = input()
pos1 = -1
pos2 = -1
for i in range(ord('A'), ord('Z') + 1):
	if s.count(chr(i)) == 2:
		pos1 = s.index(chr(i))
		pos2 = s[pos1 + 1:].index(chr(i)) + pos1 + 1
		break
if pos1 + 1 == pos2:
	print('Impossible')
else:
	kiri = pos1
	kanan = 26 - pos2
	panjang = pos2 - pos1 - 1
	pos = (panjang + 2) // 2
	hasil[0][13 - pos] = s[pos1]
	sekarang = [0, 13 - pos]
	for i in range(panjang):
		lanjut(sekarang)
		hasil[sekarang[0]][sekarang[1]] = s[pos1 + i + 1]
	for i in range(kanan):
		lanjut(sekarang)
		hasil[sekarang[0]][sekarang[1]] = s[pos2 + i + 1]
	for i in range(kiri):
		lanjut(sekarang)
		hasil[sekarang[0]][sekarang[1]] = s[i]
	for i in range(2):
		for j in range(13):
			print(hasil[i][j], end='')
		print()


s = input()
cnt = dict()
f = 0
for elem in s:
	if elem in cnt:
		cnt[elem].append(f)
	else:
		cnt[elem] = [f]
	f += 1
t = sorted([(len(cnt[elem]), cnt[elem], elem) for elem in cnt])[-1]
if t[1][1] - t[1][0] == 1:
	print('Impossible')
near = [list()] * 26
near[0] = [1, 24, 25]
for i in range(1, 12):
	near[i] = [i - 1, i + 1, 26 - i, 25 - i, 24 - i]
near[12] = [11, 13, 14]
near[13] = [11, 12, 14]
for i in range(14, 25):
	near[i] = [i - 1, i + 1, 26 - i, 25 - i, 24 - i]
near[25] = [0, 1, 24]
second = t[1][1]
s1 = ''
for i in range(27):
	if i != second:
		s1 += s[i]
for i in range(26):
	t = s1.find(s[0])
	pos = 0
	while pos != 26:
		A = near[t]
		letters = [(s1[elem], elem) for elem in A]
		hop = -1
		for elem in letters:
			if elem[0] == s[pos + 1]:
				hop = elem[1]
				break
		if hop == -1:
			break
		else:
			t = hop
			pos += 1
	if pos == 26:
		print(s1[:13])
		print(s1[13:][::-1])
		break
	s1 = s1[-1] + s1[:-1]


import math
import collections

def make_grid(p0, s_uniq):
	s_uniq = list(s_uniq)
	grid = [list(range(13)) for _ in range(2)]
	if p0 >= 0:
		grid[0][p0:] = s_uniq[:13 - p0]
		grid[1] = list(reversed(s_uniq[13 - p0:13 - p0 + 13]))
		grid[0][:p0] = s_uniq[13 - p0 + 13:]
	else:
		grid[1][:-p0] = list(reversed(s_uniq[:-p0]))
		grid[0] = s_uniq[-p0:-p0 + 13]
		grid[1][-p0:] = list(reversed(s_uniq[-p0 + 13:]))
	return grid
s = input()
poses = collections.defaultdict(list)
for (i, c) in enumerate(s):
	poses[c].append(i)
for c in poses:
	if len(poses[c]) > 1 and poses[c][1] - poses[c][0] > 1:
		i = poses[c][0]
		j = poses[c][1]
		s_uniq = s[:j] + s[j + 1:]
		ans = make_grid(math.floor((26 - i - j) / 2), s_uniq)
		print(''.join(ans[0]))
		print(''.join(ans[1]))
		raise SystemExit
print('Impossible')


s = input()
arr = [0] * 26
for i in s:
	arr[ord(i) - 65] += 1
l = chr(arr.index(2) + 65)
a = s.find(l)
b = s.rfind(l)
ans = b - a - 1
x = 27 + a + ans // 2
if ans == 0:
	print('Impossible')
else:
	s = 3 * s
	print(s[x - 12:x + 1])
	s1 = s[x + 1:x + 15][::-1]
	s1 = s1[:s1.find(l)] + s1[s1.find(l) + 1:]
	print(s1)


s = input()
m = dict()
c = '?'
for i in range(27):
	if s[i] in m:
		left = m[s[i]]
		right = i
		c = s[i]
	else:
		m[s[i]] = i
mid = right - left - 1
if mid == 0:
	print('Impossible')
	exit()
a = [['?', '?'] for i in range(13)]
if mid % 2 == 1:
	a[mid // 2][0] = c
	cur = mid // 2 - 1
	for i in range(left + 1, left + mid // 2 + 1):
		a[cur][0] = s[i]
		cur -= 1
	cur = 0
	for i in range(left + mid // 2 + 1, right):
		a[cur][1] = s[i]
		cur += 1
	cur = mid // 2 + 1
	zn = 0
	for i in range(left - 1, -1, -1):
		if cur == 13:
			cur -= 1
			zn = 1
		a[cur][1 - zn] = s[i]
		if zn == 0:
			cur += 1
		else:
			cur -= 1
	cur = mid // 2 + 1
	zn = 0
	for i in range(right + 1, 27):
		if cur == 13:
			cur -= 1
			zn = 1
		a[cur][zn] = s[i]
		if zn == 0:
			cur += 1
		else:
			cur -= 1
else:
	a[mid // 2][0] = c
	cur = mid // 2 - 1
	for i in range(left + 1, left + mid // 2 + 1):
		a[cur][0] = s[i]
		cur -= 1
	cur = 0
	for i in range(left + mid // 2 + 1, right):
		a[cur][1] = s[i]
		cur += 1
	cur = mid // 2
	zn = 0
	for i in range(left - 1, -1, -1):
		if cur == 13:
			cur -= 1
			zn = 1
		a[cur][1 - zn] = s[i]
		if zn == 0:
			cur += 1
		else:
			cur -= 1
	cur = mid // 2 + 1
	zn = 0
	for i in range(right + 1, 27):
		if cur == 13:
			cur -= 1
			zn = 1
		a[cur][zn] = s[i]
		if zn == 0:
			cur += 1
		else:
			cur -= 1
for i in range(13):
	print(a[i][0], end='')
print()
for i in range(13):
	print(a[i][1], end='')


s = input()
a = []
for i in range(27):
	if s[i] in a:
		letter = s[i]
		break
	a.append(s[i])
p1 = s.find(letter)
p2 = s.rfind(letter)
if p1 + 1 == p2:
	print('Impossible')
else:
	str1 = ''
	str2 = ''
	dist = p2 - p1
	if dist % 2:
		new_s = s[p2 + 1:] + s[:p1]
		len1 = 13 - dist // 2
		len2 = 13 - dist // 2 + 1
		str1 = new_s[:len1 - 1][::-1]
		str2 = new_s[len1 - 1:]
		str1 += s[p1:p1 + dist // 2 + 1]
		str2 += s[p1 + dist // 2 + 1:p2][::-1]
		print(str1)
		print(str2)
	else:
		new_s = s[p2 + 1:] + s[:p1]
		lenn = 13 - dist // 2
		str1 = new_s[:lenn][::-1]
		str2 = new_s[lenn:]
		str1 += s[p1 + 1:p1 + dist // 2 + 1]
		str2 += letter + s[p1 + dist // 2 + 1:p2][::-1]
		print(str1)
		print(str2)


def main():
	s = input()
	poss = {}
	lst = [[' '] * 13]
	lst.append([' '] * 13)
	for i in range(27):
		if s[i] in poss:
			poss[s[i]].append(i)
			D = s[i]
		else:
			poss[s[i]] = [i]
	loop1 = s[poss[D][0]:poss[D][1]]
	if len(loop1) <= 1:
		print('Impossible')
		return False
	p = -len(loop1) // 2
	inc = 1
	row = 0
	for c in loop1:
		lst[row][p] = c
		if p == -1 and row == 0:
			inc = -1
			row = 1
		else:
			p += inc
	loop2 = s[poss[D][1] + 1:] + s[:poss[D][0]]
	p = 13 + -len(loop1) // 2
	inc = -1
	row = 0
	for c in loop2:
		if p == 0 and row == 0:
			inc = 1
			row = 1
		else:
			p += inc
		lst[row][p] = c
	print(''.join(lst[0]))
	print(''.join(lst[1]))
main()


s = input().strip()
length = 27
d = {}
(firsti, secondi) = (-1, -1)
for i in range(length):
	if s[i] in d:
		firsti = d[s[i]]
		secondi = i
		break
	d[s[i]] = i
if secondi - firsti > 1:
	table = [[0] * 13, [0] * 13]
	blen = secondi - firsti
	midindx = 13 - (blen // 2 + blen % 2)
	for i in range(blen // 2 + blen % 2):
		table[0][midindx + i] = s[firsti + i]
	tmpindx = firsti + (blen // 2 + blen % 2)
	for i in range(blen // 2):
		table[1][12 - i] = s[tmpindx + i]
	clen = 26 - secondi
	alen = firsti
	curindx = -1
	curlen = 0
	step = -1
	if clen > alen:
		curindx = secondi + 1
		curlen = clen
		step = 1
	else:
		curindx = firsti - 1
		curlen = alen
		step = -1
	direction = -1
	indx1 = 1
	indx2 = midindx - 1 + blen % 2
	while curindx >= 0 and curindx < 27 and (indx2 >= 0) and (indx2 < 13):
		table[indx1][indx2] = s[curindx]
		curindx += step
		if indx2 == 0 and direction == -1:
			direction = 1
		else:
			indx2 += direction
		indx1 = (indx1 + 1) % 2
	if clen > alen:
		curindx = firsti - 1
		curlen = alen
		step = -1
	else:
		curindx = secondi + 1
		curlen = clen
		step = 1
	direction = -1
	indx1 = blen % 2
	indx2 = midindx - 1
	while curindx >= 0 and curindx < 27 and (indx2 >= 0) and (indx2 < 13):
		table[indx1][indx2] = s[curindx]
		curindx += step
		if indx2 == 0 and direction == -1:
			direction = 1
		else:
			indx2 += direction
		indx1 = (indx1 + 1) % 2
	print(''.join(table[0]))
	print(''.join(table[1]))
else:
	print('Impossible')


s = input()
n = len(s)
(left, right) = (-1, -1)
for i in range(n):
	j = s[i + 1:].find(s[i])
	if j == -1:
		continue
	left = i
	right = i + 1 + j
	break
if left == right - 1:
	print('Impossible')
else:
	a = left
	b = n - right - 1
	d = n - 2 - a - b
	if a > b:
		(left, right) = (n - 1 - right, n - 1 - left)
		(a, b) = (b, a)
		s = s[::-1]
	b1 = right + (a + b + 1) // 2 + 1
	b2 = left + d // 2 + 1
	print(s[b1:] + s[:b2])
	print((s[b2:right] + s[right + 1:b1])[::-1])


import sys
debug = False

def print_debug(*args, **kwargs):
	if debug:
		print(*args, **kwargs, file=sys.stderr)
s = input()
double = ''
for c in range(ord('A'), ord('Z') + 1):
	if s.count(chr(c)) == 2:
		double = chr(c)
(i1, i2) = [i for (i, c) in enumerate(s) if c == double]
print_debug(double, i1, i2)
if abs(i1 - i2) == 1:
	print('Impossible')
	sys.exit(0)
for shift in range(0, 26):
	(i1, i2) = [i for (i, c) in enumerate(s) if c == double]
	s2 = s[:i1] + s[i1 + 1:]
	i1 -= 1
	print_debug(s2)
	i2 = [i for (i, c) in enumerate(s2) if c == double][0]
	print_debug(i2)
	i2 = 25 - i2
	print_debug(i2)
	if i2 - 1 <= i1 <= i2:
		print(s2[:13])
		print(s2[13:][::-1])
		sys.exit(0)
	s = s[1:] + s[:1]
print('Impossible')


from sys import stdin, stdout
import sys
import random
import datetime
DEBUG = True
endl = '\n'

class Scan:

	def __init__(self):
		self.read = stdin.read
		self.input = stdin.readline

	def integer(self, count=1):
		if count == 1:
			return self._integer()
		return [self._integer() for _ in range(count)]

	def _integer(self):
		sym: str = self.read(1)
		while sym != '-' and (not sym.isdigit()):
			sym = self.read(1)
		(number, sign) = (0, -1) if sym == '-' else (int(sym), 1)
		sym: str = self.read(1)
		while sym.isdigit():
			number = number * 10 + int(sym)
			sym = self.read(1)
		return number * sign

	def array(self, func=int, sep=' '):
		if func == str:
			return input().split(sep)
		return list(map(func, input().split(sep)))

	def string(self, count=1):
		if count == 1:
			return self._string()
		return [self._string() for _ in range(count)]

	def _string(self):
		sym = self.read(1)
		while sym in ('\n', '\r', ' '):
			sym = self.read(1)
		s = str()
		while sym not in ('\n', '\r', ' '):
			s += sym
			sym = self.read(1)
		return s

class Write:

	def __lshift__(self, other):
		stdout.write(str(other))

class Number:

	def gcd(a, b):
		while b > 0:
			(a, b) = (b, a % b)
		return a

	def lcm(a, b):
		return a * b // gcd(a, b)

	def sqrt(n):
		sqrt_n = int(n ** 0.5)
		while sqrt_n * sqrt_n < n:
			sqrt_n += 1
		while sqrt_n * sqrt_n > n:
			sqrt_n -= 1
		return sqrt_n

	def sum_n(n):
		return n * (n + 1) // 2

class Constants:
	EPS = 10 ** (-9)
	INF = 10 ** 18
	MOD = 10 ** 9 + 7

def solution(scan: Scan, write: Write):
	s = scan.string()
	s1 = str()
	s2 = str()
	c = str()
	for i in range(len(s)):
		ind = s.find(s[i], i + 1)
		if ind != -1:
			c = s[i]
			s1 = s[i + 1:ind]
			s2 = s[ind + 1:] + s[:i]
	if not s1:
		print('Impossible')
		return
	if len(s1) % 2 == 0:
		(s1, s2) = (s2, s1)
	ans1 = str()
	ans2 = str()
	ans1 = s1[:len(s1) // 2][::-1] + c
	ans2 = s1[len(s1) // 2:]
	ans1 += s2[:len(s2) // 2]
	ans2 += s2[len(s2) // 2:][::-1]
	print(ans1)
	print(ans2)

def main():
	queries: int = 1
	(scan, write) = (Scan(), Write())
	for _ in range(queries):
		solution(scan, write)
main()


s = input()
s1 = s
our = dict()
f = ''
for i in s:
	our[i] = our.get(i, 0) + 1
	if our[i] == 2:
		f = i
i1 = s.find(f)
i2 = s.rfind(f)
if abs(i1 - i2) == 1:
	print('Impossible')
l = [list()] * 26
l[0] = [1, 24, 25]
l[12] = [11, 13, 14]
l[13] = [11, 12, 14]
l[25] = [0, 1, 24]
for i in range(1, 25):
	if i not in (12, 13):
		l[i] = [i - 1, i + 1, 24 - i, 25 - i, 26 - i]
s = s[:i2] + s[i2 + 1:]
for i in range(26):
	id1 = s.find(s1[0])
	id2 = 0
	while id2 != 26:
		can = l[id1]
		p = [(s[i], i) for i in can]
		flag = -1
		for i in p:
			if i[0] == s1[id2 + 1]:
				flag = i[1]
				break
		if flag == -1:
			break
		else:
			id2 += 1
			id1 = flag
	if id2 == 26:
		print(s[:13])
		print(s[13:][::-1])
		break
	s = s[-1] + s[:-1]


a = input()
for i in range(1, 27):
	if a[i] == a[i - 1]:
		print('Impossible')
		break
else:
	b = [[] for i in range(26)]
	for i in range(27):
		b['ABCDEFGHIJKLMNOPQRSTUVWXYZ'.find(a[i])].append(i)
	c = [[' ' for i in range(13)] for j in range(2)]
	j = 0
	for i in range(26):
		if len(b[i]) == 2:
			j = i
			break
	d = b[j][1] - b[j][0]
	c[0][13 - d // 2 - d % 2] = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'[j]
	for i in range(14 - d // 2 - d % 2, 13):
		c[0][i] = a[b[j][0] + i - 13 + d // 2 + d % 2]
	y = 0
	k = 27
	for i in range(b[j][0] + d // 2 + d % 2, 27):
		if i == b[j][1]:
			y = 1
		else:
			if -1 - i + b[j][0] + d // 2 + d % 2 + y < -13:
				k = i
				break
			c[1][-1 - i + b[j][0] + d // 2 + d % 2 + y] = a[i]
	for i in range(k, 27):
		c[0][i - k] = a[i]
	for i in range(-13 + b[j][0] + d // 2 + d % 2):
		c[1][-27 - i + b[j][0] + d // 2 + d % 2] = a[i]
	for i in range(13 - d // 2 - d % 2):
		c[0][i] = a[-13 + b[j][0] + d // 2 + d % 2 + i]
	print(*c[0], sep='')
	print(*c[1], sep='')


s = input()
gx = None
for i in range(26):
	x = chr(ord('A') + i)
	if s.count(x) == 2:
		gx = x
x = gx
sz = s.rindex(x) - s.index(x) - 1
ss = s[s.index(x) + 1:s.rindex(x)]
if sz == 0:
	print('Impossible')
else:
	cols = sz // 2
	ans = [[None for _ in range(13)], [None for _ in range(13)]]
	st = 0
	for i in range(cols - 1, -1, -1):
		ans[0][st] = ss[i]
		ans[1][st] = ss[sz - i - 1]
		st += 1
	ans[0][cols] = gx
	if sz & 1:
		ans[1] = [ss[cols]] + ans[1][:-1]
	w = 0
	idx = cols + 1
	for c in s[:s.index(x)][::-1]:
		if idx == 13:
			idx = 12
			w = 1
		if w == 0:
			ans[0][idx] = c
			idx += 1
		else:
			ans[1][idx] = c
			idx -= 1
	w = 0
	idx = cols if sz % 2 == 0 else cols + 1
	for c in s[s.rindex(x) + 1:]:
		if idx == 13:
			idx = 12
			w = 1
		if w == 0:
			ans[1][idx] = c
			idx += 1
		else:
			ans[0][idx] = c
			idx -= 1
	print(''.join(ans[0]))
	print(''.join(ans[1]))


s = input()
for c in s:
	if s.count(c) == 2:
		break
i = s.index(c)
j = i + 1 + s[i + 1:].index(c)
if i + 1 == j:
	print('Impossible')
	exit(0)
s = s.replace(c, '', 1) * 3
mid = 13 + (i + j) // 2
print(s[mid - 13:mid])
print(s[mid:mid + 13][::-1])


def is_path_in(G, s):
	(cur_x, cur_y) = (-1, -1)
	for y in range(2):
		for x in range(13):
			if G[y][x] == s[0]:
				(cur_y, cur_x) = (y, x)
	if cur_x == -1:
		return False
	for c in s[1:]:
		for d in range(8):
			(nx, ny) = (cur_x + dx[d], cur_y + dy[d])
			if nx < 0 or nx > 12 or ny < 0 or (ny > 1):
				continue
			if G[ny][nx] == c:
				(cur_x, cur_y) = (nx, ny)
				break
		else:
			return False
	return True
s = input()
for (i, a) in enumerate(s):
	if s.count(a) > 1:
		T = s[:i] + s[i + 1:]
		break
dy = [-1, -1, -1, 0, 0, 1, 1, 1]
dx = [-1, 0, 1, -1, 1, -1, 0, 1]
for i in range(26):
	G = [T[:13], T[13:][::-1]]
	if is_path_in(G, s):
		print(G[0])
		print(G[1])
		break
	T = T[1:] + T[0]
else:
	print('Impossible')


(l, d) = ([], {})
for (i, c) in enumerate(input()):
	if c in d:
		(u, v) = ((d[c] + i + 1) // 2, i)
	else:
		l.append(c)
	d[c] = i
s = ''.join(l * 2)
print(s[u:u + 13] + '\n' + s[u + 25:u + 12:-1] if u < v else 'Impossible')


s = str(input())
A = [[] for _ in range(26)]
Al = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
i = 0
while i < 27:
	A[Al.index(s[i])] += [i]
	i += 1
T = [len(A[i]) for i in range(26)]
ok = 0
for i in range(26):
	if T[i] > 1:
		for k in range(T[i] - 1):
			for l in range(k + 1, T[i]):
				if abs(A[i][k] - A[i][l]) - 1 > 0:
					ok = 1
					k1 = A[i][k]
					l1 = A[i][l]
					break
			if ok == 1:
				break
	if ok == 1:
		break
if ok == 0:
	print('Impossible')
else:
	R1 = ['' for _ in range(13)]
	R2 = ['' for _ in range(13)]
	d = 1 + (abs(l1 - k1) - 2) // 2
	debut = 13 - d - k1
	if debut >= 0:
		for i in range(k1):
			R1[debut + i] = s[i]
		for i in range(debut):
			R1[i] = s[27 - debut + i]
		for i in range(k1, 13 - debut):
			R1[debut + i] = s[i + 1]
		for i in range(13):
			R2[12 - i] = s[14 + i - debut]
	else:
		for i in range(-debut, k1):
			R1[i + debut] = s[i]
		for i in range(k1, 13 - debut):
			R1[i + debut] = s[i + 1]
		for i in range(13 + debut):
			R2[12 - i] = s[-debut + i + 14]
		for i in range(-debut):
			R2[i] = s[-debut - i - 1]
	for i in range(13):
		print(R1[i], end='')
	print()
	for j in range(13):
		print(R2[j], end='')


(l, d) = ([], {})
for (i, c) in enumerate(input()):
	if c in d:
		(d1, len) = (d[c], (i - d[c] - 1) // 2 + 1)
		d2 = i
	else:
		l.append(c)
	d[c] = i
s = ''.join(l * 2)
if d2 - d1 <= 1:
	print('Impossible')
else:
	print(s[d1 + 26 - 13 + len:d1 + 26] + s[d1:d1 + len] + '\n' + s[d1 + len:d1 + len + 13][::-1])


def solve(s):
	for i0 in range(27):
		for i1 in range(i0 + 1, 27):
			if s[i0] == s[i1]:
				break
		if s[i0] == s[i1]:
			break
	assert s[i0] == s[i1]
	d = i1 - i0
	if d == 1:
		return 'Impossible'
	res = [None] * 26

	def set(idx, ch):
		nonlocal res
		res[(idx + 26) % 26] = ch

	def copy(start_idx):
		for (idx, ch) in enumerate(s[:i1] + s[i1 + 1:]):
			set(start_idx + idx, ch)
	off = d // 2 - 1 + d % 2
	copy(12 - off - i0)
	assert None not in res
	return ''.join(res[:13]) + '\n' + ''.join(reversed(res[13:]))
s = input()
print(solve(s))


import sys
s = input()
n = 27
alphabet = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
pos = [-1] * 26
first = 0
second = 0
for i in range(n):
	x = alphabet.index(s[i])
	if pos[x] != -1:
		second = i
		first = pos[x]
		break
	pos[x] = i
if second - first == 1:
	print('Impossible')
	sys.exit()
middle = (first + second) // 2 + (first - second) % 2
s = s[0:second] + s[second + 1:27]
s *= 2
if middle < 13:
	middle += 13
a1 = s[middle - 13:middle]
a2 = s[middle:middle + 13]
print(a1)
print(a2[::-1])


def main():
	(l, d) = ([], {})
	for (i, c) in enumerate(input()):
		if c in d:
			(u, v) = (d[c], i)
		else:
			d[c] = i
			l.append(c)
	if v - u == 1:
		print('Impossible')
		return
	l *= 2
	w = (u + v + 1) // 2
	print(''.join(l[w:w + 13]))
	print(''.join(l[w + 25:w + 12:-1]))
main()


def find_duplicate(s):
	for i in range(len(s)):
		for j in range(i + 1, len(s)):
			if s[i] == s[j]:
				return (i, j, s[i])

def main():
	s = input()
	(l, r, ch) = find_duplicate(s)
	if r - l == 1:
		print('Impossible')
		return
	ans = [['#' for i in range(13)] for j in range(2)]
	pos = 12 - (r - l - 1) // 2
	ans[0][pos] = ch
	in_cur = l + 1
	out_cur = pos + 1
	while out_cur < 13:
		ans[0][out_cur] = s[in_cur]
		in_cur += 1
		out_cur += 1
	out_cur = 12
	while in_cur < r:
		ans[1][out_cur] = s[in_cur]
		in_cur += 1
		out_cur -= 1
	in_cur += 1
	if in_cur >= len(s):
		in_cur = 0
	row = 1
	sign = -1
	while in_cur != l:
		ans[row][out_cur] = s[in_cur]
		in_cur += 1
		if in_cur >= len(s):
			in_cur = 0
		out_cur += sign
		if out_cur < 0:
			sign = 1
			out_cur = 0
			row = 0
	print(''.join(ans[0]))
	print(''.join(ans[1]))
main()


s = input()
seen_letters = set()
doubled_letter = None
for l in s:
	if l in seen_letters:
		doubled_letter = l
		break
	seen_letters.add(l)
indices = []
for (i, l) in enumerate(s):
	if l == doubled_letter:
		indices.append(i)
(idx_fst, idx_snd) = indices
delta = idx_snd - idx_fst - 1
grid = [['*' for _ in range(13)] for _ in [0, 1]]
if delta == 0:
	print('Impossible')
else:
	other_letters = s[idx_snd + 1:] + s[:idx_fst]
	if delta == 1:
		grid[1][13 - 2] = doubled_letter
		grid[1][13 - 1] = s[idx_fst + 1]
		(i, j) = (1, 13 - 2)
		for el in other_letters:
			if i == 1:
				if j == 0:
					i = 0
				else:
					j -= 1
			else:
				j += 1
			grid[i][j] = el
	else:
		pos = delta // 2
		grid[1][-pos - 1] = doubled_letter
		(i, j) = (1, 13 - pos - 1)
		for el in other_letters:
			if i == 1:
				if j == 0:
					i = 0
				else:
					j -= 1
			else:
				j += 1
			grid[i][j] = el
		(i, j) = (1, 13 - pos - 1)
		other_letters = s[idx_fst + 1:idx_snd]
		other_letters = reversed(other_letters)
		for el in other_letters:
			if i == 1:
				if j == 13 - 1:
					i = 0
				else:
					j += 1
			else:
				j -= 1
			grid[i][j] = el
	print(''.join(grid[0]))
	print(''.join(grid[1]))


from collections import Counter

def display(r1, r2):
	if len(r1) > 13:
		(r1, r2) = (r1[:13], r2 + r1[13:][::-1])
	elif len(r2) > 13:
		(r1, r2) = (r1 + r2[13:][::-1], r2[:13])
	print(r1)
	print(r2)

def main():
	s = input()
	counter = Counter(s)
	double = None
	for c in s:
		if counter[c] == 2:
			double = c
	a = s.index(double)
	b = s.index(double, a + 1)
	if a + 1 == b:
		print('Impossible')
		return
	grid = [['0' for _ in range(13)] for _ in range(2)]
	first = s[:a]
	second = s[b + 1:]
	middle_chunk = s[a + 1:b]
	mid_len = len(middle_chunk)
	if mid_len == 1:
		display(double + first[::-1], middle_chunk + second)
		return
	else:
		cols = mid_len // 2
		r1 = middle_chunk[:cols][::-1] + double + first[::-1]
		r2 = middle_chunk[cols:] + second
		display(r1, r2)
main()


def main():
	s = input()
	flag = False
	st = -1
	fn = -1
	for i in range(27):
		for j in range(i + 2, 27):
			if s[i] == s[j]:
				flag = True
				st = i
				fn = j
				break
	if not flag:
		print('Impossible')
		return
	s = s[st:] + s[:st]
	add = st
	fn -= st
	st = 0
	ans = [['%'] * 13 for i in range(2)]
	sx = -1
	sy = 1
	if fn % 2 == 0:
		st_ind = fn // 2 - 1
		for i in range(st_ind + 1):
			ans[0][st_ind - i] = s[i]
		for i in range(st_ind + 1):
			ans[1][i] = s[st_ind + 1 + i]
		sx = st_ind + 1
	else:
		st_ind = fn // 2
		for i in range(st_ind + 1):
			ans[0][st_ind - i] = s[i]
		for i in range(st_ind):
			ans[1][i] = s[st_ind + 1 + i]
		sx = st_ind
	for i in s[fn + 1:]:
		ans[sy][sx] = i
		if sy == 1:
			if sx == 12:
				sy -= 1
			else:
				sx += 1
		else:
			sx -= 1
	print(''.join(ans[0]))
	print(''.join(ans[1]))
main()


s = input()
(l, r) = (-1, -1)
for c in 'QWERTYUIOPLKJHGFDSAZXCVBNM':
	if s.count(c) == 2:
		(l, r) = (s.find(c), s.rfind(c))
		break
if r - l < 2:
	print('Impossible')
else:
	res = [['_'] * 13 for x in range(2)]
	(i, j) = (0, -1 - (r - l - 1) // 2)
	s = s[l:r] + s[r + 1:] + s[:l]
	for c in s:
		res[i][j] = c
		if i == 0 and j == -1 or (i == 1 and j == -13):
			i ^= 1
		else:
			j += 1 if i == 0 else -1
	for line in res:
		print(*line, sep='')


from collections import Counter
s = input()
cnt = Counter(s)
double = cnt.most_common(1)[0][0]
a = s.index(double)
b = len(s) - 1 - s[::-1].index(double)
if a + 1 == b:
	print('Impossible')
	exit(0)
x = s[:a]
y = s[a + 1:b]
z = s[b + 1:]
res = [y[:len(y) // 2], y[len(y) // 2:][::-1]]
res[0] = double + res[0]
x = z + x
while len(res[0]) < 13:
	res[0] = x[-1] + res[0]
	x = x[:-1]
res[1] = x[::-1] + res[1]
for line in res:
	print(line)


d = {}
di = {}
ct = 0
x = input()
bad = []
for i in x:
	if i not in d:
		ct += 1
		d[i] = ct
		di[ct] = i
	else:
		bad = [ct, d[i]]
if bad[0] == bad[1]:
	print('Impossible')
	quit()

def gen(x):
	bot = []
	for i in range(x + 13, x, -1):
		bot.append(i)
	top = []
	for i in range(x + 14, 27):
		top.append(i)
	for i in range(1, x + 1):
		top.append(i)
	return [top, bot]

def gen2(x):
	top = []
	bot = []
	for i in range(x - 1):
		top.append(2 * i + 1)
		bot.append(2 * i + 2)
	for i in range(2 * x - 1, x + 13):
		top.append(i)
		bot.append(2 * x + 25 - i)
	return [top, bot]
for i in range(1, 14):
	if bad[0] + bad[1] == 2 * i or bad[0] + bad[1] == 2 * i + 1:
		(a, b) = gen(i)
		for j in a:
			print(di[j], end='')
		print()
		for j in b:
			print(di[j], end='')
for i in range(2, 15):
	if bad[0] + bad[1] in [2 * i + 24, 2 * i + 25]:
		(a, b) = gen2(i)
		for j in a:
			print(di[j], end='')
		print()
		for j in b:
			print(di[j], end='')


from string import ascii_uppercase
import math
a = input()
map = {}
for c in ascii_uppercase:
	map[c] = 0
for c in a:
	map[c] = map[c] + 1
for c in a:
	if map[c] > 1:
		duplicate = c
		break
upper = ''
lower = ''
start_pos_dup = a.find(duplicate)
end_pos_dup = len(a) - 1 - a[::-1].find(duplicate)
if end_pos_dup - start_pos_dup - 1 == 0:
	print('Impossible')
else:
	upper = duplicate + a[start_pos_dup + 1:start_pos_dup + 1 + (end_pos_dup - start_pos_dup - 1) // 2]
	if len(a[0:start_pos_dup]) >= 13 - math.ceil((end_pos_dup - start_pos_dup - 1) / 2):
		lower = str(a[start_pos_dup - 13 + math.ceil((end_pos_dup - start_pos_dup - 1) / 2):start_pos_dup]) + str(a[start_pos_dup + 1 + (end_pos_dup - start_pos_dup - 1) // 2:end_pos_dup])[::-1]
	else:
		lower = str(a[0:start_pos_dup]) + str(a[start_pos_dup + 1 + (end_pos_dup - start_pos_dup - 1) // 2:end_pos_dup])[::-1]
	temp = 13 - len(upper)
	upper = str(a[end_pos_dup + 1:end_pos_dup + 1 + 13 - len(upper)])[::-1] + upper
	if len(a[end_pos_dup + 1:]) < temp:
		upper = a[0:temp - len(a[end_pos_dup + 1:])][::-1] + upper
	lower = str(a[end_pos_dup + 1 + temp:]) + lower
	print(upper)
	print(lower)


from collections import deque, defaultdict
s = input()

def check_string(a, b):
	for i in a:
		if i not in b:
			return False
	return True

class tiles:

	def __init__(self, a_string, interest_location):
		n = len(a_string)
		self.half_len = n // 2
		self.double_tile = [deque(a_string[:self.half_len]), deque(a_string[n - 1:self.half_len - 1:-1])]
		if interest_location < self.half_len:
			self.interest_i = 0
			self.interest_j = interest_location
		else:
			self.interest_i = 1
			self.interest_j = n - 1 - interest_location

	def shift(self):
		last_element_first = self.double_tile[0].pop()
		first_element_second = self.double_tile[1].popleft()
		self.double_tile[0].appendleft(first_element_second)
		self.double_tile[1].append(last_element_first)
		if self.interest_i == 0 and self.interest_j == self.half_len - 1:
			self.interest_i = 1
		elif self.interest_i == 1 and self.interest_j == 0:
			self.interest_i = 0
		elif self.interest_i == 0:
			self.interest_j += 1
		else:
			self.interest_j -= 1

	def find_neighbor(self):
		i = self.interest_i
		j = self.interest_j
		if j == 0:
			return self.double_tile[i][j + 1] + self.double_tile[(i + 1) % 2][j + 1] + self.double_tile[(i + 1) % 2][j]
		elif j == self.half_len - 1:
			return self.double_tile[i][j - 1] + self.double_tile[(i + 1) % 2][j - 1] + self.double_tile[(i + 1) % 2][j]
		else:
			return self.double_tile[i][j - 1] + self.double_tile[i][j + 1] + self.double_tile[(i + 1) % 2][j - 1] + self.double_tile[(i + 1) % 2][j + 1] + self.double_tile[(i + 1) % 2][j]

	def print_tiles(self):
		print_row = ['', '']
		for i in range(2):
			for j in range(self.half_len):
				print_row[i] += self.double_tile[i][j]
		for i in range(2):
			print(print_row[i])
n = len(s)
word_dict = defaultdict(int)
for i in s:
	word_dict[i] += 1
	if word_dict[i] == 2:
		interesting_char = i
		break
interesting_index = [i for i in range(n) if s[i] == interesting_char]
if interesting_index[1] - interesting_index[0] == 1:
	print('Impossible')
else:
	slimmer_s = s[:interesting_index[1]] + s[interesting_index[1] + 1:]
	interesting_neighbor = s[interesting_index[1] - 1]
	if interesting_index[1] < n - 1:
		interesting_neighbor += s[interesting_index[1] + 1]
	our_tiles = tiles(slimmer_s, interesting_index[0])
	while not check_string(interesting_neighbor, our_tiles.find_neighbor()):
		our_tiles.shift()
	our_tiles.print_tiles()


s = str(input())
l = list(s)
lr = l[::-1]
for i in range(27):
	if s[i] in l[:i]:
		c = s[i]
flag = True
for i in range(27):
	if s[i] == c and flag:
		a1 = i
		flag = False
	elif s[i] == c and flag == False:
		a2 = i
d = a2 - a1 - 1
if d == 0:
	print('Impossible')
	exit()
s1 = l[:a1 + d // 2 + 1]
s1 = l + s1
s2 = l[a1 + 1 + d // 2:a2]
s2 = s2[::-1]
s3 = l[a2 + 1:]
s3 = s3[::-1]
s2 = s3 + s2
s2 = lr + s2
print(''.join(s1[-13:]))
print(''.join(s2[-13:]))


P = print
S = input()
for i in range(26):
	if S.count(chr(i + 65)) == 2:
		x = chr(i + 65)
a = S.find(x)
b = S.rfind(x)
s = S[a + 1:b]
w = q = ''
if s == '':
	P('Impossible')
	exit()
while len(s) > 1:
	t = len(s) // 2 - 1
	q += s[t]
	w += s[t + 1]
	s = s[:t] + s[t + 2:]
q += s + S[:a][::-1]
w += x + S[b + 1:]
if len(q) > len(w):
	(q, w) = (w, q)
while len(q) < len(w):
	q += w[-1]
	w = w[:-1]
P(q + '\n' + w)


def fail():
	print('Impossible')
	exit()
s = input()
from collections import Counter
C = Counter()
for i in s:
	C[i] += 1
for i in C:
	if C[i] == 2:
		ch = i
		break
(X, Y) = (s.find(ch), s.rfind(ch))
(a, b, c) = (X, Y - X - 1, 26 - Y)
if b == 0:
	fail()
ans = [[''] * 13 for i in range(2)]
ind = 12 - b // 2
ans[0][ind] = ch
j = X + 1
for i in range(ind + 1, 13):
	ans[0][i] = s[j]
	j += 1
end = ind if b % 2 else ind + 1
for i in range(12, end - 1, -1):
	ans[1][i] = s[j]
	j += 1
(x, y) = (0, ind - 1)
if ind == 0:
	(x, y) = (1, 0)
for i in range(X - 1, -1, -1):
	ans[x][y] = s[i]
	if (x, y) == (0, 0):
		(x, y) = (1, 0)
	elif x == 1:
		y += 1
	else:
		y -= 1
(x, y) = (1, ind if b % 2 == 0 else ind - 1)
for i in range(Y + 1, 27):
	ans[x][y] = s[i]
	if (x, y) == (1, 0):
		(x, y) = (0, 0)
	elif x == 0:
		y += 1
	else:
		y -= 1
[print(''.join(i)) for i in ans]


import sys
s = input()
possible = False
d = {}
(l, r) = (-1, -1)
for i in range(len(s)):
	if not s[i] in d:
		d[s[i]] = []
	d[s[i]].append(i)
for (i, v) in d.items():
	if max(v) - min(v) > 1:
		(l, r) = (min(v), max(v))
		possible = True
if not possible:
	print('Impossible')
	sys.exit(0)
g = [['' for _ in range(13)] for _ in range(2)]
k = (r - l - 1) // 2
g[0][k] = s[l]
for i in range(1, k + 1):
	g[0][k - i] = s[l + i]
for i in range(r - l - k - 1):
	g[1][i] = s[l + k + i + 1]
h = s[:l][::-1] + s[r + 1:][::-1]
i = 0
while k + i + 1 < 13:
	g[0][k + i + 1] = h[i]
	i += 1
j = 12
while j >= 0 and g[1][j] == '':
	g[1][j] = h[i]
	i += 1
	j -= 1
print(''.join(g[0]))
print(''.join(g[1]))


s1 = ['' for j in range(13)]
s2 = ['' for j in range(13)]
s = input()
f = 0
for i in range(27):
	if f == 0 and s.count(s[i]) == 2:
		f = 1
		sp1 = i
	elif f == 1 and s[i] == s[sp1]:
		sp2 = i
		break
if sp2 - sp1 == 1:
	print('Impossible')
else:
	tp = 12 - (sp2 - sp1 - 1) // 2
	for i in range(27):
		if i <= sp1:
			if sp1 - i <= tp:
				s1[tp - sp1 + i] = s[i]
			elif sp1 - i - tp - 1 <= 12:
				s2[sp1 - i - tp - 1] = s[i]
			else:
				s1[25 - (sp1 - i - tp - 1)] = s[i]
		else:
			if i == sp2:
				continue
			elif i < sp2:
				j = i
			else:
				j = i - 1
			if tp + (j - sp1) <= 12:
				s1[tp + (j - sp1)] = s[i]
			elif 25 - (tp + (j - sp1)) <= 12 and 25 - (tp + (j - sp1)) >= 0:
				s2[25 - (tp + (j - sp1))] = s[i]
			else:
				s1[abs(26 - (tp + (j - sp1)))] = s[i]
	print(''.join(s1))
	print(''.join(s2))


s = input()
for i in range(65, 91):
	if s.index(chr(i)) != s.rindex(chr(i)):
		k = chr(i)
		l = s.index(chr(i))
		r = s.rindex(chr(i))
if r - l == 1:
	print('Impossible')
else:
	p = s[:l]
	q = s[l + 1:r]
	t = s[r + 1:]
	s1 = ''
	s2 = ''
	s1 += q[:len(q) // 2][::-1] + k
	s2 += q[len(q) // 2:]
	if len(p) <= 13 - len(s1):
		s1 += p[::-1]
		d = 13 - len(s1)
		if d > 0:
			s1 += t[-d:][::-1]
			s2 += t[:-d]
		else:
			s2 += t
	else:
		s2 += t
		d = 13 - len(s2)
		if d > 0:
			s2 += p[:d]
			s1 += p[d:][::-1]
		else:
			s1 += p[::-1]
	print(s1, s2, sep='\n')


s = input().strip()
pos = [[] for i in range(26)]
for i in range(len(s)):
	pos[ord(s[i]) - ord('A')].append(i)
p = -1
for i in range(26):
	if pos[i][-1] - pos[i][0] > 1:
		p = i
		break
else:
	print('Impossible')
	exit(0)
a = pos[p][0]
b = pos[p][-1]
pos[p] = pos[p][1:-1]
res = ['', '']
inner = s[a + 1:b]
di = len(inner)
outer = s[b + 1:] + s[:a]
res[0] = res[0] + inner[:len(inner) // 2][::-1] + s[a]
res[1] = res[1] + inner[len(inner) // 2:]
x = len(res[0])
res[0] = res[0] + outer[:13 - x]
res[1] = res[1] + outer[13 - x:][::-1]
print(res[0])
print(res[1])


s = input()
from collections import Counter
cnt = Counter(s)
sc = sorted(cnt.items(), key=lambda x: x[1], reverse=True)[0][0]
s = s[s.index(sc):] + s[:s.index(sc)]
if s[0] == s[1]:
	print('Impossible')
	exit(0)
(sl, sr) = (s[:1 + s[1:].index(sc)], s[s[1:].index(sc) + 2:])
slu = sl[:(len(sl) + 1) // 2][::-1]
sru = sr[:13 - len(slu)]
sld = sl[len(slu):]
srd = sr[len(sru):][::-1]
print(slu + sru)
print(sld + srd)


__author__ = 'Think'
word = input()
found = False
for i in range(2, 27):
	if word[i] in word[:i - 1]:
		place2 = i
		place1 = word[:i - 1].index(word[i])
		found = True
		break
if not found:
	print('Impossible')
else:
	rows = [[''] * 13, [''] * 13]
	start = (place1 + place2 + 1) // 2
	pos = 0
	skip = 0
	while pos < 26:
		if (start + pos + skip) % 27 == place2:
			skip = 1
		else:
			point = (start + pos + skip) % 27
			if pos < 13:
				rows[0][pos] = word[point]
			else:
				rows[1][25 - pos] = word[point]
			pos += 1
	for i in rows[0]:
		print(i, end='')
	print()
	for j in rows[1]:
		print(j, end='')


checky = [-1] * 26
rowOne = [None] * 13
rowTwo = [None] * 13
firstr = None
secondr = None
listy = [x for x in input()]
for (i, c) in enumerate(listy):
	if checky[ord(c) - 65] > -1:
		secondr = i
		firstr = checky[ord(c) - 65]
	else:
		checky[ord(c) - 65] = i
if firstr + 1 == secondr:
	print('impossible')
else:
	index = int((firstr + secondr + 1) / 2)
	row = 2
	col = 12
	for i in range(27):
		if index != secondr:
			if row == 2:
				rowTwo[col] = listy[index]
				if col == 0:
					row = 1
				else:
					col -= 1
			else:
				rowOne[col] = listy[index]
				col += 1
		if index == 26:
			index = 0
		else:
			index += 1
	print(''.join(rowOne))
	print(''.join(rowTwo))