local sort_memo = {}
local function string_sort(str)
if not sort_memo[str] then
local t = {}
for c in str:gmatch "." do
table.insert(t, c)
end
table.sort(t)
sort_memo[str] = table.concat(t)
end
return sort_memo[str]
end
local function are_anagramic(w1, w2) return string_sort(w1) == string_sort(w2) end
local function remove_once(t, e)
local res = {}
local removed = false
for _, o in ipairs(t) do
if o ~= e or removed then table.insert(res, o) else removed = true end
end
return res
end
local function reverse(t)
local res = {}
local l = #t
for i = #t, 1, -1 do table.insert(res, t[i]) end
return res
end
local search_memo = {}
local function search(words, str)
local key = table.concat(words, " ") .. " " .. str
if not search_memo[key] then
if #words == 0 and str:len() == 0 then
local result = {{}, {}}
search_memo[key] = {result, true}
return result, true
end
for _, w in ipairs(words) do
local ana = str:sub(1, w:len())
if are_anagramic(w, ana) then
local result, success = search(remove_once(words, w), str:sub(w:len() + 1))
if success then
table.insert(result[1], ana)
table.insert(result[2], w)
search_memo[key] = {result, true}
return result, true
end
end
end
search_memo[key] = {"huy tam", false }
return "huy tam", false
else
return search_memo[key][1], search_memo[key][2]
end
end
local function main()
local str1 = io.read()
local words = {}
for w in str1:gmatch "[%w%p]+" do
table.insert(words, w)
end
local str2 = io.read()
local result, success = search(words, str2)
if success then
print(table.concat(reverse(result[1]), " "))
print(table.concat(reverse(result[2]), " "))
else
print(result)
end
end
main()