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

public class TestGen {

    static PrintWriter out;
    static Random rnd = new Random(0);
    static int tNumber;
    static PrintWriter testDescr;


    
    static void printTest(int[] nxt, int[] a, int[] b, int sb) throws IOException {
        System.out.println(String.format("Generating test %d", tNumber));
        if (tNumber < 10)
            out = new PrintWriter("../tests/0" + tNumber);
        else
            out = new PrintWriter("../tests/" + tNumber);
        for (int i = 'a'; i <= 'z'; ++i)
            out.print((char)nxt[i - 'a']);
        out.println();
        out.println(a.length);

        for (int i = 0; i < a.length; ++i)
            out.print((char)a[i]);        
        out.println();        
        for (int i = 0; i < b.length; ++i)
            out.print((char)b[i]);          
        out.println();                        
        out.close();
        testDescr.println("../tests/" + ((tNumber > 9) ? tNumber : ("0" + tNumber)) + ", folder=tests, subtask=subtask" + sb + ", points=0, comment=\"Random test, n=" + a.length + "\"");
        tNumber++;        
    }

    static void printTest(int[] nxt, int[] a, int[] b, int sb, String comment) throws IOException {
        System.out.println(String.format("Generating test %d", tNumber));
        if (tNumber < 10)
            out = new PrintWriter("../tests/0" + tNumber);
        else
            out = new PrintWriter("../tests/" + tNumber);
        for (int i = 'a'; i <= 'z'; ++i)
            out.print((char)nxt[i - 'a']);
        out.println();
        out.println(a.length);

        for (int i = 0; i < a.length; ++i)
            out.print((char)a[i]);        
        out.println();        
        for (int i = 0; i < b.length; ++i)
            out.print((char)b[i]);          
        out.println();                        
        out.close();
        testDescr.println("../tests/" + ((tNumber > 9) ? tNumber : ("0" + tNumber)) + ", folder=tests, subtask=subtask" + sb + ", points=0, comment=\"" + comment + "\"");
        tNumber++;        
    }
    
    static void genSample() throws FileNotFoundException {
        out = new PrintWriter("../preliminary/01");
        out.println("bcdefghijklmnopqrstuvwwwww");
        out.println("7");
        out.println("abacaba");
        out.println("cdcecdc");        
        out.close();                
        testDescr.println("../preliminary/01, folder=preliminary, subtask=subtask0, points=0, comment=\"sample 1\"");
    }
    
    static int randFromTo(int l, int r) {
        return rnd.nextInt(r - l + 1) + l;      
    }
    

    static int[] getPartition(int n, int k) {
        ArrayList<Integer> tmp = new ArrayList<Integer>();
        int[] was = new int[n];
        for (int i = 0; i < n; ++i)
            was[i] = 0;
        for (int i = 0; i < k - 1; i++) {
            int now = randFromTo(1, n - 1);
            while (was[now] > 0) 
                now = randFromTo(1, n - 1);
            tmp.add(now);
            was[now] = 1;
        }
        Collections.sort(tmp);
        int[] ans = new int[k];
        int y = 0;
        for (int i = 0; i < tmp.size(); i++) {
            ans[i] = tmp.get(i) - y;
            y = tmp.get(i);
        }
        ans[k - 1] = n - y;
        return ans;
    }


    static int[] genCleverNexts(int k) {
        ArrayList<Integer> chars = new ArrayList<Integer>();
        for (int i = 'a'; i <= 'z'; ++i)
            chars.add(i);
        Collections.shuffle(chars);
        int[] ans = new int[30];
        int[] part;
        if (randFromTo(0, 1) == 1)
            part = getPartition(('z' - 'a' + 1), k);
        else {
            int t = ('z' - 'a' + 1) / k;
            part = new int[k];
            for (int i = 0; i < k; ++i)
                part[i] = t;
            part[0] += ('z' - 'a' + 1) % k;
        }
        for (int i = 0; i < k; ++i) {
            int cLen = part[i];//randFromTo(part[i]/2 + 1, part[i]);
            int y = -1;
            for (int j = 0; j < part[i] - 1; j++) {
                ans[chars.get(0) - 'a'] = chars.get(1);
                if (part[i] - cLen == j)
                    y = chars.get(0);
                chars.remove(0);
            }
            if (y == -1)
                y = chars.get(0);
            ans[chars.get(0) - 'a'] = y;
            chars.remove(0);
        }
        return ans;
    }

    static int[] genRandomNexts() {
        int[] ans = new int[30];
        for (int i = 'a'; i <= 'z'; ++i)
            ans[i - 'a'] = randFromTo('a', 'z');
        return ans;
    }

