import java.io.*;
import java.util.*;

public class TestGen {
    private static int nTests;
    private static Random random = new Random(42);

    public static void write(String[] dict, String[] words) {
        try {
            PrintWriter out = new PrintWriter(String.format("%02d", nTests + 1));
            out.println(dict.length);
            for (String s : dict) {
                out.println(s);
            }
            out.println(words.length);
            for (String s : words) {
                out.println(s);
            }
            out.close();
            if (out.checkError()) {
                throw new IOException("Some error occured during test writing");
            }
            ++nTests;
        } catch (IOException ex) {
            ex.printStackTrace();
        }
    }

    private static char[][] neighbour1 = new char[128][];
    private static char[][][] neighbour2 = new char[128][128][];
    static {
        String[] keyboard = {"qwertyuiop", "asdfghjkl", "zxcvbnm"};
        for (int i = 0; i < keyboard.length; ++i) {
            String line = keyboard[i];
            for (int j = 0; j < line.length(); ++j) {
                char c = line.charAt(j);
                int set = 0;
                if (j > 0) {
                    set |= 1 << (line.charAt(j - 1) - 'a');
                }
                if (j + 1 < line.length()) {
                    set |= 1 << (line.charAt(j + 1) - 'a');
                }
                if (i > 0) {
                    String line2 = keyboard[i - 1];
                    if (j < line2.length()) {
                        set |= 1 << (line2.charAt(j) - 'a');
                    }
                    if (j + 1 < line2.length()) {
                        set |= 1 << (line2.charAt(j + 1) - 'a');
                    }
                }
                if (i + 1 < keyboard.length) {
                    String line2 = keyboard[i + 1];
                    if (j < line2.length()) {
                        set |= 1 << (line2.charAt(j) - 'a');
                    }
                    if (j - 1 < line2.length() && j > 0) {
                        set |= 1 << (line2.charAt(j - 1) - 'a');
                    }
                }
                neighbour1[c] = new char[Integer.bitCount(set)];
                for (int ii = 0, jj = 0; ii < 30; ++ii) {
                    if ((set & (1 << ii)) != 0) {
                        neighbour1[c][jj++] = (char) ('a' + ii);
                    }
                }
            }
        }
        for (char c1 = 'a'; c1 <= 'z'; ++c1) {
            for (char c2 = 'a'; c2 <= 'z'; ++c2) {
                int union = 0;
                for (char t : neighbour1[c1]) {
                    union |= 1 << (t - 'a');
                }
                for (char t : neighbour1[c2]) {
                    union |= 1 << (t - 'a');
                }
                neighbour2[c1][c2] = new char[Integer.bitCount(union)];
                for (int i = 0, j = 0; i < 30; ++i) {
                    if ((union & (1 << i)) != 0) {
                        neighbour2[c1][c2][j++] = (char) ('a' + i);
                    }
                }
            }
        }
    }

