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


struct crate {
	struct crate * next;
	char id;
};


void
crate_free(struct crate * c)
{
	if (!c)
		return;
	crate_free(c->next);
	free(c);
}


int
crates_move_9000(struct crate ** stack, int stacks, int dest, int src, int count)
{
	int i;

	if (dest < 0 || dest >= stacks
			|| src < 0 || src >= stacks)
	{
		fprintf(stderr, "Invalid src/dest stack (%d/%d/%d)\n",
				stacks, dest, src);
		return -1;
	}

	for (i = 0; i < count; ++i) {
		struct crate * c;

		if (stack[src] == NULL) {
			fprintf(stderr, "No crates available in stack %d\n",
					src);
			return -1;
		}

		c = stack[src];
		stack[src] = c->next;
		c->next = stack[dest];
		stack[dest] = c;
	}

	return 0;
}


int
crates_move_9001(struct crate ** stack, int stacks, int dest, int src, int count)
{
	int i;
	struct crate * first, * last;

	if (dest < 0 || dest >= stacks
			|| src < 0 || src >= stacks)
	{
		fprintf(stderr, "Invalid src/dest stack (%d/%d/%d)\n",
				stacks, dest, src);
		return -1;
	}

	last = first = stack[src];
	for (i = 1; i < count; ++i) {
		if (last)
			last = last->next;
	}
	if (!last) {
		fprintf(stderr, "Fewer than %d crates available in stack %d\n",
				count, src);
		return -1;
	}

	stack[src] = last->next;
	last->next = stack[dest];
	stack[dest] = first;

	return 0;
}


#ifdef CRATES_DUMP
int
crates_dump(struct crate ** stack, int stacks)
{
	int i;

	for (i = 0; i < stacks; ++i) {
		struct crate * c;

		fprintf(stderr, "%d:", i + 1);
		for (c = stack[i]; c != NULL; c = c->next) {
			fprintf(stderr, " %c", c->id);
		}
		fprintf(stderr, "\n");
	}
	fprintf(stderr, "\n");

	return 0;
}
#endif


int
main(int argc, char ** argv)
{
	int (*crates_move)(struct crate **, int, int, int, int) = crates_move_9000;
	char buf[BUFSIZ];
	int stacks = 0, i;
	struct crate ** stack = NULL;
	regex_t movecmd;

	while ((i = getopt(argc, argv, "p:m:")) != -1) {
		switch (i) {
		case 'p':
			switch (atoi(optarg)) {
			case 1:
				crates_move = crates_move_9000;
				break;

			case 2:
				crates_move = crates_move_9001;
				break;

			default:
				fprintf(stderr, "Unexpected puzzle part %s\n", optarg);
				return -1;
			}
			break;

		case 'm':
			if (strcmp(optarg, "9000") == 0)
				crates_move = crates_move_9000;
			else if (strcmp(optarg, "9001") == 0)
				crates_move = crates_move_9001;
			else {
				fprintf(stderr, "Unknown CrateMover %s\n", optarg);
				return -1;
			}
			break;

		default:
			return -1;
		}
	}

	while (fgets(buf, sizeof(buf), stdin)) {
		int len;

		len = strlen(buf);

		if (len == 1 && buf[0] == '\n') {
			break;
		}
		if (stacks == 0 && stack == NULL) {
			if (len % 4 != 0) {
				fprintf(stderr, "Unexpected first line width: %d\n", len);
				return -1;
			}
			stacks = len / 4;
			stack = calloc(stacks, sizeof(struct crate *));
		}
		if (len != stacks * 4) {
			fprintf(stderr, "Unexpected input line width: %d/%d\n", len, stacks * 4);
			return -1;
		}

		for (i = 0; i < stacks; ++i) {
			if (isupper(buf[i * 4 + 1])) {
				struct crate ** pc = stack + i;
				while (*pc != NULL)
					pc = &(*pc)->next;
				*pc = malloc(sizeof(struct crate));
				(*pc)->next = NULL;
				(*pc)->id = buf[i * 4 + 1];
			}
		}

#ifdef CRATES_DUMP
		crates_dump(stack, stacks);
#endif
	}

	regcomp(&movecmd, "move ([[:digit:]]+) from ([[:digit:]]+) to ([[:digit:]]+)\n", REG_EXTENDED);
	while (fgets(buf, sizeof(buf), stdin)) {
		regmatch_t matches[4];
		if (regexec(&movecmd, buf, 4, matches, 0) != 0) {
			fprintf(stderr, "Unexpected move command: %s\n", buf);
		}
		crates_move(stack, stacks,
				atoi(buf + matches[3].rm_so) - 1,
				atoi(buf + matches[2].rm_so) - 1,
				atoi(buf + matches[1].rm_so));

#ifdef CRATES_DUMP
		crates_dump(stack, stacks);
#endif
	}
	regfree(&movecmd);

	for (i = 0; i < stacks; ++i) {
		fputc(stack[i] ? stack[i]->id : ' ', stdout);
	}
	fputc('\n', stdout);

	for (i = 0; i < stacks; ++i) {
		crate_free(stack[i]);
	}
	free(stack);

	return 0;
}