/* package whatever; // don't place package name! */
 
import java.util.*;
import java.lang.*;
import java.io.*;
 
/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
	private static boolean canMakePalindrome(String str){
        int[] arr = new int[255];
        for (int i = 0; i<str.length(); i++) {
            arr[str.charAt(i)] += 1;
        }
        int count = 0;
        for(int i=0; i<255; ++i){
            if((arr[i]&1)==1){
                count++;
            }
        }
        return count > 1 ? false : true;
    }
	// Make Palindrome from given String
    private static boolean canMakePalindrome(String str, String[] strs){
        int[] arr = new int[256];
        for (int i = 0; i<str.length(); i++) {
            arr[str.charAt(i)] += 1;
        }
        int count = 0;
        for(int i=0; i<256; ++i){
            if((arr[i]&1)==1){
                count++;
                strs[1] = (char)i+"";
            } else {
                for (int j = 0; j < arr[i]/2; j++) {
                    strs[0] += (char)i+"";
                }
            }
        }
        return count < 2;
    }
 
 
 
    private static ArrayList<String> generateAllPalidromes(String str, String center){
        ArrayList<String> arr = new ArrayList<String>();
        generatePalidrome(str, "", arr);
        for (int i = 0; i < arr.size(); i++) {
            String a = arr.get(i) + center + new StringBuilder(arr.get(i)).reverse().toString();
            arr.set(i, a);
        }
        return arr;
    }
 
    private static void generatePalidrome(String str, String prefix, ArrayList<String> arr){
        int n = str.length();
        if(n==0){
            arr.add(prefix);
        } else {
            for (int i = 0; i < n; i++) {
                generatePalidrome(str.substring(0,i) + str.substring(i+1,n), prefix+str.charAt(i), arr);
            }
        }
    }
 
    public static void testCanMakePalindrome(){
        assert true : canMakePalindrome("1");
        assert true : canMakePalindrome("122");
        assert true : canMakePalindrome("1122");
        assert false : canMakePalindrome("111222");
    }
 
    public static void main(String[] args) {
        String[] strs = {"","0"};
        String[] targets = {
                "",
                "1",
                "12",
                "121",
                "1221",
                "12321",
        };
        for(String target: targets) {
            if (canMakePalindrome(target, strs)) {
                String center = strs[1]; //"1";
                String str = strs[0]; //"123";
                System.out.printf("center: %s str: %s\n", center, str);
 
                ArrayList<String> arr = generateAllPalidromes(str, center);
                for (int i = 0; i < arr.size(); i++) {
                    System.out.println(arr.get(i));
                }
            } else {
                System.out.printf("No Solution for %s\n", target);
            }
        }
    }   
}

