import static java.lang.Math.min;
import static java.lang.System.exit;
import static java.util.Arrays.fill;
import static java.util.Arrays.sort;

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

/**
 * Tests generator. Checks printed tests for correctness. Generates 3 groups of
 * tests: <br>
 * 1) |T| <= 1000, |A| <= 100, Sum(|A_i|) <= 1000, for 20 points, 10 tests <br>
 * Answer = 1, 2 tests<br>
 * Anti-greedy, 2 tests<br>
 * OK tests, 5 tests<br>
 * Impossible test, 1 test<br>
 * 
 * 2) |T| <= 10000, |A| <= 1000, Sum(|A_i|) <= 100000, for 40 points, 20 tests <br>
 * Answer = 1, 2 tests<br>
 * Anti-stupid-substring-entry-solver, 18 tests<br>
 * 
 * 3) |T| <= 100000, |A| <= 100000, Sum(|A_i|) <= 100000, for 40 points, 20
 * tests<br>
 * 
 * Answer = 1, 1 test <br>
 * Many Strings tests, 19 tests<br>
 * 
 * @author Niyaz Nigmatullin
 * 
 */
public class TestsGen {

	static final int MAXSUMLEN = 100000;
	static final int MAXLEN = 100000;
	static final int MAXSTRINGS = 100000;
	static int curTest;
	static final Random rand = new Random(553223321112345545L);
	static final int ALPHABET = 26;

	static class Test {
		String t;
		String[] a;

		public Test(String t, String[] a) {
			this.t = t;
			this.a = a;
			for (int i = 1; i < a.length; i++) {
				int j = random(i + 1);
				String tmp = a[i];
				a[i] = a[j];
				a[j] = tmp;
			}
		}

	}

	static boolean isCorrect(String s) {
		if (s.length() < 1 || s.length() > MAXLEN) {
			return false;
		}
		for (char c : s.toCharArray()) {
			if (c < 'a' || c > 'z') {
				return false;
			}
		}
		return true;
	}

	static boolean isCorrect(Test test) {
		if (!isCorrect(test.t)) {
			return false;
		}
		if (test.a.length < 1 || test.a.length > MAXSTRINGS) {
			return false;
		}
		int sumLen = 0;
		Set<String> set = new HashSet<String>();
		for (String e : test.a) {
			if (!isCorrect(e)) {
				return false;
			}
			if (set.contains(e)) {
				return false;
			}
			set.add(e);
			sumLen += e.length();
		}
		AhoCorasick ac = new AhoCorasick(test.a);
		List<String> temp = new ArrayList<String>();
		for (int i = 0; i < ac.free; i++) {
			ac.addAllEntries(i, temp);
			if (temp.size() > 1) {
				return false;
			}
			temp.clear();
		}
		if (sumLen > MAXSUMLEN) {
			return false;
		}
		return true;
	}

	static void printTest(Test test) {
		if (!isCorrect(test)) {
			throw new AssertionError();
		}
		System.err.println("Generating test #" + (++curTest));
		try {
			PrintWriter out = new PrintWriter(curTest / 10 + "" + curTest % 10);
			out.println(test.t);
			out.println(test.a.length);
			for (String e : test.a) {
				out.println(e);
			}
			out.close();
		} catch (IOException e) {
			e.printStackTrace();
			exit(239);
		}
	}

	public static void main(String[] args) {
		firstGroup();
		secondGroup();
		thirdGroup();
	}

	static void thirdGroup() {
		printTest(getAnswerEqualsToOneTest(100000, 50000, 10000));
		for (int i = 0; i < 19; i++) {
			printTest(manyStringsTest());
		}
	}

	static void saySorry() {
		System.err.println("Sorry, test generation may take a bit long");
	}

	static Test manyStringsTest() {
		int block = random(4, 6);
		int let = 26;
		while (pow(let, block) * block > MAXSUMLEN) {
			let--;
		}
		String t = genString(MAXLEN, let);
		List<String> all = new ArrayList<String>();
		gen(0, block, let, all, new char[block]);
		all.add(genString(MAXSUMLEN - (int) pow(let, block) * block - 1, 26)
				+ "z");
		return new Test(t, all.toArray(new String[all.size()]));
	}

	static void gen(int x, int block, int let, List<String> all, char[] c) {
		if (x == block) {
			all.add(new String(c));
			return;
		}
		for (int i = 0; i < let; i++) {
			c[x] = (char) ('a' + i);
			gen(x + 1, block, let, all, c);
		}
	}

	static long pow(int a, int b) {
		long ret = 1;
		for (int i = 0; i < b; i++) {
			ret *= a;
		}
		return ret;
	}

	static void secondGroup() {
		printTest(getAnswerEqualsToOneTest(100000, 10000, 1000));
		printTest(getAnswerEqualsToOneTest(100000, 10000, 1000));
		for (int i = 0; i < 18; i++) {
			printTest(antiSubstringSolver());
		}
	}