    private static String randomString(int length) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < length; ++i) {
            sb.append((char) (random.nextInt(26) + 'a'));
        }
        return sb.toString();
    }

    private static String randomMutation(String s, int index) {
        StringBuilder sb;
        do {
            sb = new StringBuilder(s);
            switch (random.nextInt(3)) {
                case 0:
                    sb.deleteCharAt(index == sb.length() ? index - 1 : index);
                break;
                case 1:
                    sb.setCharAt(index == sb.length() ? index - 1 : index, (char) ('a' + random.nextInt(26)));
                break;
                case 2:
                    sb.insert(index, (char) ('a' + random.nextInt(26)));
                break;
            }
        } while (sb.length() == 0);
        return sb.toString();
    }

    private static void writeRandom1(int nDict, int nWords, int length) {
        boolean fromEnd = length < 0;
        length = Math.abs(length);
        Set<String> dictionary = new HashSet<String>();
        List<String> words = new ArrayList<String>();
        do {
            while (words.size() > 10 * nWords) {
                words.remove(words.size() - 1);
            }
            String base = randomString(length);
            List<Integer> indices;
            {
                Set<Integer> set = new HashSet<Integer>();
                if (fromEnd) {
                    for (int i = 0; i < 40; ++i) {
                        set.add(length - i - 1);
                    }
                } else {
                    for (int i = 0; i < 1000; ++i) {
                        set.add(random.nextInt(length + 1));
                    }
                }
                indices = new ArrayList<Integer>(set);
            }
            int itCount = 0;
            while (dictionary.size() < nDict && itCount < 100) {
                int os = dictionary.size();
                dictionary.add(randomMutation(base, indices.get(random.nextInt(indices.size()))));
                if (dictionary.size() == os) {
                    ++itCount;
                }
            }
            for (int i = 0; i < nWords; ++i) {
                words.add(randomMutation(base, indices.get(random.nextInt(indices.size()))));
            }
            System.out.print(".");
        } while (dictionary.size() < nDict);
        Collections.shuffle(words, random);
        words = words.subList(0, nWords);
        write(dictionary.toArray(new String[nDict]), words.toArray(new String[nWords]));
    }

    private static void useAll(int nDict, int nWords, int length) {
        String[] dict = new String[nDict];
        Set<String> dictUsed = new HashSet<String>();
        List<String> words = new ArrayList<String>();
        for (int i = 0; i < nDict; ++i) {
            do {
                dict[i] = randomString(length);
            } while (dictUsed.contains(dict[i]));
            dictUsed.add(dict[i]);
            for (int j = 0; j < 10000; ++j) {
                words.add(randomMutation(dict[i], random.nextInt(length + 1)));
            }
        }
        Collections.shuffle(words, random);
        write(dict, words.subList(0, nWords).toArray(new String[nWords]));
    }

    private static void genAll(StringBuilder sb, int length, List<String> dest) {
        if (sb.length() != 0) {
            dest.add(sb.toString());
        }
        if (sb.length() < length) {
            sb.append('0');
            for (char c = 'a'; c <= 'z'; ++c) {
                sb.setCharAt(sb.length() - 1, c);
                genAll(sb, length, dest);
            }
            sb.deleteCharAt(sb.length() - 1);
        }
    }

    private static void randomSmallAll(int order, int maxCount, int nAppend) {
        List<String> all = new ArrayList<String>();
        genAll(new StringBuilder(), order, all);
        Collections.shuffle(all, random);
        List<String> all2 = new ArrayList<String>(all);
        all2.addAll(all);
        Collections.shuffle(all2, random);
        while (all.size() > maxCount) {
            all.remove(all.size() - 1);
        }
        while (all2.size() > maxCount) {
            all2.remove(all2.size() - 1);
        }
        StringBuilder nnn = new StringBuilder();
        for (int i = 0; i < nAppend; ++i) {
            nnn.append('q');
        }
        String nn = nnn.toString();
        for (int i = 0; i < all.size(); ++i) {
            all.set(i, all.get(i) + nn);
        }
        for (int i = 0; i < all2.size(); ++i) {
            all2.set(i, all2.get(i) + nn);
        }
        write(all.toArray(new String[all.size()]), all2.toArray(new String[all2.size()]));
    }

    private static void veryLongVerySmall() {
        String s = randomString(490000);
        String[] dict = new String[27];
        String[] words = new String[27];
        for (int i = 0; i < 26; ++i) {
            words[i] = dict[i] = String.valueOf((char) ('a' + i));
        }
        dict[26] = s;
        words[26] = randomMutation(s, random.nextInt(s.length() + 1));
        Collections.shuffle(Arrays.asList(dict), random);
        Collections.shuffle(Arrays.asList(words), random);
        write(dict, words);
    }

    public static void main(String[] args) throws IOException {
        write(new String[] {"a"}, new String[] {"a"});
        write(new String[] {"a"}, new String[] {"z"});
        write(new String[] {"p"}, new String[] {"k"});
        write(new String[] {"q", "w", "e", "a", "s", "d", "z", "x", "c"}, new String[] {"w", "e", "r", "s", "d", "f", "x", "c", "v"});
        write(new String[] {"p", "l", "m"}, new String[] {"o", "k", "n"});
        for (int nt = 6; nt <= 25; ++nt) {
            randomSmallAll(2, 500, Math.min(17, 2 * (nt - 1)));
        }
        for (int nt = 26; nt <= 30; ++nt) {
            System.out.print("Generating test #" + (nTests + 1) + "...");
            useAll(100, 50000, 4);
            System.out.println(" done!");
        }
        for (int nt = 31; nt <= 35; ++nt) {
            System.out.print("Generating test #" + (nTests + 1) + "...");
            writeRandom1(40000, 40000, 10);
            System.out.println(" done!");
        }
        for (int nt = 36; nt <= 40; ++nt) {
            System.out.print("Generating test #" + (nTests + 1) + "...");
            randomSmallAll(4, 50000, 0);
            System.out.println(" done!");
        }
        for (int nt = 41; nt <= 45; ++nt) {
            System.out.print("Generating test #" + (nTests + 1) + "...");
            writeRandom1(1200, 1200, -400);
            System.out.println(" done!");
        }
        for (int nt = 46; nt <= 50; ++nt) {
            System.out.print("Generating test #" + (nTests + 1) + "...");
            veryLongVerySmall();
            System.out.println(" done!");
        }
    }
}
