#define _GNU_SOURCE

#include <ctype.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>


// Proper modulo operator
#define modulo(n, m) ((((n) % (m)) + (m)) % (m))


enum direction {
	D_NORTH = 3,
	D_EAST = 0,
	D_SOUTH = 1,
	D_WEST = 2,
};


char const *
direction_name(enum direction dir)
{
	switch (dir) {
	case D_NORTH: return "North";
	case D_EAST: return "East";
	case D_SOUTH: return "South";
	case D_WEST: return "West";
	}
	return NULL;
}


enum direction
direction_turn(enum direction dir, char turn)
{
#define direction_go(d, t) (1000 * (d) + (t))

	switch (direction_go(dir, turn)) {
	case direction_go(D_NORTH, 'R'):
	case direction_go(D_SOUTH, 'L'):
		return D_EAST;

	case direction_go(D_NORTH, 'L'):
	case direction_go(D_SOUTH, 'R'):
		return D_WEST;

	case direction_go(D_EAST, 'L'):
	case direction_go(D_WEST, 'R'):
		return D_NORTH;

	case direction_go(D_EAST, 'R'):
	case direction_go(D_WEST, 'L'):
		return D_SOUTH;
	}

	fprintf(stderr, "Unexpected direction_turn(%d, %c)\n", dir, turn);
	return D_NORTH;

#undef direction_go
}


int
map_move(char * map, int cols, int rows, int pos, enum direction dir, int distance)
{
	int skip, wrap, base;

	switch (dir) {
	case D_NORTH:
		skip = -cols;
		wrap = cols * rows;
		break;

	case D_EAST:
		skip = 1;
		wrap = cols;
		break;

	case D_SOUTH:
		skip = cols;
		wrap = cols * rows;
		break;

	case D_WEST:
		skip = -1;
		wrap = cols;
		break;

	default:
		fprintf(stderr, "Unexpected direction %d\n", dir);
		return -1;
	}

	base = (pos / wrap) * wrap;

	while (distance > 0) {
		int newpos = base + modulo(pos + skip, wrap);

		while (map[newpos] == ' ' || map[newpos] == '\n')
			newpos = base + modulo(newpos + skip, wrap);

		switch (map[newpos]) {
		case '.':
			pos = newpos;
			--distance;
			break;

		case '#':
			distance = 0;
			break;

		default:
			fprintf(stderr, "Unexpected map character %c\n", map[newpos]);
			return -1;
		}
	}

	return pos;
}


int
main()
{
	char * buf = NULL, * beg, * end;
	long bufsiz = 0, buflen = 0, maxline = 0, lines = 0;
	long pos;
	enum direction dir;
	char distance[8], c;
	int dlen = 0;


	// Read map data
	// Don't try and figure out lines yet, in case we get a line longer than
	// our read buffer, which could make things awkward.
	while (1) {
		if (bufsiz - buflen < BUFSIZ / 2) {
			void * p;
			bufsiz += BUFSIZ;
			if ((p = realloc(buf, bufsiz)) == NULL) {
				fprintf(stderr, "Bad realloc(%ld)\n", bufsiz);
				free(buf);
				return -1;
			}
			buf = p;
		}

		if (!fgets(buf + buflen, bufsiz - buflen, stdin))
			// End of file!
			break;

		if (buflen > 0 && buf[buflen] == '\n' && buf[buflen - 1] == '\n')
			// End of map input.
			break;

		buflen += strlen(buf + buflen);
	}

	// Work out max lines and longest line.
	for (beg = buf, lines = 0; beg < buf + buflen; beg = end + 1, ++lines) {
		end = memchr(beg, '\n', buf + buflen - beg);
		if (end - beg > maxline)
			maxline = end - beg;
	}
	if (maxline == 0 || lines == 0) {
		fprintf(stderr, "Unexpected map size (%ld,%ld)\n", maxline, lines);
		free(buf);
		return -1;
	}
	++maxline; // Also count the newline on the end of each line.

	// Resize the map data buffer to hold a full grid of data
	if ((beg = realloc(buf, lines * maxline)) == NULL) {
		fprintf(stderr, "Bad realloc(%ld)\n", bufsiz);
		free(buf);
		return -1;
	}
	buf = beg;
	memset(buf + buflen, ' ', lines * maxline - buflen);

	// Move the map data so that it fits the grid properly
	for (end = buf + buflen, pos = lines - 1; pos >= 0; end = beg, --pos) {
		beg = memrchr(buf, '\n', (end - buf) - 1);
		beg = beg ? beg + 1 : buf;
		memmove(buf + pos * maxline, beg, (end - beg));
		memset(buf + (pos * maxline) + (end - beg) - 1, ' ', maxline - (end - beg) + 1);
		buf[pos * maxline + maxline - 1] = '\n';
	}

	// Set initial position
	pos = 0;
	dir = D_EAST;
	while (buf[pos] != '.') {
		++pos;
	}

	// Read and follow the movement instructions.
	while (pos >= 0 && (c = fgetc(stdin)) != EOF) {
		if (isdigit(c)) {
			distance[dlen++] = c;
		}
		else if (c == 'L' || c == 'R') {
			distance[dlen] = '\0';

			pos = map_move(buf, maxline, lines, pos, dir, atoi(distance));

			dir = direction_turn(dir, c);
			dlen = 0;
		}
		else if (c == '\n') {
			// Cover last bit of distance, if any
			distance[dlen] = '\0';
			pos = map_move(buf, maxline, lines, pos, dir, atoi(distance));
			break;
		}
		else {
			fprintf(stderr, "Unexpected movement instruction (%c)\n", c);
			free(buf);
			return -1;
		}
	}
	if (pos < 0) {
		free(buf);
		return -1;
	}

	// Done.
	printf("Password is %ld (%ld,%ld,%d)\n",
			1000 * (1 + pos / maxline) + 4 * (1 + pos % maxline) + dir,
			(1 + pos % maxline), (1 + pos / maxline), dir);

	// Tidy and exit.
	free(buf);

	return 0;
}