import static java.lang.System.exit;

import java.io.PrintWriter;
import java.util.Random;

public class TestsGen {

	static int testsCount;
	static final Random rand = new Random(1263123L);
	private static final String REVBRACKETS = ")]}";
	private static final String BRACKETS = "([{";
	static final String ALPHABET = REVBRACKETS + BRACKETS;

	static char byID(int id) {
		if (id < ~2 || id > 2) {
			throw new AssertionError();
		}
		return id >= 0 ? BRACKETS.charAt(id) : REVBRACKETS.charAt(~id);
	}

	static int getID(char c) {
		int pos = BRACKETS.indexOf(c);
		if (pos < 0) {
			return ~(REVBRACKETS.indexOf(c));
		} else {
			return pos;
		}
	}

	static void printTest(String line) {
		System.err.println("[" + (++testsCount) + "]");
		try {
			PrintWriter out = new PrintWriter(testsCount / 10 + "" + testsCount
					% 10);
			out.println(line);
			out.close();
		} catch (Exception e) {
			e.printStackTrace();
			exit(1);
		}
	}

	public static void main(String[] args) {
		// First group n <= 1000, 60 points
		printTest(genCorrectTest(1000));
		printTest(genTwoChangesTest(1000));
		printTest(genTwoChangesTest(1000));
		printTest(genTwoChangesTest(1000));
		printTest(genOddLengthTest(1000));
		for (int i = 0; i < 25; i++) {
			printTest(genRandomOKTest(1, 1000));
		}
		// Second group n <= 10^5, 40 points
		for (int i = 0; i < 20; i++) {
			printTest(genRandomOKTest(50000, 100000));
		}
	}

	static void genRandomString(int n, StringBuilder sb) {
		if (n == 0) {
			return;
		}
		int m = rand.nextInt(n);
		int type = rand.nextInt(3);
		sb.append(byID(type));
		genRandomString(m, sb);
		sb.append(byID(~type));
		genRandomString(n - m - 1, sb);
	}

	static String genCorrectTest(int maxN) {
		StringBuilder sb = new StringBuilder();
		int len = rand.nextInt(maxN / 2) + 1;
		genRandomString(len, sb);
		char[] s = sb.toString().toCharArray();
		return new String(s);
	}

	static String genOddLengthTest(int maxN) {
		StringBuilder sb = new StringBuilder();
		int len = rand.nextInt(maxN / 2) + 1;
		genRandomString(len, sb);
		char[] s = sb.toString().toCharArray();
		String ret = new String(s);
		int toRemove = rand.nextInt(ret.length());
		return ret.substring(0, toRemove) + ret.substring(toRemove + 1);
	}

	static String genTwoChangesTest(int maxN) {
		StringBuilder sb = new StringBuilder();
		int len = rand.nextInt(maxN / 2) + 1;
		genRandomString(len, sb);
		char[] s = sb.toString().toCharArray();
		int i = rand.nextInt(s.length);
		int j;
		do {
			j = rand.nextInt(s.length);
		} while (i == j);
		change(s, i);
		change(s, j);
		return new String(s);
	}

	static void change(char[] s, int i) {
		char c;
		do {
			c = ALPHABET.charAt(rand.nextInt(6));
		} while (s[i] == c);
		s[i] = c;
	}

	static String genRandomOKTest(int minN, int maxN) {
		StringBuilder sb = new StringBuilder();
		int len = rand.nextInt((maxN - minN) / 2) + 1 + minN / 2;
		genRandomString(len, sb);
		char[] s = sb.toString().toCharArray();
		change(s, rand.nextInt(s.length));
		return new String(s);
	}
}
