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 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+" do table.insert(words, w) end local str2 = io.read() local result, success = search(words, str2) if success then print(table.concat(result[1], " ")) print(table.concat(result[2], " ")) else print(result) end end main()