	static void firstGroup() {
		printTest(getAnswerEqualsToOneTest(1000, 500, 30));
		printTest(getAnswerEqualsToOneTest(1000, 500, 70));
		printTest(antiGreedy(1000, 500, 30));
		printTest(antiGreedy(1000, 500, 70));
		for (int i = 0; i < 5; i++) {
			printTest(okTest(1000, 500 + random(100), random(30) + 20));
		}
		printTest(impossible(1000, 1000, 100));
	}

	static Test impossible(int maxsumlen, int lenT, int maxCount) {
		Test ret;
		do {
			String t = genString(lenT, 26);
			String[] a = new String[random(maxCount / 9) + 1];
			int lengthLeft = maxsumlen;
			for (int i = 0; i + 1 < a.length; i++) {
				int maxlen = lengthLeft / (a.length - i);
				a[i] = genString(random(maxlen) + 3, 26);
				lengthLeft -= a[i].length();
			}
			a[a.length - 1] = genString(lengthLeft, 26);
			ret = new Test(t, a);
		} while (!isCorrect(ret));
		return ret;
	}

	static Test antiSubstringSolver() {
		int maxsumlen = 100000;
		int lenT = 10000;
		int maxCount = 1000;
		Test ret;
		do {
			String t = genString(lenT, 1);
			int[] border = new int[random(10) + 1];
			Set<Integer> set = new HashSet<Integer>();
			char[] curT = t.toCharArray();
			for (int i = 0; i < border.length; i++) {
				do {
					border[i] = random(t.length() - 1);
				} while (set.contains(border[i]) || set.contains(border[i] + 1));
				set.add(border[i]);
				set.add(border[i] + 1);
				curT[border[i] + 1] = (char) ('a' + random(25) + 1);
			}
			t = new String(curT);
			sort(border);
			int lengthLeft = maxsumlen;
			String[] a = new String[maxCount];
			a[0] = genString(random(10), 26) + t.substring(0, border[0] + 1);
			lengthLeft -= a[0].length();
			boolean[] used = new boolean[t.length()];
			used[border[0]] = true;
			for (int i = 1; i < border.length; i++) {
				a[i] = t.substring(border[i - 1] + 1, border[i] + 1);
				lengthLeft -= a[i].length();
				used[border[i]] = true;
			}
			a[border.length] = t.substring(border[border.length - 1] + 1)
					+ genString(random(10) + 1, 26);
			lengthLeft -= a[border.length].length();
			int curLetters = 0;
			for (int i = border.length + 1; i < a.length; i++) {
				int len = lengthLeft / (a.length - i);
				a[i] = genString(len - 3, 1);
				a[i] += (char) ('b' + curLetters / 25 / 25);
				a[i] += (char) ('b' + curLetters / 25 % 25);
				a[i] += (char) ('b' + curLetters % 25);
				curLetters++;
				lengthLeft -= a[i].length();
			}
			ret = new Test(t, a);
		} while (!isCorrect(ret));
		return ret;
	}

	static Test okTest(int maxsumlen, int lenT, int maxCount) {
		Test ret;
		do {
			String t = genString(lenT, 26);
			int[] border = new int[random(maxCount - 10) + 1];
			Set<Integer> set = new HashSet<Integer>();
			for (int i = 0; i < border.length; i++) {
				do {
					border[i] = random(t.length() - 1);
				} while (!set.add(border[i]));
			}
			sort(border);
			int lengthLeft = maxsumlen;
			String[] a = new String[border.length + 1
					+ halfRandom(maxCount - border.length - 5)];
			a[0] = genString(random(10), 26) + t.substring(0, border[0] + 1);
			lengthLeft -= a[0].length();
			boolean[] used = new boolean[t.length()];
			used[border[0]] = true;
			for (int i = 1; i < border.length; i++) {
				a[i] = t.substring(border[i - 1] + 1, border[i] + 1);
				lengthLeft -= a[i].length();
				used[border[i]] = true;
			}
			a[border.length] = t.substring(border[border.length - 1] + 1)
					+ genString(random(10) + 1, 26);
			lengthLeft -= a[border.length].length();
			all: for (int i = border.length + 1; i + 1 < a.length; i++) {
				int maxlen = lengthLeft / (a.length - i);
				if (random(3) != 0) {
					int left = random(t.length());
					int right;
					int countHere = 0;
					do {
						if (++countHere == 4) {
							i--;
							continue all;
						}
						right = random(left + 1, min(left + maxlen, t.length()));
					} while (used[right - 1]);
					used[right - 1] = true;
					a[i] = t.substring(left, right);
				} else {
					a[i] = genString(random(maxlen) + 1, 26);
				}
				lengthLeft -= a[i].length();
			}
			if (a[a.length - 1] == null) {
				a[a.length - 1] = genString(lengthLeft, 26);
			}
			ret = new Test(t, a);
		} while (!isCorrect(ret));
		return ret;
	}

