#include <limits.h>
#include <stdio.h>

#define GRID_SIZE 300

/* Dump a 2d array for debugging */

#define array_size(array) (sizeof array / sizeof array[0])
#define dump2d(array) { \
	puts(#array":"); \
	for (int row = 0; row < array_size(array); row++) { \
		for (int col = 0; col < array_size(array[0]); col++) { \
			printf("%5d", array[row][col]); \
		} \
		putchar('\n'); \
	} \
}

#define BAD_ARGS 1
int main(int argc, char *argv[]) {
	static int cells[GRID_SIZE][GRID_SIZE];
	int grid_serial;
	struct {
		int power_level, bottom, right, size;
	} best = {INT_MIN};

	if (argc < 2 || sscanf(argv[1], "%d", &grid_serial) != 1 ) {
		return BAD_ARGS;
	}

	/* Fill in cell power levels and check individual cells */

	for (int row = 0; row < GRID_SIZE; row++) {
		int y = row + 1;
		for (int col = 0; col < GRID_SIZE; col++) {
			int x = col + 1;
			int rack_id = x + 10;
			int power_level = rack_id * y;
			power_level += grid_serial;
			power_level *= rack_id;
			power_level = power_level % 1000 / 100;
			power_level -= 5;
			cells[row][col] = power_level;
			if (power_level > best.power_level) {
				best.power_level = power_level;
				best.bottom = row;
				best.right = col;
				best.size = 1;
			}
		}
	}

	if (0) dump2d(cells)

	/* Replace the value in each cell with the sum of all values in
	 * the rectangle from that cell to the top left corner, inclusive */

	for (int right = 1; right < GRID_SIZE; right++) {
		cells[0][right] += cells[0][right-1];
	}
	for (int bottom = 1; bottom < GRID_SIZE; bottom++) {
		int row_sum = 0;
		for (int right = 0; right < GRID_SIZE; right++) {
			row_sum += cells[bottom][right];
			cells[bottom][right] = row_sum + cells[bottom-1][right];
		}
	}

	if (0) dump2d(cells)

	/* Check all squares 2x2 and up */

	/* Sums for squares of any size in the top left corner
	 * of the grid can be read off directly */

	for (int right = 1; right < GRID_SIZE; right++) {
		int bottom = right;
		int size = bottom + 1;
		int power_level = cells[bottom][right];
		if (power_level > best.power_level) {
			best.power_level = power_level;
			best.bottom = bottom;
			best.right = right;
			best.size = size;
		}
	}

	/* Other squares along the top row of the grid
	 * need the rectangle to their left subtracted out */

	for (int bottom = 1; bottom < GRID_SIZE; bottom++) {
		int size = bottom + 1;
		for (int right = size; right < GRID_SIZE; right++) {
			int power_level =
				cells[bottom][right] -
			       	cells[bottom][right-size];
			if (power_level > best.power_level) {
				best.power_level = power_level;
				best.bottom = bottom;
				best.right = right;
				best.size = size;
			}
		}
	}

	/* Other squares down the left side of the grid
	 * need the rectangle above them subtracted out */

	for (int bottom = 2; bottom < GRID_SIZE; bottom++) {
		for (int right = 1; right < bottom; right++) {
			int size = right + 1;
			int power_level =
				cells[bottom][right] -
			       	cells[bottom-size][right];
			if (power_level > best.power_level) {
				best.power_level = power_level;
				best.bottom = bottom;
				best.right = right;
				best.size = size;
			}
		}
	}

	/* Squares everywhere else need both the rectangle to their
	 * left and the rectangle above them subtracted out, then
	 * the overlap of those two regions added back in */

	for (int size = 2; size < GRID_SIZE; size++) {
		for (int bottom = size; bottom < GRID_SIZE; bottom++) {
			for (int right = size; right < GRID_SIZE; right++) {
				int power_level =
					cells[bottom][right] -
			       		cells[bottom][right-size] -
					cells[bottom-size][right] +
					cells[bottom-size][right-size];
				if (power_level > best.power_level) {
					best.power_level = power_level;
					best.bottom = bottom;
					best.right = right;
					best.size = size;
				}
			}
		}
	}

	printf("%d,%d,%d (%d)\n",
		best.right - best.size + 2,
		best.bottom - best.size + 2,
		best.size,
		best.power_level
	);
	return 0;
}