LyogcGFja2FnZSB3aGF0ZXZlcjsgLy8gZG9uJ3QgcGxhY2UgcGFja2FnZSBuYW1lISAqLwoKaW1wb3J0IGphdmEudXRpbC4qOwppbXBvcnQgamF2YS5sYW5nLio7CmltcG9ydCBqYXZhLmlvLio7CgovKiBOYW1lIG9mIHRoZSBjbGFzcyBoYXMgdG8gYmUgIk1haW4iIG9ubHkgaWYgdGhlIGNsYXNzIGlzIHB1YmxpYy4gKi8KY2xhc3MgSWRlb25lCnsKCXByaXZhdGUgc3RhdGljIGJvb2xlYW4gY2FuTWFrZVBhbGluZHJvbWUoU3RyaW5nIHN0cil7CiAgICAgICAgaW50W10gYXJyID0gbmV3IGludFsyNTVdOwogICAgICAgIGZvciAoaW50IGkgPSAwOyBpPHN0ci5sZW5ndGgoKTsgaSsrKSB7CiAgICAgICAgICAgIGFycltzdHIuY2hhckF0KGkpXSArPSAxOwogICAgICAgIH0KICAgICAgICBpbnQgY291bnQgPSAwOwogICAgICAgIGZvcihpbnQgaT0wOyBpPDI1NTsgKytpKXsKICAgICAgICAgICAgaWYoKGFycltpXSYxKT09MSl7CiAgICAgICAgICAgICAgICBjb3VudCsrOwogICAgICAgICAgICB9CiAgICAgICAgfQogICAgICAgIHJldHVybiBjb3VudCA+IDEgPyBmYWxzZSA6IHRydWU7CiAgICB9CgkvLyBNYWtlIFBhbGluZHJvbWUgZnJvbSBnaXZlbiBTdHJpbmcKICAgIHByaXZhdGUgc3RhdGljIGJvb2xlYW4gY2FuTWFrZVBhbGluZHJvbWUoU3RyaW5nIHN0ciwgU3RyaW5nW10gc3Rycyl7CiAgICAgICAgaW50W10gYXJyID0gbmV3IGludFsyNTZdOwogICAgICAgIGZvciAoaW50IGkgPSAwOyBpPHN0ci5sZW5ndGgoKTsgaSsrKSB7CiAgICAgICAgICAgIGFycltzdHIuY2hhckF0KGkpXSArPSAxOwogICAgICAgIH0KICAgICAgICBpbnQgY291bnQgPSAwOwogICAgICAgIGZvcihpbnQgaT0wOyBpPDI1NjsgKytpKXsKICAgICAgICAgICAgaWYoKGFycltpXSYxKT09MSl7CiAgICAgICAgICAgICAgICBjb3VudCsrOwogICAgICAgICAgICAgICAgc3Ryc1sxXSA9IChjaGFyKWkrIiI7CiAgICAgICAgICAgIH0gZWxzZSB7CiAgICAgICAgICAgICAgICBmb3IgKGludCBqID0gMDsgaiA8IGFycltpXS8yOyBqKyspIHsKICAgICAgICAgICAgICAgICAgICBzdHJzWzBdICs9IChjaGFyKWkrIiI7CiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICAgICAgcmV0dXJuIGNvdW50IDwgMjsKICAgIH0KCgoKICAgIHByaXZhdGUgc3RhdGljIEFycmF5TGlzdDxTdHJpbmc+IGdlbmVyYXRlQWxsUGFsaWRyb21lcyhTdHJpbmcgc3RyLCBTdHJpbmcgY2VudGVyKXsKICAgICAgICBBcnJheUxpc3Q8U3RyaW5nPiBhcnIgPSBuZXcgQXJyYXlMaXN0PFN0cmluZz4oKTsKICAgICAgICBnZW5lcmF0ZVBhbGlkcm9tZShzdHIsICIiLCBhcnIpOwogICAgICAgIGZvciAoaW50IGkgPSAwOyBpIDwgYXJyLnNpemUoKTsgaSsrKSB7CiAgICAgICAgICAgIFN0cmluZyBhID0gYXJyLmdldChpKSArIGNlbnRlciArIG5ldyBTdHJpbmdCdWlsZGVyKGFyci5nZXQoaSkpLnJldmVyc2UoKS50b1N0cmluZygpOwogICAgICAgICAgICBhcnIuc2V0KGksIGEpOwogICAgICAgIH0KICAgICAgICByZXR1cm4gYXJyOwogICAgfQoKICAgIHByaXZhdGUgc3RhdGljIHZvaWQgZ2VuZXJhdGVQYWxpZHJvbWUoU3RyaW5nIHN0ciwgU3RyaW5nIHByZWZpeCwgQXJyYXlMaXN0PFN0cmluZz4gYXJyKXsKICAgICAgICBpbnQgbiA9IHN0ci5sZW5ndGgoKTsKICAgICAgICBpZihuPT0wKXsKICAgICAgICAgICAgYXJyLmFkZChwcmVmaXgpOwogICAgICAgIH0gZWxzZSB7CiAgICAgICAgICAgIGZvciAoaW50IGkgPSAwOyBpIDwgbjsgaSsrKSB7CiAgICAgICAgICAgICAgICBnZW5lcmF0ZVBhbGlkcm9tZShzdHIuc3Vic3RyaW5nKDAsaSkgKyBzdHIuc3Vic3RyaW5nKGkrMSxuKSwgcHJlZml4K3N0ci5jaGFyQXQoaSksIGFycik7CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICB9CgogICAgcHVibGljIHN0YXRpYyB2b2lkIHRlc3RDYW5NYWtlUGFsaW5kcm9tZSgpewogICAgICAgIGFzc2VydCB0cnVlIDogY2FuTWFrZVBhbGluZHJvbWUoIjEiKTsKICAgICAgICBhc3NlcnQgdHJ1ZSA6IGNhbk1ha2VQYWxpbmRyb21lKCIxMjIiKTsKICAgICAgICBhc3NlcnQgdHJ1ZSA6IGNhbk1ha2VQYWxpbmRyb21lKCIxMTIyIik7CiAgICAgICAgYXNzZXJ0IGZhbHNlIDogY2FuTWFrZVBhbGluZHJvbWUoIjExMTIyMiIpOwogICAgfQoKICAgIHB1YmxpYyBzdGF0aWMgdm9pZCBtYWluKFN0cmluZ1tdIGFyZ3MpIHsKICAgICAgICBTdHJpbmdbXSBzdHJzID0geyIiLCIwIn07CiAgICAgICAgU3RyaW5nW10gdGFyZ2V0cyA9IHsKICAgICAgICAgICAgICAgICIiLAogICAgICAgICAgICAgICAgIjEiLAogICAgICAgICAgICAgICAgIjEyIiwKICAgICAgICAgICAgICAgICIxMjEiLAogICAgICAgICAgICAgICAgIjEyMjEiLAogICAgICAgICAgICAgICAgIjEyMzIxIiwKICAgICAgICB9OwogICAgICAgIGZvcihTdHJpbmcgdGFyZ2V0OiB0YXJnZXRzKSB7CiAgICAgICAgICAgIGlmIChjYW5NYWtlUGFsaW5kcm9tZSh0YXJnZXQsIHN0cnMpKSB7CiAgICAgICAgICAgICAgICBTdHJpbmcgY2VudGVyID0gc3Ryc1sxXTsgLy8iMSI7CiAgICAgICAgICAgICAgICBTdHJpbmcgc3RyID0gc3Ryc1swXTsgLy8iMTIzIjsKICAgICAgICAgICAgICAgIFN5c3RlbS5vdXQucHJpbnRmKCJjZW50ZXI6ICVzIHN0cjogJXNcbiIsIGNlbnRlciwgc3RyKTsKCiAgICAgICAgICAgICAgICBBcnJheUxpc3Q8U3RyaW5nPiBhcnIgPSBnZW5lcmF0ZUFsbFBhbGlkcm9tZXMoc3RyLCBjZW50ZXIpOwogICAgICAgICAgICAgICAgZm9yIChpbnQgaSA9IDA7IGkgPCBhcnIuc2l6ZSgpOyBpKyspIHsKICAgICAgICAgICAgICAgICAgICBTeXN0ZW0ub3V0LnByaW50bG4oYXJyLmdldChpKSk7CiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgIH0gZWxzZSB7CiAgICAgICAgICAgICAgICBTeXN0ZW0ub3V0LnByaW50ZigiTm8gU29sdXRpb24gZm9yICVzXG4iLCB0YXJnZXQpOwogICAgICAgICAgICB9CiAgICAgICAgfQogICAgfSAgIAp9