    static int[] genRandomString(int len) {
        int[] ans = new int[len];
        for (int i = 0; i < len; ++i)
            ans[i] = randFromTo('a', 'z');      
        return ans;
    }

    static int[] genGoodPairString(int[] str, int[] nxt, int steps) {
        int[] ans = new int[str.length];
        int[] now = new int[30];
        for (int i = 'a'; i <= 'z'; ++i)
            now[i - 'a'] = i;
        for (int i = 0; i < steps; i++)
            for (int j = 'a'; j <= 'z'; ++j)
                now[j - 'a'] = nxt[now[j - 'a'] - 'a'];
        for (int i = 0; i < ans.length; i++)
            ans[i] = now[str[i] - 'a']; 
        return ans;
    }


    static int getAns(int[] nxt, int[] a, int[] b) {
        int[] go = new int[200];
        for (int i = 0; i < a.length; ++i) {
            if (go[a[i]] == 0)
                go[a[i]] = b[i];
            if (go[a[i]] != b[i]) {
                return -1;
            }
        }
        int[] now = new int[200];
        for (int i = 'a'; i <= 'z'; ++i)
            now[i] = i;
        int it = 1000000;
        int t = 0;
        while (it --> 0) {
            boolean good = true;
            for (int i = 'a'; i <= 'z'; ++i)
                good &= go[i] == 0 || (now[i] == go[i]);
            if (good) {
                return t;
            }
            for (int i = 'a'; i <= 'z'; ++i)
                now[i] = nxt[now[i] - 'a'];
            ++t;    
        }
        return t;
    }

    
    public static void main(String[] args) throws IOException {
        new File("../preliminary").mkdir();
        new File("../tests").mkdir();        
        testDescr = new PrintWriter("../tests.desc");

        long time = System.currentTimeMillis();        
        genSample();
        tNumber = 1;
        for (int i = 0; i < 5; ++i) {
            int[] nxt = genRandomNexts();
            int[] a = genRandomString(5);
            int[] b = genGoodPairString(a, nxt, i + 1);                     
            printTest(nxt, a, b, 1);            
        } 
        {
            int[] nxt = genRandomNexts();
            int[] a = genRandomString(20);
            int[] b = genRandomString(20);                      
            printTest(nxt, a, b, 1);        
        }
        for (int i = 0; i < 10; ++i) {
            int[] nxt = genRandomNexts();
            int[] a = genRandomString(1000);
            int[] b = genGoodPairString(a, nxt, randFromTo(1000, 10000));                       
            printTest(nxt, a, b, 1);
        } 
        {
            int[] nxt = genRandomNexts();
            int[] a = genRandomString(1000);
            int[] b = genRandomString(1000);                        
            printTest(nxt, a, b, 1);        
        }
        {
            int[] nxt = genRandomNexts();
            int[] a = {'a', 'b', 'a', 'c', 'a', 'b', 'a'};
            int[] b = {'a', 'b', 'a', 'c', 'a', 'b', 'a'};
            printTest(nxt, a, b, 1, "Equal strings, n = 7, ans = 0");
        }                                              
        {
            int[] nxt = genRandomNexts();
            int[] a = new int[1000];
            int[] b = new int[1000];
            for (int i = 0; i < 1000; i++) {
                int c = randFromTo('a', 'z');
                a[i] = c;
                b[i] = c;
            }
            printTest(nxt, a, b, 1, "Equal strings, n = 1000, ans = 0");
        }
        {
            Scanner sc = new Scanner(new File("BigTest0.java"));
            String snxt = sc.next();
            int n = sc.nextInt();
            String sa = sc.next();
            String sb = sc.next();
            int[] a = new int[1000];
            int[] b = new int[1000];
            for (int i = 0; i < 1000; i += n) {
            	for (int j = 0; j < n; ++j) {
            		a[i + j] = sa.charAt(j);
            		b[i + j] = sb.charAt(j);            		
            	}
            }
            int[] nxt = new int[30];
            for (int i = 0; i < snxt.length(); i++)
            	nxt[i] = snxt.charAt(i);
            printTest(nxt, a, b, 1, "Big test, n = 1000, ans = 1242");
        }
        testDescr.println("comment_subtask1=\"n &lt;= 1000\"\nbonus_subtask1=60");


        for (int i = 0; i < 10; ++i) {
            int[] nxt = genRandomNexts();
            int[] a = genRandomString(100000);
            int[] b = genGoodPairString(a, nxt, randFromTo(10000, 100000));                     
            printTest(nxt, a, b, 2);
        } 
        {
            int[] nxt = genRandomNexts();
            int[] a = genRandomString(400000);
            int[] b = genRandomString(400000);                      
            printTest(nxt, a, b, 2);        
        }

        for (int i = 0; i < 5; ++i) {
            int[] nxt, a, b;
            do {
                nxt = genCleverNexts(randFromTo(2, 7));
                a = genRandomString(1000000);
                b = genGoodPairString(a, nxt, randFromTo(10000, 1000000));                      
                //System.out.println(getAns(nxt, a, b));
            } while (getAns(nxt, a, b) < 500);
            printTest(nxt, a, b, 2);
        } 
        {
            int[] nxt = genRandomNexts();
            int[] a = genRandomString(1000000);
            int[] b = genRandomString(1000000);                     
            printTest(nxt, a, b, 2);        
        }
        {
            int[] nxt = genRandomNexts();
            int[] a = new int[1000000];
            int[] b = new int[1000000];
            for (int i = 0; i < 1000000; i++) {
                int c = randFromTo('a', 'z');
                a[i] = c;
                b[i] = c;
            }
            printTest(nxt, a, b, 2, "Equal strings, n = 1000000, ans = 0");
        }                                              
        {
            int[] nxt = genRandomNexts();
            int[] a = new int[1000000];
            int[] b = new int[1000000];
            for (int i = 0; i < 1000000; i++) {
                int c = randFromTo('a', 'z');
                a[i] = c;
                b[i] = c;
            }
            printTest(nxt, a, b, 2, "Equal strings, n = 1000000, ans = 0");
        }                                              
        {
            Scanner sc = new Scanner(new File("BigTest1.java"));
            String snxt = sc.next();
            int n = sc.nextInt();
            String sa = sc.next();
            String sb = sc.next();
            int[] a = new int[1000000];
            int[] b = new int[1000000];
            for (int i = 0; i < 1000000; i += n) {
            	for (int j = 0; j < n; ++j) {
            		a[i + j] = sa.charAt(j);
            		b[i + j] = sb.charAt(j);            		
            	}
            }
            int[] nxt = new int[30];
            for (int i = 0; i < snxt.length(); i++)
            	nxt[i] = snxt.charAt(i);
            printTest(nxt, a, b, 2, "Big test, n = 1000000, ans = 1242");
        }

		{
            Scanner sc = new Scanner(new File("BigTest2.java"));
            String snxt = sc.next();
            int n = sc.nextInt();
            String sa = sc.next();
            String sb = sc.next();
            int[] a = new int[1000000];
            int[] b = new int[1000000];
            for (int i = 0; i < 1000000; i += n) {
            	for (int j = 0; j < n; ++j) {
            		a[i + j] = sa.charAt(j);
            		b[i + j] = sb.charAt(j);            		
            	}
            }
            int[] nxt = new int[30];
            for (int i = 0; i < snxt.length(); i++)
            	nxt[i] = snxt.charAt(i);
            printTest(nxt, a, b, 2, "Big test, n = 1000000, ans = 1079");
        }

		{
            Scanner sc = new Scanner(new File("BigTest3.java"));
            String snxt = sc.next();
            int n = sc.nextInt();
            String sa = sc.next();
            String sb = sc.next();
            int[] a = new int[1000000];
            int[] b = new int[1000000];
            for (int i = 0; i < 1000000; i += n) {
            	for (int j = 0; j < n; ++j) {
            		a[i + j] = sa.charAt(j);
            		b[i + j] = sb.charAt(j);            		
            	}
            }
            int[] nxt = new int[30];
            for (int i = 0; i < snxt.length(); i++)
            	nxt[i] = snxt.charAt(i);
            printTest(nxt, a, b, 2, "Big test, n = 1000000, ans = 1163");
        }


		{
            Scanner sc = new Scanner(new File("BigTest4.java"));
            String snxt = sc.next();
            int n = sc.nextInt();
            String sa = sc.next();
            String sb = sc.next();
            int[] a = new int[1000000];
            int[] b = new int[1000000];
            for (int i = 0; i < 1000000; i += n) {
            	for (int j = 0; j < n; ++j) {
            		a[i + j] = sa.charAt(j);
            		b[i + j] = sb.charAt(j);            		
            	}
            }
            int[] nxt = new int[30];
            for (int i = 0; i < snxt.length(); i++)
            	nxt[i] = snxt.charAt(i);
            printTest(nxt, a, b, 2, "Big test, n = 1000000, ans = 1078");
        }


        testDescr.println("comment_subtask2=\"n &lt;= 1000000\"\nbonus_subtask2=40");
        System.out.println((System.currentTimeMillis() - time) / 1000);


    	testDescr.close();
    }                 
}