	static Test antiGreedy(int maxsumlen, int lenT, int maxCount) {
		Test ret;
		int q = 0;
		do {
			if (++q == 10) {
				maxCount /= 2;
				q = 0;
			}
			String t = genString(lenT, 26);
			int[] border = new int[random(maxCount - 10) + 1];
			Set<Integer> set = new HashSet<Integer>();
			for (int i = 0; i < border.length; i++) {
				do {
					border[i] = random(t.length() - 1);
				} while (!set.add(border[i]));
			}
			sort(border);
			int lengthLeft = maxsumlen;
			String[] a = new String[border.length + 1
					+ halfRandom(maxCount - border.length - 5)];
			a[0] = genString(random(10), 26) + t.substring(0, border[0] + 1);
			lengthLeft -= a[0].length();
			boolean[] used = new boolean[t.length()];
			used[border[0]] = true;
			for (int i = 1; i < border.length; i++) {
				a[i] = t.substring(border[i - 1] + 1, border[i] + 1);
				lengthLeft -= a[i].length();
				used[border[i]] = true;
			}
			a[border.length] = t.substring(border[border.length - 1] + 1)
					+ genString(random(10) + 1, 26);
			lengthLeft -= a[border.length].length();
			all: for (int i = border.length + 1; i + 1 < a.length; i++) {
				int maxlen = lengthLeft / (a.length - i);
				if (random(3) != 0) {
					int left = random(3) == 0 ? 0 : random(t.length());
					int right;
					int countHere = 0;
					do {
						if (++countHere == 4) {
							i--;
							continue all;
						}
						right = random(left + 1, min(left + maxlen, t.length()));
					} while (used[right - 1]);
					used[right - 1] = true;
					a[i] = t.substring(left, right);
				} else {
					a[i] = genString(random(maxlen) + 1, 26);
				}
				lengthLeft -= a[i].length();
			}
			if (a[a.length - 1] == null) {
				a[a.length - 1] = genString(lengthLeft, 26);
			}
			ret = new Test(t, a);
		} while (!isCorrect(ret));
		return ret;
	}

	static Test getAnswerEqualsToOneTest(int maxsumlen, int lenT, int maxCount) {
		if (maxsumlen <= lenT) {
			throw new AssertionError();
		}
		Test ret;
		do {
			String t = genString(lenT, 1);
			String[] a = new String[random(maxCount) + 1];
			int lengthLeft = maxsumlen;
			{
				int left = random(10);
				int right = random(10);
				a[0] = genString(left, 26) + t + genString(right, 26);
				lengthLeft -= a[0].length();
			}

			int curLetters = 0;
			for (int i = 1; i < a.length; i++) {
				int len = lengthLeft / (a.length - i);
				a[i] = genString(len - 3, 1);
				a[i] += (char) ('b' + curLetters / 25 / 25);
				a[i] += (char) ('b' + curLetters / 25 % 25);
				a[i] += (char) ('b' + curLetters % 25);
				curLetters++;
				lengthLeft -= a[i].length();
			}
			ret = new Test(t, a);
		} while (!isCorrect(ret));
		return ret;
	}

	static String genString(int length, int letters) {
		if (length < 0) {
			throw new AssertionError();
		}
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < length; i++) {
			sb.appendCodePoint('a' + random(letters));
		}
		return sb.toString();
	}

	static int halfRandom(int n) {
		return random(n / 10, n);
	}

	static int random(int n) {
		return random(0, n - 1);
	}

	static int random(int a, int b) {
		return rand.nextInt(b - a + 1) + a;
	}

	static class AhoCorasick {
		final static int ALPHABET = 26;
		int[][] link;
		int[] sufLink;
		String[] terminates;
		int free;
		final int root = 0;

		public AhoCorasick(String[] a) {
			int sumLen = 1;
			for (String e : a) {
				sumLen += e.length();
			}
			link = new int[ALPHABET][sumLen];
			sufLink = new int[sumLen];
			terminates = new String[sumLen];
			free = 1;
			for (int[] d : link) {
				fill(d, -1);
			}
			fill(sufLink, -1);
			for (String e : a) {
				addWord(e);
			}
			makeSufLinks();
		}

		void addAllEntries(int pos, List<String> temp) {
			if (terminates[pos] == null) {
				pos = sufLink[pos];
			}
			for (; pos > 0; pos = sufLink[pos]) {
				temp.add(terminates[pos]);
			}
		}

		int go(int pos, char c) {
			return link[c - 'a'][pos];
		}

		void addWord(String word) {
			int pos = 0;
			for (int i = 0; i < word.length(); i++) {
				int c = word.charAt(i) - 'a';
				if (link[c][pos] < 0) {
					link[c][pos] = free++;
				}
				pos = link[c][pos];
			}
			terminates[pos] = word;
		}

		void makeSufLinks() {
			int[] q = new int[sufLink.length];
			int head = 0;
			int tail = 1;
			sufLink[0] = 0;
			while (head < tail) {
				int v = q[head++];
				for (int i = 0; i < link.length; i++) {
					int u = link[i][v];
					int w = v == root ? root : link[i][sufLink[v]];
					if (u < 0) {
						link[i][v] = w;
					} else {
						q[tail++] = u;
						sufLink[u] = w;
					}
				}
			}
			for (int i = 0; i < head; i++) {
				int j = q[i];
				if (terminates[sufLink[j]] == null) {
					sufLink[j] = sufLink[sufLink[j]];
				}
			}
		}
	}

}
