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

import static java.lang.Math.*;

public class ProperTicTacToe {
	Map<Integer,Integer> minimax = new HashMap<Integer,Integer>();
	static final Rational MONE = Rational.ONE.negate();
	static final Rational[] LOST
		= new Rational[] { MONE, MONE, MONE };
	static final Rational[] DRAW
		= new Rational[] { Rational.ZERO, Rational.ZERO, Rational.ZERO};
	static final Rational BIG = new Rational("3");
	static final Rational MBIG = BIG.negate();
	static final String[] SYM = { " ", "X", "O" };

	void print(int state) {
		System.out.println("+-+-+-+");
		for (int i = 0 ; i < 9 ; i++) {
			System.out.print("|");
			System.out.print(SYM[state >> 2*i &3]);
			if (i%3 == 2) System.out.println("|\n+-+-+-+");
		}
		System.out.println();
	}

	Rational[] inv(Rational[] array) {
		Rational[] result = new Rational[array.length];
		for (int i = 0 ; i < result.length ; i++) 
			result[i] = array[array.length - 1 - i].negate();
		return result;
	}

	boolean hasWon(int state, int player) {
		for (int i = 0 ; i < 3 ; i++) {
			if ((state >>    2*i &3) == player &&
				(state >>  6+2*i &3) == player &&
				(state >> 12+2*i &3) == player ||
				(state >>    6*i &3) == player &&
				(state >>  2+6*i &3) == player &&
				(state >>  4+6*i &3) == player) {
				return true;
			}
		}
		if ((state >>  8 &3) == player && (
			(state >>  0 &3) == player && (state >> 16 &3) == player ||
			(state >>  4 &3) == player && (state >> 12 &3) == player)) {
			return true;
		}
		return false;
	}

	//int states = 0;

	Rational[] minimax(int state, int player) {
		//states++;
		if (hasWon(state, 3-player)) return LOST;
		Rational[][] child = new Rational[9][];
		for (int i = 0 ; i < 9 ; i++) if ((state >> 2*i &3) == 0) child[i] = inv(minimax(state | player << 2*i, 3-player));
		Rational v = null;
		for (Rational[] c : child) if (c != null && (v == null || v.compareTo(c[1]) < 0)) v = c[1];
		if (v == null) return DRAW;
		Rational maxVi = null;
		for (Rational[] c : child) if (c != null) {
			if (c[0].compareTo(v) < 0 && (maxVi == null || maxVi.compareTo(c[0]) < 0))
				maxVi = c[0];
			if (c[1].compareTo(v) < 0 && (maxVi == null || maxVi.compareTo(c[1]) < 0))
				maxVi = c[1];
		}
		if (maxVi == null) maxVi = v;
		Rational sum = Rational.ZERO;
		for (Rational[] c : child) if (c != null && c[1].equals(v)) {
			Rational dif = c[2].subtract(c[1]);
			if (dif.compareTo(Rational.ZERO) > 0) sum = sum.add(dif.invert());
		}
		Rational[] result = new Rational[] { maxVi, v, v };
		if (sum != Rational.ZERO) result[2] = v.add(sum.invert());
		return result;
	}

	String pad(String s, int length) {
		int pad = length - s.length();
		StringBuilder sb = new StringBuilder();
		for (int i = 0 ; i < pad / 2 ; i++) sb.append(' ');
		sb.append(s);
		for (int i = pad / 2 ; i < pad ; i++) sb.append(' ');
		return sb.toString();
	}

	void run(int board) {
		//states = 0;
		//long time = System.currentTimeMillis();
		System.out.println("\nInput:");
		print(board);System.out.println();
		int[] count = new int[4];
		for (int i = 0 ; i < 9 ; i++) count[board >> 2*i &3]++;
		if (count[3] > 0 || count[1] > count[2] + 1 || count[1] < count[2]) {
			System.out.println("Invalid board");
			return;
		}
		for (int player = 1 ; player <= 2 ; player++) if (hasWon(board, player)) {
			System.out.println("Player " + SYM[player] + " has already won");
			return;
		}
		int player = count[1] == count[2] ? 1 : 2;
		Rational[][] child = new Rational[9][];
		for (int i = 0 ; i < 9 ; i++) if ((board >> 2*i &3) == 0) child[i] = inv(minimax(board | player << 2*i, 3-player));
		Rational v = null;
		for (Rational[] c : child) if (c != null && (v == null || v.compareTo(c[1]) < 0)) v = c[1];
		if (v == null) {
			System.out.println("Game is already over");
			return;
		}
		Rational sum = Rational.ZERO;
		for (Rational[] c : child) if (c != null && c[1].equals(v)) {
			Rational dif = c[2].subtract(c[1]);
			if (dif.compareTo(Rational.ZERO) > 0) sum = sum.add(dif.invert());
		}
		String[] pretty = new String[9];
		for (int i = 0 ; i < 9 ; i++) {
			if (child[i] == null) pretty[i] = "";//SYM[board >> 2*i &3];
			else if (child[i][1].compareTo(v) < 0) pretty[i] = "0";
			else if (sum.equals(Rational.ZERO)) pretty[i] = "*";
			else if (child[i][1].compareTo(child[i][2]) == 0) pretty[i] = "0";
			else if (child[i][1].compareTo(child[i][2]) < 0) pretty[i] = child[i][2].subtract(child[i][1]).invert().divide(sum).toString();
			else throw new RuntimeException("Case fallthrough... D'OH!");
		}
		int[] colwidth = new int[3];
		for (int y = 0 ; y < 3 ; y++) {
			for (int x = 0 ; x < 3 ; x++) {
				colwidth[x] = max(colwidth[x], pretty[3*y+x].length());
			}
		}
		StringBuilder div = new StringBuilder("+");
		for (int i = -2 ; i < colwidth[0] ; i++) div.append('-');
		div.append("+");
		for (int i = -2 ; i < colwidth[1] ; i++) div.append('-');
		div.append("+");
		for (int i = -2 ; i < colwidth[2] ; i++) div.append('-');
		div.append("+");
		String DIV = div.toString();
		System.out.println("Strategy:");
		System.out.println(DIV);
		for (int i = 0 ; i < 9 ; i++) {
			System.out.print("|");
			System.out.print(pad(pretty[i], colwidth[i%3] + 2));
			if (i%3 == 2) System.out.println("|\n" + DIV);
		}
		System.out.println();
		//System.out.println(states / ((System.currentTimeMillis() - time)/1000) + " states per second");
	}

	public static void main(String[] args) {
		ProperTicTacToe pttt = new ProperTicTacToe();
		if (args.length == 0) {
			pttt.run(0);
		} else for (String arg : args) {
			try {
				BufferedReader input = new BufferedReader(new FileReader(args[0]));
				int board = 0;
				int y = 0;
				for (String line = input.readLine() ; y < 3 && line != null ; line = input.readLine()) {
					line = line.replace('x','X').replace('o','O').replace('0','O');
					StringTokenizer st = new StringTokenizer(line, " XO", true);
					int x = 0;
					while (x < 3 && st.hasMoreTokens()) {
						String t = st.nextToken();
						if (t.equals("X")) {
							board |= 1 << 2*(3*y + x);
						} else if (t.equals("O")) {
							board |= 2 << 2*(3*y + x);
						} else if (!t.equals(" ")) {
							continue;
						}
						x++;
					}
					if (x > 0) y++;
				}
				pttt.run(board);
			} catch (IOException e) {
				System.out.println("Error while reading file \"" + arg + "\"");
			}
		}
	}
}