package main;

import java.util.ArrayList;
import java.util.HashMap;

public class A306308 {

	private static int INI_START_VALUE = 1;
	private static int INI_END_VALUE = 302500;

	private static int ARRAY_HALF_SIZE = 400;
	private static int ARRAY_DIM = 1 + 2 * ARRAY_HALF_SIZE;

	private static int VISIT_MAX = 1;

	private static int FIRST_J = 2;

	private static int SECOND_J = 1;

	private static int MAX_STEPS = VISIT_MAX * ARRAY_DIM * ARRAY_DIM + 1;

	private final static int[][] board = new int[ARRAY_DIM][ARRAY_DIM];
	private final static HashMap<Integer, Coord> bvalues = new HashMap<Integer, Coord>();

	public static void main(String[] args) {
		new A306308().run();
	}

	public void run() {

		int newx = 0, newy = 0;
		int[][] visited = new int[ARRAY_DIM][ARRAY_DIM];

		int x = ARRAY_HALF_SIZE;
		int y = ARRAY_HALF_SIZE;

		board[x][y] = 1;
		bvalues.put(1, new Coord(x, y));

		x += 1;
		board[x][y] = 2;
		bvalues.put(2, new Coord(x, y));

		System.out.println("Initializing...\n");
		int count = 3;
		while (count < ARRAY_DIM * ARRAY_DIM) {
			while (board[x - 1][y] != 0) {
				++y;
				board[x][y] = count;
				bvalues.put((int) count, new Coord(x, y));
				++count;
			}
			while (board[x][y - 1] != 0) {
				--x;
				board[x][y] = count;
				bvalues.put((int) count, new Coord(x, y));
				++count;
			}
			while (board[x + 1][y] != 0) {
				--y;
				board[x][y] = count;
				bvalues.put((int) count, new Coord(x, y));
				++count;
			}
			while (board[x][y + 1] != 0 && x < (ARRAY_DIM - 1)) {
				++x;
				board[x][y] = count;
				bvalues.put((int) count, new Coord(x, y));
				++count;
			}
		}

		ArrayList<ArrayList<Integer>> foundLoops = new ArrayList<>();
		HashMap<Integer, Integer> startValueLoopIndex = new HashMap<>();
		ArrayList<Integer> savedEndValues = new ArrayList<>();
		int[] loopIndexCount = new int[50];

		newStartValue: for (int startValue = INI_START_VALUE; startValue <= INI_END_VALUE; ++startValue) {

			if (startValue % 500 == 0)
				System.out.println("Start value = " + startValue);

			x = bvalues.get(startValue).x;
			y = bvalues.get(startValue).y;

			savedEndValues.clear();

			nextRunStart: while (true) {

				for (int i = 0; i < ARRAY_DIM; ++i) {
					for (int j = 0; j < ARRAY_DIM; ++j)
						visited[i][j] = 0;
				}
				visited[x][y] = 1;

				for (int steps = 0; steps <= MAX_STEPS; ++steps) {

					if (x >= ARRAY_DIM - FIRST_J) {
						System.out.println("x overflow");
						System.exit(1);
					}
					if (x < FIRST_J) {
						System.out.println("x underflow");
						System.exit(2);
					}
					if (y >= ARRAY_DIM - FIRST_J) {
						System.out.println("y overflow");
						System.exit(3);
					}
					if (y < FIRST_J) {
						System.out.println("y underflow");
						System.exit(4);
					}

					int small = MAX_STEPS;

					if (visited[x + FIRST_J][y + SECOND_J] < VISIT_MAX && board[x + FIRST_J][y + SECOND_J] < small) {
						small = board[x + FIRST_J][y + SECOND_J];
						newx = x + FIRST_J;
						newy = y + SECOND_J;
					}
					if (visited[x + FIRST_J][y - SECOND_J] < VISIT_MAX && board[x + FIRST_J][y - SECOND_J] < small) {
						small = board[x + FIRST_J][y - SECOND_J];
						newx = x + FIRST_J;
						newy = y - SECOND_J;
					}
					if (visited[x + SECOND_J][y + FIRST_J] < VISIT_MAX && board[x + SECOND_J][y + FIRST_J] < small) {
						small = board[x + SECOND_J][y + FIRST_J];
						newx = x + SECOND_J;
						newy = y + FIRST_J;
					}
					if (visited[x + SECOND_J][y - FIRST_J] < VISIT_MAX && board[x + SECOND_J][y - FIRST_J] < small) {
						small = board[x + SECOND_J][y - FIRST_J];
						newx = x + SECOND_J;
						newy = y - FIRST_J;
					}
					if (visited[x - FIRST_J][y + SECOND_J] < VISIT_MAX && board[x - FIRST_J][y + SECOND_J] < small) {
						small = board[x - FIRST_J][y + SECOND_J];
						newx = x - FIRST_J;
						newy = y + SECOND_J;
					}
					if (visited[x - FIRST_J][y - SECOND_J] < VISIT_MAX && board[x - FIRST_J][y - SECOND_J] < small) {
						small = board[x - FIRST_J][y - SECOND_J];
						newx = x - FIRST_J;
						newy = y - SECOND_J;
					}
					if (visited[x - SECOND_J][y + FIRST_J] < VISIT_MAX && board[x - SECOND_J][y + FIRST_J] < small) {
						small = board[x - SECOND_J][y + FIRST_J];
						newx = x - SECOND_J;
						newy = y + FIRST_J;
					}
					if (visited[x - SECOND_J][y - FIRST_J] < VISIT_MAX && board[x - SECOND_J][y - FIRST_J] < small) {
						small = board[x - SECOND_J][y - FIRST_J];
						newx = x - SECOND_J;
						newy = y - FIRST_J;
					}

					if (small == MAX_STEPS) {

						if (savedEndValues.contains(board[x][y])) {
							if (savedEndValues.contains(board[x][y])) {
								for (int i = 0; i < foundLoops.size(); ++i) {
									if (foundLoops.get(i).indexOf(board[x][y]) >= 0) {
										startValueLoopIndex.put(startValue, i);
										++loopIndexCount[i];
										continue newStartValue;
									}
								}

							}

							ArrayList<Integer> newLoop = new ArrayList<>();
							for (int i = savedEndValues.indexOf(board[x][y]); i < savedEndValues.size(); ++i)
								newLoop.add(savedEndValues.get(i));
							System.out.print("Found a new loop!: " + newLoop + "  Start value:" + startValue
									+ "  End value squence: ");
							for (int k = 0; k < savedEndValues.size(); ++k)
								System.out.print(savedEndValues.get(k) + " ");
							System.out.println();
							++loopIndexCount[foundLoops.size()];
							startValueLoopIndex.put(startValue, foundLoops.size());
							foundLoops.add(newLoop);
							continue newStartValue;
						} 
						else {
							savedEndValues.add(board[x][y]);
							continue nextRunStart;
						}
					}

					x = newx;
					y = newy;
					++visited[x][y];
				}
				throw new RuntimeException("It appears we didn't find an end value");

			}

		}

		System.out.println("Found loops:");
		for (int i=0;i<foundLoops.size();++i) System.out.println("\t"+i+": "+foundLoops.get(i)+"  Start square count: "+loopIndexCount[i]);

	}
	
	class Coord {
		public Integer x;
		public Integer y;

		Coord(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}

}