import java.io.*; import java.util.*; public class Solution { private static boolean canBreak(String loginAttempt, ArrayList sol, ArrayList passwords) { int len = loginAttempt.length(); if (len == 0) { return true; } ArrayList dpTable = new ArrayList<>(); for (int i = 0; i < len + 1; i++) { dpTable.add(false); } for (int i = 1; i <= len; i++) { if (dpTable.get(i) == false && passwords.contains(loginAttempt.substring(0, i))) { dpTable.set(i, true); //sol.add(loginAttempt.substring(0, i)); } if (dpTable.get(i) == true) { if (i == len) { //sol.add(loginAttempt.substring(0, i)); return true; } for (int j = i + 1; j <= len; j++) // i instead of i + 1? { //System.out.println("i is " + i); // 2 //System.out.println("j is " + j); // 3 if (dpTable.get(j) == false && passwords.contains(loginAttempt.substring(i, j))) //instead of j-i { dpTable.set(j, true); //sol.add(loginAttempt.substring(i, j)); } if (j == len && dpTable.get(j) == true) { //sol.add(loginAttempt.substring(i, j)); return true; } } } } return false; } private static ArrayList getWords(ArrayList sol, String loginAttempt, ArrayList pass, int len, String result) { if (sol.contains("CRAPAMOLE")) { return sol; } //System.out.println("getWords(" + loginAttempt + ")"); //int len = loginAttempt.length(); for (int i = 1; i <= len; i++) { String prefix = loginAttempt.substring(0, i); if (pass.contains(prefix)) { if (i == len) { sol.add(result + prefix); sol.add("CRAPAMOLE"); return sol; } getWords(sol, loginAttempt.substring(i, len), pass, len - i, result + prefix + " "); //sol.add(prefix); } } return sol; } public static void main(String[] args) { Scanner pasta = new Scanner(System.in); int numTestCases = pasta.nextInt(); for (int i = 0; i < numTestCases; i++) { int numUsersWithPasswords = pasta.nextInt(); ArrayList existingPasswords = new ArrayList<>(); for (int j = 0; j < numUsersWithPasswords; j++) { existingPasswords.add(pasta.next()); } String loginAttempt = pasta.next(); ArrayList sol = new ArrayList<>(); if (canBreak(loginAttempt, sol, existingPasswords)) { sol = getWords(sol, loginAttempt, existingPasswords, loginAttempt.length(), ""); for (int j = 0; j < sol.size(); j++) { if (sol.get(j).equals("CRAPAMOLE")) { System.out.println(); break; } if (j == sol.size() - 1) { System.out.println(sol.get(j)); } else { System.out.print(sol.get(j) + " "); } } } else { System.out.println("WRONG PASSWORD"); } } } }