def solve():
import sys
input = sys.stdin.read
data = input().splitlines()
# Read inputs
n = int(data[0]) # Number of substrings
substrings = [data[i + 1] for i in range(n)]
main_string = data[n + 1]
k = int(data[n + 2])
# Preprocessing substrings
unique_chars = set(main_string)
valid_substrings = []
for sub in substrings:
filtered = "".join(c for c in sub if c in unique_chars)
if filtered:
valid_substrings.append(filtered)
# Check for "Impossible"
main_set = set(main_string)
available_chars = set("".join(valid_substrings))
if not main_set.issubset(available_chars):
print("Impossible")
return
# Dynamic programming to calculate deletions
dp = [float('inf')] * (len(main_string) + 1)
dp[0] = 0 # Base case: 0 deletions to form an empty prefix
for i in range(len(main_string)):
for sub in valid_substrings:
m = len(sub)
if i + 1 >= m and main_string[i - m + 1:i + 1] == sub:
# Calculate deletions required for this substring
required_deletions = len(sub) - len(main_string[i - m + 1:i + 1])
dp[i + 1] = min(dp[i + 1], dp[i - m + 1] + required_deletions)
# Determine the output
if dp[len(main_string)] <= k:
print("Possible")
else:
# Find the longest prefix that can be formed within K deletions
for i in range(len(main_string), -1, -1):
if dp[i] <= k:
print(main_string[:i])
return
print("Nothing")
