package cz.wrent.advent

fun main() {
	println(partOne(test))

	val result = partOne(input)
	println("9a: $result")

	println(partTwo(test))
	println(partTwo(test2))
	val resultTwo = partTwo(input)
	println("9b: $resultTwo")
}

private fun partOne(input: String): Long {
	val commands = input.split("\n")
		.map { it.split(" ") }
		.map { it.get(0) to it.get(1).toInt() }

	val visited = mutableSetOf(0 to 0)
	var head = 0 to 0
	var tail = 0 to 0
	commands.forEach { command ->
		repeat(command.second) {
			head = head.moveHead(command.first)
			tail = tail.moveTail(head)
			visited.add(tail)
		}
	}
	return visited.size.toLong()
}

private fun partTwo(input: String): Long {
	val commands = input.split("\n")
		.map { it.split(" ") }
		.map { it.get(0) to it.get(1).toInt() }

	val visited = mutableSetOf(0 to 0)
	val knots = mutableListOf<Pair<Int, Int>>()
	repeat(10) {
		knots.add(0 to 0)
	}
	commands.forEach { command ->
		repeat(command.second) {
			knots[0] = knots.first().moveHead(command.first)
			for (i in 1..9) {
				knots[i] = knots[i].moveTail(knots[i - 1])
			}
			visited.add(knots[9])
		}
	}
	return visited.size.toLong()}

private fun Pair<Int, Int>.moveHead(direction: String): Pair<Int, Int> {
	return when (direction) {
		"U" -> this.first to this.second + 1
		"D" -> this.first to this.second - 1
		"R" -> this.first + 1 to this.second
		"L" -> this.first - 1 to this.second
		else -> error("")
	}
}

private fun Pair<Int, Int>.toNeighboursAll(): Set<Pair<Int, Int>> {
	val set = mutableSetOf<Pair<Int, Int>>()
	for (i in this.first - 1..this.first + 1) {
		for (j in this.second - 1 .. this.second + 1) {
			set.add(i to j)
		}
	}
	return set
}

private fun Pair<Int, Int>.moveTail(head: Pair<Int, Int>): Pair<Int, Int> {
	if (head.toNeighboursAll().contains(this)) {
		return this
	} else if (this.first == head.first) {
		return this.first to if (this.second > head.second) this.second - 1 else this.second + 1
	} else if (this.second == head.second) {
		return (if (this.first > head.first) this.first - 1 else this.first + 1) to this.second
	} else {
		return (if (this.first > head.first) this.first - 1 else this.first + 1) to if (this.second > head.second) this.second - 1 else this.second + 1
	}
}

private const val test = """R 4
U 4
L 3
D 1
R 4
D 1
L 5
R 2"""

private const val test2 = """R 5
U 8
L 8
D 3
R 17
D 10
L 25
U 20"""

private const val input =
	"""R 2
L 2
D 2
U 2
R 2
D 2
L 2
D 2
U 2
L 2
D 1
R 1
D 2
R 2
U 1
R 1
U 2
R 1
L 2
D 2
L 1
U 1
L 1
D 1
R 1
L 2
U 2
R 2
U 1
R 2
L 2
D 1
U 1
D 2
L 1
U 1
L 1
D 1
U 1
D 1
L 2
D 2
U 2
L 2
U 1
R 2
D 2
L 1
R 1
U 1
R 1
L 1
U 2
D 1
U 2
R 1
U 1
R 2
D 2
R 2
U 2
D 2
U 2
L 1
D 2
R 1
L 2
D 2
R 2
L 2
U 2
L 2
R 1
D 1
R 1
L 2
D 1
L 2
R 1
U 1
R 1
U 1
L 2
U 1
D 2
R 1
L 1
D 1
R 1
L 2
R 2
L 2
R 1
L 1
D 1
L 1
R 1
D 2
U 1
D 2
R 1
D 1
U 1
L 1
R 1
D 2
R 2
L 2
R 1
L 1
R 1
U 3
L 2
R 3
L 1
R 1
L 2
D 1
U 3
L 1
R 3
U 1
L 2
U 2
D 2
R 2
D 1
L 2
U 1
R 1
L 3
R 2
L 3
R 2
L 2
D 2
U 3
R 2
L 1
R 2
U 1
D 2
U 3
D 1
U 3
L 1
R 3
D 2
R 1
L 2
D 1
L 1
D 3
U 2
L 3
R 1
U 3
L 1
R 2
U 3
D 2
U 3
L 3
R 1
L 2
R 2
D 3
L 1
D 3
R 3
L 1
U 1
D 1
L 3
D 1
U 2
D 3
U 3
L 1
U 2
D 1
R 3
D 1
R 1
L 2
U 1
R 1
L 1
U 3
D 3
U 3
R 1
D 3
U 1
L 2
R 2
U 2
R 1
D 3
L 1
D 2
U 2
R 2
D 2
R 3
L 2
R 1
L 3
D 3
R 1
L 1
U 3
R 1
D 3
R 3
D 2
U 2
R 2
D 2
U 3
D 2
R 1
U 2
L 3
D 1
L 2
U 1
D 1
U 4
R 4
U 4
D 4
U 3
D 1
R 4
L 1
D 2
R 3
U 1
R 2
D 2
U 4
R 3
D 2
L 1
U 4
D 3
U 1
D 4
L 2
U 3
D 4
R 3
L 2
D 4
L 2
R 3
U 2
R 2
U 1
L 3
R 3
L 3
U 4
R 4
U 2
R 3
U 1
L 3
D 4
L 4
R 4
D 3
L 4
R 1
U 4
D 3
R 3
U 1
L 4
U 2
L 2
D 4
U 3
R 1
U 2
D 4
U 4
D 4
U 1
L 4
R 3
U 2
R 1
L 4
D 4
U 3
R 2
L 2
U 3
L 1
R 1
L 1
U 4
L 1
R 3
U 1
R 1
D 2
R 2
L 4
D 1
L 2
R 1
D 1
L 3
D 3
U 4
R 2
L 4
U 2
L 1
R 3
U 3
L 2
R 2
D 2
R 3
U 4
L 1
U 3
L 3
U 1
R 1
L 2
D 3
L 5
D 2
U 2
D 4
R 2
L 3
U 3
R 1
U 4
D 1
R 2
U 1
L 5
R 4
D 5
R 5
D 2
U 2
L 5
D 2
U 3
R 2
L 4
D 5
L 4
R 4
U 5
R 2
U 5
L 1
D 2
L 3
U 4
D 2
U 2
L 3
R 4
U 4
R 5
L 1
D 2
U 4
D 5
L 5
R 4
U 3
R 2
U 5
L 3
U 5
R 3
U 2
R 2
D 3
R 2
L 2
D 4
R 4
U 3
R 3
D 5
R 2
U 3
L 5
R 1
U 5
D 4
R 3
D 5
U 1
R 4
L 5
D 1
U 3
L 4
U 3
R 3
D 5
U 5
D 5
L 5
U 4
D 5
L 3
R 3
D 4
U 2
L 5
R 1
U 5
L 4
U 4
D 5
R 4
L 1
U 2
D 2
L 1
R 2
D 4
R 5
L 3
R 4
D 4
L 4
R 2
L 1
D 3
L 3
R 2
D 3
R 5
D 2
U 4
D 5
L 1
U 3
D 3
U 6
L 1
R 1
L 4
R 6
L 1
R 1
D 2
U 6
R 1
U 3
R 6
U 1
R 1
L 3
D 5
R 6
L 6
R 1
U 2
R 1
L 5
R 5
D 6
R 4
D 4
R 1
U 6
R 4
U 1
R 5
U 3
L 5
U 1
R 5
L 5
D 5
R 3
L 5
D 3
L 2
U 3
R 1
U 1
D 4
R 4
L 2
U 3
L 1
U 5
L 5
D 4
R 6
U 6
L 5
U 3
R 3
D 1
U 6
R 2
L 4
R 2
L 5
U 3
D 1
U 3
R 1
D 1
L 3
U 6
L 5
U 2
L 3
D 1
L 3
U 6
L 4
D 3
R 4
D 1
L 4
U 1
R 6
D 6
R 5
D 4
R 4
D 4
U 6
D 4
L 3
R 4
L 5
R 1
D 6
U 6
D 2
R 1
L 6
U 6
L 5
D 6
U 4
R 4
D 3
U 5
D 6
U 7
L 5
U 7
R 6
U 1
L 6
U 1
R 2
D 7
R 4
U 1
R 6
L 6
D 4
L 4
U 4
R 1
D 7
L 7
D 7
L 5
D 1
L 1
U 2
R 5
D 5
L 3
U 5
D 6
L 4
R 1
U 6
L 3
D 6
L 7
D 6
R 3
U 7
R 1
D 6
R 3
U 7
D 5
U 1
L 4
U 3
D 3
U 3
R 1
L 2
R 2
L 1
U 3
D 5
U 7
D 1
U 7
L 4
D 3
U 4
R 6
D 2
L 5
R 7
L 5
R 1
U 6
R 7
U 4
D 3
U 1
L 1
D 1
U 6
L 1
U 1
R 7
L 4
D 1
U 2
R 7
L 7
R 5
U 4
R 2
L 7
U 6
R 5
L 1
R 3
U 7
D 7
L 4
R 1
U 4
R 1
L 7
D 4
L 5
D 7
U 4
L 5
R 6
U 1
L 4
R 6
D 2
L 1
D 2
U 4
L 5
U 5
D 4
U 7
L 2
D 3
U 5
R 7
D 1
R 7
D 6
U 4
R 3
D 5
U 5
D 8
R 7
L 7
R 1
D 5
L 3
R 1
U 3
R 6
D 5
R 6
L 5
D 7
L 5
R 2
D 1
R 7
L 1
D 3
R 8
L 5
U 8
R 6
U 4
D 2
U 4
D 5
U 7
D 5
U 2
D 3
U 1
R 4
L 2
R 4
U 7
R 8
D 2
U 3
R 7
D 2
U 1
D 6
R 4
L 4
R 3
D 8
R 8
U 7
L 3
U 7
D 1
U 6
R 8
L 1
R 1
D 8
U 7
L 3
D 4
L 4
R 2
L 6
D 6
L 4
R 7
D 8
L 8
U 8
R 2
L 6
U 5
D 2
L 5
U 1
L 6
D 6
U 7
L 2
U 5
R 6
D 5
L 8
U 8
R 1
U 2
L 3
D 1
L 3
U 4
D 3
L 6
R 9
L 9
U 9
R 1
D 4
U 1
L 3
R 7
U 7
R 1
U 1
R 2
D 4
U 8
L 7
R 3
U 8
L 1
R 1
D 7
U 3
L 3
U 8
D 3
L 1
D 6
L 3
U 4
D 3
U 3
L 3
D 5
L 6
U 9
L 1
U 2
L 3
R 1
L 9
D 2
U 1
L 3
R 9
L 8
R 2
L 7
D 4
L 4
R 2
L 4
R 8
D 4
L 2
D 5
R 8
U 6
L 9
D 1
L 6
R 9
D 4
L 5
U 5
D 1
U 3
L 4
U 2
L 2
R 2
L 1
R 7
L 4
D 4
U 4
L 1
R 2
D 6
L 1
U 8
D 7
R 5
D 7
R 7
L 8
U 8
L 5
D 7
U 2
D 2
R 1
U 2
L 1
R 1
L 2
D 1
U 9
L 9
U 9
R 1
U 3
R 7
U 8
R 1
L 7
D 1
U 7
R 9
D 8
R 2
D 5
L 5
D 2
L 6
U 6
R 1
L 1
D 2
R 4
L 3
U 2
R 5
L 3
R 6
U 8
R 1
U 1
R 7
D 10
R 2
D 4
R 3
L 5
D 1
U 8
R 1
U 4
D 6
L 5
U 8
D 6
L 6
R 4
L 9
R 5
U 6
L 8
U 6
L 10
D 4
U 6
L 8
U 3
R 3
L 6
U 1
R 9
D 8
U 9
R 5
U 10
R 8
U 9
L 7
R 4
D 7
U 3
L 5
R 3
D 9
L 9
U 6
R 10
L 2
D 7
U 8
D 4
L 3
U 4
R 2
L 10
D 4
U 10
R 7
D 5
R 7
U 3
L 10
R 8
L 7
D 3
L 6
R 1
L 2
U 1
R 1
U 8
R 5
L 9
R 9
L 1
D 4
R 6
U 7
L 7
R 3
U 4
D 2
U 8
L 5
D 3
L 6
D 7
L 2
U 1
R 6
L 8
D 9
R 3
U 4
D 8
L 5
R 9
L 1
U 7
L 5
D 4
U 5
L 4
R 4
L 3
U 11
D 1
L 10
U 6
L 5
D 3
U 8
D 11
L 8
R 2
U 5
L 9
D 3
L 11
R 2
U 5
L 7
D 11
R 8
U 1
L 10
R 10
L 9
R 9
L 8
R 7
D 3
U 6
R 11
U 8
D 4
L 9
U 3
D 5
L 4
R 5
D 7
L 5
U 10
D 8
L 3
D 2
U 9
D 6
L 3
U 3
D 8
U 4
R 1
L 9
U 4
L 5
D 10
L 11
U 6
D 8
L 5
R 9
L 2
U 2
L 10
R 5
U 6
L 7
R 7
U 9
D 6
R 7
D 8
U 7
R 6
L 2
D 6
R 8
L 5
R 1
L 10
R 8
U 11
R 10
L 10
R 10
L 4
U 4
D 9
U 8
R 5
D 7
U 7
L 6
D 4
L 9
R 2
U 8
D 2
L 2
D 2
U 6
L 2
R 9
U 10
D 11
U 3
R 9
U 1
L 11
R 7
L 4
R 5
U 10
L 3
R 10
L 10
D 2
L 9
D 9
L 6
D 11
R 10
L 2
R 4
D 2
R 4
D 8
L 3
U 10
R 4
L 2
U 1
L 3
R 1
L 2
R 3
D 2
L 2
D 3
R 5
U 10
L 12
R 5
D 5
U 9
L 9
D 2
L 8
U 2
L 11
U 5
L 8
U 7
R 4
U 10
D 4
L 5
R 3
D 8
R 12
L 5
U 9
L 10
R 5
U 10
R 1
L 5
U 6
D 7
L 12
D 2
R 12
L 1
U 11
D 8
R 12
L 8
U 3
R 9
L 8
D 2
L 10
D 10
R 4
D 2
R 11
U 4
R 10
U 7
L 7
D 5
U 5
R 9
D 10
L 10
U 1
D 11
U 4
D 5
U 5
D 8
U 2
D 4
R 4
L 5
U 10
D 12
R 9
L 11
R 9
L 1
D 9
L 11
D 12
U 4
R 7
D 1
U 3
L 4
U 9
R 12
D 1
L 7
U 7
D 6
U 1
R 3
L 7
U 5
L 2
D 10
R 12
L 3
U 7
D 10
L 5
R 1
U 9
L 1
D 11
R 5
L 2
D 1
U 3
R 2
L 3
U 5
L 3
D 5
R 10
L 7
R 12
U 4
D 3
R 3
L 2
R 7
U 4
D 9
U 7
D 1
R 9
L 2
U 6
R 5
D 3
U 7
R 12
L 10
D 11
L 8
U 12
D 13
U 9
D 5
U 4
R 2
L 3
U 13
R 4
L 9
U 4
L 3
U 9
R 1
D 6
U 4
D 3
U 5
R 5
L 11
R 8
D 1
U 4
D 10
R 5
D 10
U 3
D 4
R 1
U 3
R 13
L 6
D 8
R 12
L 4
U 2
L 13
D 11
L 4
U 8
L 10
R 2
D 8
R 11
L 2
D 8
R 8
L 10
U 10
L 4
D 9
L 7
D 11
L 10
U 13
L 6
U 7
D 8
L 3
R 10
L 14
U 13
L 11
D 5
R 8
U 2
D 9
L 14
U 7
R 4
U 1
D 8
U 8
D 9
L 2
D 7
R 1
D 9
R 2
U 4
D 8
L 9
R 6
L 2
R 11
D 6
L 5
U 8
L 4
R 3
D 5
L 3
U 9
R 3
U 1
D 7
R 1
L 10
U 1
L 8
U 11
D 8
U 12
R 9
L 5
D 10
L 2
R 8
D 10
R 6
D 1
L 11
D 8
R 7
L 14
D 12
L 11
R 11
U 9
R 12
D 10
L 12
R 4
L 8
D 2
R 3
L 14
R 7
U 10
R 1
L 6
R 4
D 11
L 13
R 12
U 4
L 12
U 10
D 8
R 10
D 9
R 13
L 2
U 2
D 7
U 7
R 3
D 3
R 13
U 8
R 10
U 13
D 14
R 11
D 7
R 2
U 5
D 2
L 6
U 14
L 10
R 9
U 11
R 12
D 5
L 11
R 12
U 11
R 8
L 2
D 14
U 3
D 9
U 5
L 4
U 5
L 6
D 3
L 1
R 10
L 4
D 12
U 15
L 5
D 11
L 15
D 10
L 14
U 1
L 14
D 6
R 6
U 9
R 1
L 7
D 11
U 12
D 2
R 7
L 2
D 13
U 13
R 6
L 3
D 3
R 11
U 3
D 3
U 11
L 10
U 7
R 7
D 9
U 10
R 11
U 12
D 11
R 11
U 2
R 2
D 9
R 12
D 1
L 11
R 1
U 2
R 14
L 4
R 1
D 12
R 7
U 12
L 2
U 5
D 7
R 15
D 5
L 9
D 7
R 10
U 12
D 10
R 11
D 5
U 10
R 2
U 11
R 3
U 6
D 14
U 11
D 5
L 8
D 6
L 2
U 2
L 14
R 8
U 15
L 10
D 1
R 4
L 8
D 7
L 15
U 10
D 14
U 9
L 7
R 13
U 11
R 15
L 11
R 2
L 11
R 14
L 1
D 10
L 2
U 7
L 9
D 12
R 2
L 4
U 4
R 9
L 6
R 13
D 1
U 13
R 7
D 3
R 14
L 12
D 15
R 16
L 7
R 2
U 3
R 9
U 10
D 6
U 7
L 11
D 12
L 16
R 12
D 10
U 16
D 9
U 14
L 14
U 11
D 14
L 14
D 10
L 3
D 10
U 6
D 11
L 8
U 4
D 1
U 5
D 5
L 4
U 8
R 3
D 12
U 4
R 8
D 6
U 8
D 2
U 12
L 6
D 12
R 7
D 6
U 7
D 12
L 3
R 2
L 12
R 13
U 16
L 6
D 8
U 13
R 14
D 4
U 7
D 1
R 4
D 13
R 10
D 7
R 11
L 6
U 6
R 7
L 8
D 2
L 11
U 3
L 12
U 4
D 11
U 8
D 10
U 1
R 12
U 1
L 15
R 15
D 2
L 8
D 13
L 3
R 8
U 14
R 5
U 3
D 15
U 7
D 1
L 6
D 8
U 13
R 6
L 6
D 3
L 9
D 17
U 8
R 16
L 6
D 9
U 3
L 10
R 13
L 14
U 8
R 7
U 12
D 14
R 1
D 3
L 11
R 8
D 9
R 17
D 5
R 17
U 8
L 10
D 7
U 4
D 16
L 9
D 1
L 16
R 7
L 1
R 11
U 10
R 2
U 10
L 15
U 10
R 2
D 11
U 12
L 15
U 4
D 2
R 4
U 2
L 11
R 16
U 10
R 4
D 9
U 7
D 2
R 10
D 14
L 10
U 9
R 7
D 3
R 7
L 3
U 15
D 13
L 17
R 12
U 13
D 16
U 13
R 13
U 14
L 16
U 7
D 2
R 11
U 17
D 9
R 12
U 16
L 11
R 3
U 9
L 6
D 2
U 1
D 7
L 1
U 7
D 8
U 11
L 4
R 6
L 2
U 12
L 13
U 5
L 17
R 16
D 10
U 12
L 7
R 4
U 8
D 17
R 13
L 2
D 5
L 1
R 2
D 16
U 9
D 15
L 8
U 14
R 9
D 18
U 16
L 17
U 9
D 11
U 17
R 8
D 17
U 14
D 8
U 8
R 8
U 14
R 5
L 1
R 3
D 5
U 10
R 16
U 18
D 16
U 11
D 18
U 13
L 11
D 2
R 16
D 15
L 9
D 12
R 11
L 8
U 8
R 10
L 2
D 6
L 5
D 9
L 3
D 1
U 18
D 12
U 13
L 6
R 17
D 10
R 9
L 6
R 3
U 1
R 1
U 6
L 15
U 8
D 15
U 14
R 10
L 6
U 1
L 12
R 9
D 13
U 1
L 16
U 16
L 13
R 4
U 3
D 11
L 12
R 11
U 17
R 18
L 4
R 6
L 18
D 10
L 16
R 2
D 4
R 14
D 11
L 12
R 7
L 9
U 12
D 12
R 4
L 1
D 14
R 14
L 3
U 2
L 6
R 7
D 6
U 18
L 17
U 12
R 12
L 5
D 13
R 7
D 8
L 16
D 13
U 4
D 3
R 16
L 9
U 8
D 15
R 8
L 12
R 5
L 1
U 11
D 11
L 10
U 7
D 6
L 15
D 9
R 10
D 6
U 14
L 7
U 19
R 17
L 12
U 1
L 9
R 17
D 12
U 3
L 15
R 16
D 15
R 15
L 1
U 16
R 19
D 9
L 16
D 12
R 8
L 2
D 16
L 17
U 16
D 9
L 9
U 8
L 9
R 16
L 3
D 8
U 7
D 10
U 17
R 2
D 16
R 6
U 9
R 4
L 17
D 10
U 10
L 14
D 9
R 8
L 9
R 18
U 13
L 16
R 2
U 16
L 11
U 4
L 13
R 8
L 19
U 4
D 10
R 10
U 14
R 13
L 17
U 17
R 12
D 18
R 2
D 5
L 12
U 6
D 7
R 9
L 13
D 15
R 9
U 16
D 14
R 8
L 8
U 10
L 8
D 18
U 8
D 9
L 6
R 8
U 4
D 14
L 13
D 4
R 3
U 13
L 2"""

package cz.wrent.advent

fun main() {
	println(partOne(test))

	val result = partOne(input)
	println("9a: $result")

	println(partTwo(test))
	println(partTwo(test2))
	val resultTwo = partTwo(input)
	println("9b: $resultTwo")
}

private fun partOne(input: String): Long {
	val commands = input.split("\n")
		.map { it.split(" ") }
		.map { it.get(0) to it.get(1).toInt() }

	val visited = mutableSetOf(0 to 0)
	var head = 0 to 0
	var tail = 0 to 0
	commands.forEach { command ->
		repeat(command.second) {
			head = head.moveHead(command.first)
			tail = tail.moveTail(head)
			visited.add(tail)
		}
	}
	return visited.size.toLong()
}

private fun partTwo(input: String): Long {
	val commands = input.split("\n")
		.map { it.split(" ") }
		.map { it.get(0) to it.get(1).toInt() }

	val visited = mutableSetOf(0 to 0)
	val knots = mutableListOf<Pair<Int, Int>>()
	repeat(10) {
		knots.add(0 to 0)
	}
	commands.forEach { command ->
		repeat(command.second) {
			knots[0] = knots.first().moveHead(command.first)
			for (i in 1..9) {
				knots[i] = knots[i].moveTail(knots[i - 1])
			}
			visited.add(knots[9])
		}
	}
	return visited.size.toLong()}

private fun Pair<Int, Int>.moveHead(direction: String): Pair<Int, Int> {
	return when (direction) {
		"U" -> this.first to this.second + 1
		"D" -> this.first to this.second - 1
		"R" -> this.first + 1 to this.second
		"L" -> this.first - 1 to this.second
		else -> error("")
	}
}

private fun Pair<Int, Int>.toNeighboursAll(): Set<Pair<Int, Int>> {
	val set = mutableSetOf<Pair<Int, Int>>()
	for (i in this.first - 1..this.first + 1) {
		for (j in this.second - 1 .. this.second + 1) {
			set.add(i to j)
		}
	}
	return set
}

private fun Pair<Int, Int>.moveTail(head: Pair<Int, Int>): Pair<Int, Int> {
	if (head.toNeighboursAll().contains(this)) {
		return this
	} else if (this.first == head.first) {
		return this.first to if (this.second > head.second) this.second - 1 else this.second + 1
	} else if (this.second == head.second) {
		return (if (this.first > head.first) this.first - 1 else this.first + 1) to this.second
	} else {
		return (if (this.first > head.first) this.first - 1 else this.first + 1) to if (this.second > head.second) this.second - 1 else this.second + 1
	}
}

private const val test = """R 4
U 4
L 3
D 1
R 4
D 1
L 5
R 2"""

private const val test2 = """R 5
U 8
L 8
D 3
R 17
D 10
L 25
U 20"""

private const val input =
	"""R 2
L 2
D 2
U 2
R 2
D 2
L 2
D 2
U 2
L 2
D 1
R 1
D 2
R 2
U 1
R 1
U 2
R 1
L 2
D 2
L 1
U 1
L 1
D 1
R 1
L 2
U 2
R 2
U 1
R 2
L 2
D 1
U 1
D 2
L 1
U 1
L 1
D 1
U 1
D 1
L 2
D 2
U 2
L 2
U 1
R 2
D 2
L 1
R 1
U 1
R 1
L 1
U 2
D 1
U 2
R 1
U 1
R 2
D 2
R 2
U 2
D 2
U 2
L 1
D 2
R 1
L 2
D 2
R 2
L 2
U 2
L 2
R 1
D 1
R 1
L 2
D 1
L 2
R 1
U 1
R 1
U 1
L 2
U 1
D 2
R 1
L 1
D 1
R 1
L 2
R 2
L 2
R 1
L 1
D 1
L 1
R 1
D 2
U 1
D 2
R 1
D 1
U 1
L 1
R 1
D 2
R 2
L 2
R 1
L 1
R 1
U 3
L 2
R 3
L 1
R 1
L 2
D 1
U 3
L 1
R 3
U 1
L 2
U 2
D 2
R 2
D 1
L 2
U 1
R 1
L 3
R 2
L 3
R 2
L 2
D 2
U 3
R 2
L 1
R 2
U 1
D 2
U 3
D 1
U 3
L 1
R 3
D 2
R 1
L 2
D 1
L 1
D 3
U 2
L 3
R 1
U 3
L 1
R 2
U 3
D 2
U 3
L 3
R 1
L 2
R 2
D 3
L 1
D 3
R 3
L 1
U 1
D 1
L 3
D 1
U 2
D 3
U 3
L 1
U 2
D 1
R 3
D 1
R 1
L 2
U 1
R 1
L 1
U 3
D 3
U 3
R 1
D 3
U 1
L 2
R 2
U 2
R 1
D 3
L 1
D 2
U 2
R 2
D 2
R 3
L 2
R 1
L 3
D 3
R 1
L 1
U 3
R 1
D 3
R 3
D 2
U 2
R 2
D 2
U 3
D 2
R 1
U 2
L 3
D 1
L 2
U 1
D 1
U 4
R 4
U 4
D 4
U 3
D 1
R 4
L 1
D 2
R 3
U 1
R 2
D 2
U 4
R 3
D 2
L 1
U 4
D 3
U 1
D 4
L 2
U 3
D 4
R 3
L 2
D 4
L 2
R 3
U 2
R 2
U 1
L 3
R 3
L 3
U 4
R 4
U 2
R 3
U 1
L 3
D 4
L 4
R 4
D 3
L 4
R 1
U 4
D 3
R 3
U 1
L 4
U 2
L 2
D 4
U 3
R 1
U 2
D 4
U 4
D 4
U 1
L 4
R 3
U 2
R 1
L 4
D 4
U 3
R 2
L 2
U 3
L 1
R 1
L 1
U 4
L 1
R 3
U 1
R 1
D 2
R 2
L 4
D 1
L 2
R 1
D 1
L 3
D 3
U 4
R 2
L 4
U 2
L 1
R 3
U 3
L 2
R 2
D 2
R 3
U 4
L 1
U 3
L 3
U 1
R 1
L 2
D 3
L 5
D 2
U 2
D 4
R 2
L 3
U 3
R 1
U 4
D 1
R 2
U 1
L 5
R 4
D 5
R 5
D 2
U 2
L 5
D 2
U 3
R 2
L 4
D 5
L 4
R 4
U 5
R 2
U 5
L 1
D 2
L 3
U 4
D 2
U 2
L 3
R 4
U 4
R 5
L 1
D 2
U 4
D 5
L 5
R 4
U 3
R 2
U 5
L 3
U 5
R 3
U 2
R 2
D 3
R 2
L 2
D 4
R 4
U 3
R 3
D 5
R 2
U 3
L 5
R 1
U 5
D 4
R 3
D 5
U 1
R 4
L 5
D 1
U 3
L 4
U 3
R 3
D 5
U 5
D 5
L 5
U 4
D 5
L 3
R 3
D 4
U 2
L 5
R 1
U 5
L 4
U 4
D 5
R 4
L 1
U 2
D 2
L 1
R 2
D 4
R 5
L 3
R 4
D 4
L 4
R 2
L 1
D 3
L 3
R 2
D 3
R 5
D 2
U 4
D 5
L 1
U 3
D 3
U 6
L 1
R 1
L 4
R 6
L 1
R 1
D 2
U 6
R 1
U 3
R 6
U 1
R 1
L 3
D 5
R 6
L 6
R 1
U 2
R 1
L 5
R 5
D 6
R 4
D 4
R 1
U 6
R 4
U 1
R 5
U 3
L 5
U 1
R 5
L 5
D 5
R 3
L 5
D 3
L 2
U 3
R 1
U 1
D 4
R 4
L 2
U 3
L 1
U 5
L 5
D 4
R 6
U 6
L 5
U 3
R 3
D 1
U 6
R 2
L 4
R 2
L 5
U 3
D 1
U 3
R 1
D 1
L 3
U 6
L 5
U 2
L 3
D 1
L 3
U 6
L 4
D 3
R 4
D 1
L 4
U 1
R 6
D 6
R 5
D 4
R 4
D 4
U 6
D 4
L 3
R 4
L 5
R 1
D 6
U 6
D 2
R 1
L 6
U 6
L 5
D 6
U 4
R 4
D 3
U 5
D 6
U 7
L 5
U 7
R 6
U 1
L 6
U 1
R 2
D 7
R 4
U 1
R 6
L 6
D 4
L 4
U 4
R 1
D 7
L 7
D 7
L 5
D 1
L 1
U 2
R 5
D 5
L 3
U 5
D 6
L 4
R 1
U 6
L 3
D 6
L 7
D 6
R 3
U 7
R 1
D 6
R 3
U 7
D 5
U 1
L 4
U 3
D 3
U 3
R 1
L 2
R 2
L 1
U 3
D 5
U 7
D 1
U 7
L 4
D 3
U 4
R 6
D 2
L 5
R 7
L 5
R 1
U 6
R 7
U 4
D 3
U 1
L 1
D 1
U 6
L 1
U 1
R 7
L 4
D 1
U 2
R 7
L 7
R 5
U 4
R 2
L 7
U 6
R 5
L 1
R 3
U 7
D 7
L 4
R 1
U 4
R 1
L 7
D 4
L 5
D 7
U 4
L 5
R 6
U 1
L 4
R 6
D 2
L 1
D 2
U 4
L 5
U 5
D 4
U 7
L 2
D 3
U 5
R 7
D 1
R 7
D 6
U 4
R 3
D 5
U 5
D 8
R 7
L 7
R 1
D 5
L 3
R 1
U 3
R 6
D 5
R 6
L 5
D 7
L 5
R 2
D 1
R 7
L 1
D 3
R 8
L 5
U 8
R 6
U 4
D 2
U 4
D 5
U 7
D 5
U 2
D 3
U 1
R 4
L 2
R 4
U 7
R 8
D 2
U 3
R 7
D 2
U 1
D 6
R 4
L 4
R 3
D 8
R 8
U 7
L 3
U 7
D 1
U 6
R 8
L 1
R 1
D 8
U 7
L 3
D 4
L 4
R 2
L 6
D 6
L 4
R 7
D 8
L 8
U 8
R 2
L 6
U 5
D 2
L 5
U 1
L 6
D 6
U 7
L 2
U 5
R 6
D 5
L 8
U 8
R 1
U 2
L 3
D 1
L 3
U 4
D 3
L 6
R 9
L 9
U 9
R 1
D 4
U 1
L 3
R 7
U 7
R 1
U 1
R 2
D 4
U 8
L 7
R 3
U 8
L 1
R 1
D 7
U 3
L 3
U 8
D 3
L 1
D 6
L 3
U 4
D 3
U 3
L 3
D 5
L 6
U 9
L 1
U 2
L 3
R 1
L 9
D 2
U 1
L 3
R 9
L 8
R 2
L 7
D 4
L 4
R 2
L 4
R 8
D 4
L 2
D 5
R 8
U 6
L 9
D 1
L 6
R 9
D 4
L 5
U 5
D 1
U 3
L 4
U 2
L 2
R 2
L 1
R 7
L 4
D 4
U 4
L 1
R 2
D 6
L 1
U 8
D 7
R 5
D 7
R 7
L 8
U 8
L 5
D 7
U 2
D 2
R 1
U 2
L 1
R 1
L 2
D 1
U 9
L 9
U 9
R 1
U 3
R 7
U 8
R 1
L 7
D 1
U 7
R 9
D 8
R 2
D 5
L 5
D 2
L 6
U 6
R 1
L 1
D 2
R 4
L 3
U 2
R 5
L 3
R 6
U 8
R 1
U 1
R 7
D 10
R 2
D 4
R 3
L 5
D 1
U 8
R 1
U 4
D 6
L 5
U 8
D 6
L 6
R 4
L 9
R 5
U 6
L 8
U 6
L 10
D 4
U 6
L 8
U 3
R 3
L 6
U 1
R 9
D 8
U 9
R 5
U 10
R 8
U 9
L 7
R 4
D 7
U 3
L 5
R 3
D 9
L 9
U 6
R 10
L 2
D 7
U 8
D 4
L 3
U 4
R 2
L 10
D 4
U 10
R 7
D 5
R 7
U 3
L 10
R 8
L 7
D 3
L 6
R 1
L 2
U 1
R 1
U 8
R 5
L 9
R 9
L 1
D 4
R 6
U 7
L 7
R 3
U 4
D 2
U 8
L 5
D 3
L 6
D 7
L 2
U 1
R 6
L 8
D 9
R 3
U 4
D 8
L 5
R 9
L 1
U 7
L 5
D 4
U 5
L 4
R 4
L 3
U 11
D 1
L 10
U 6
L 5
D 3
U 8
D 11
L 8
R 2
U 5
L 9
D 3
L 11
R 2
U 5
L 7
D 11
R 8
U 1
L 10
R 10
L 9
R 9
L 8
R 7
D 3
U 6
R 11
U 8
D 4
L 9
U 3
D 5
L 4
R 5
D 7
L 5
U 10
D 8
L 3
D 2
U 9
D 6
L 3
U 3
D 8
U 4
R 1
L 9
U 4
L 5
D 10
L 11
U 6
D 8
L 5
R 9
L 2
U 2
L 10
R 5
U 6
L 7
R 7
U 9
D 6
R 7
D 8
U 7
R 6
L 2
D 6
R 8
L 5
R 1
L 10
R 8
U 11
R 10
L 10
R 10
L 4
U 4
D 9
U 8
R 5
D 7
U 7
L 6
D 4
L 9
R 2
U 8
D 2
L 2
D 2
U 6
L 2
R 9
U 10
D 11
U 3
R 9
U 1
L 11
R 7
L 4
R 5
U 10
L 3
R 10
L 10
D 2
L 9
D 9
L 6
D 11
R 10
L 2
R 4
D 2
R 4
D 8
L 3
U 10
R 4
L 2
U 1
L 3
R 1
L 2
R 3
D 2
L 2
D 3
R 5
U 10
L 12
R 5
D 5
U 9
L 9
D 2
L 8
U 2
L 11
U 5
L 8
U 7
R 4
U 10
D 4
L 5
R 3
D 8
R 12
L 5
U 9
L 10
R 5
U 10
R 1
L 5
U 6
D 7
L 12
D 2
R 12
L 1
U 11
D 8
R 12
L 8
U 3
R 9
L 8
D 2
L 10
D 10
R 4
D 2
R 11
U 4
R 10
U 7
L 7
D 5
U 5
R 9
D 10
L 10
U 1
D 11
U 4
D 5
U 5
D 8
U 2
D 4
R 4
L 5
U 10
D 12
R 9
L 11
R 9
L 1
D 9
L 11
D 12
U 4
R 7
D 1
U 3
L 4
U 9
R 12
D 1
L 7
U 7
D 6
U 1
R 3
L 7
U 5
L 2
D 10
R 12
L 3
U 7
D 10
L 5
R 1
U 9
L 1
D 11
R 5
L 2
D 1
U 3
R 2
L 3
U 5
L 3
D 5
R 10
L 7
R 12
U 4
D 3
R 3
L 2
R 7
U 4
D 9
U 7
D 1
R 9
L 2
U 6
R 5
D 3
U 7
R 12
L 10
D 11
L 8
U 12
D 13
U 9
D 5
U 4
R 2
L 3
U 13
R 4
L 9
U 4
L 3
U 9
R 1
D 6
U 4
D 3
U 5
R 5
L 11
R 8
D 1
U 4
D 10
R 5
D 10
U 3
D 4
R 1
U 3
R 13
L 6
D 8
R 12
L 4
U 2
L 13
D 11
L 4
U 8
L 10
R 2
D 8
R 11
L 2
D 8
R 8
L 10
U 10
L 4
D 9
L 7
D 11
L 10
U 13
L 6
U 7
D 8
L 3
R 10
L 14
U 13
L 11
D 5
R 8
U 2
D 9
L 14
U 7
R 4
U 1
D 8
U 8
D 9
L 2
D 7
R 1
D 9
R 2
U 4
D 8
L 9
R 6
L 2
R 11
D 6
L 5
U 8
L 4
R 3
D 5
L 3
U 9
R 3
U 1
D 7
R 1
L 10
U 1
L 8
U 11
D 8
U 12
R 9
L 5
D 10
L 2
R 8
D 10
R 6
D 1
L 11
D 8
R 7
L 14
D 12
L 11
R 11
U 9
R 12
D 10
L 12
R 4
L 8
D 2
R 3
L 14
R 7
U 10
R 1
L 6
R 4
D 11
L 13
R 12
U 4
L 12
U 10
D 8
R 10
D 9
R 13
L 2
U 2
D 7
U 7
R 3
D 3
R 13
U 8
R 10
U 13
D 14
R 11
D 7
R 2
U 5
D 2
L 6
U 14
L 10
R 9
U 11
R 12
D 5
L 11
R 12
U 11
R 8
L 2
D 14
U 3
D 9
U 5
L 4
U 5
L 6
D 3
L 1
R 10
L 4
D 12
U 15
L 5
D 11
L 15
D 10
L 14
U 1
L 14
D 6
R 6
U 9
R 1
L 7
D 11
U 12
D 2
R 7
L 2
D 13
U 13
R 6
L 3
D 3
R 11
U 3
D 3
U 11
L 10
U 7
R 7
D 9
U 10
R 11
U 12
D 11
R 11
U 2
R 2
D 9
R 12
D 1
L 11
R 1
U 2
R 14
L 4
R 1
D 12
R 7
U 12
L 2
U 5
D 7
R 15
D 5
L 9
D 7
R 10
U 12
D 10
R 11
D 5
U 10
R 2
U 11
R 3
U 6
D 14
U 11
D 5
L 8
D 6
L 2
U 2
L 14
R 8
U 15
L 10
D 1
R 4
L 8
D 7
L 15
U 10
D 14
U 9
L 7
R 13
U 11
R 15
L 11
R 2
L 11
R 14
L 1
D 10
L 2
U 7
L 9
D 12
R 2
L 4
U 4
R 9
L 6
R 13
D 1
U 13
R 7
D 3
R 14
L 12
D 15
R 16
L 7
R 2
U 3
R 9
U 10
D 6
U 7
L 11
D 12
L 16
R 12
D 10
U 16
D 9
U 14
L 14
U 11
D 14
L 14
D 10
L 3
D 10
U 6
D 11
L 8
U 4
D 1
U 5
D 5
L 4
U 8
R 3
D 12
U 4
R 8
D 6
U 8
D 2
U 12
L 6
D 12
R 7
D 6
U 7
D 12
L 3
R 2
L 12
R 13
U 16
L 6
D 8
U 13
R 14
D 4
U 7
D 1
R 4
D 13
R 10
D 7
R 11
L 6
U 6
R 7
L 8
D 2
L 11
U 3
L 12
U 4
D 11
U 8
D 10
U 1
R 12
U 1
L 15
R 15
D 2
L 8
D 13
L 3
R 8
U 14
R 5
U 3
D 15
U 7
D 1
L 6
D 8
U 13
R 6
L 6
D 3
L 9
D 17
U 8
R 16
L 6
D 9
U 3
L 10
R 13
L 14
U 8
R 7
U 12
D 14
R 1
D 3
L 11
R 8
D 9
R 17
D 5
R 17
U 8
L 10
D 7
U 4
D 16
L 9
D 1
L 16
R 7
L 1
R 11
U 10
R 2
U 10
L 15
U 10
R 2
D 11
U 12
L 15
U 4
D 2
R 4
U 2
L 11
R 16
U 10
R 4
D 9
U 7
D 2
R 10
D 14
L 10
U 9
R 7
D 3
R 7
L 3
U 15
D 13
L 17
R 12
U 13
D 16
U 13
R 13
U 14
L 16
U 7
D 2
R 11
U 17
D 9
R 12
U 16
L 11
R 3
U 9
L 6
D 2
U 1
D 7
L 1
U 7
D 8
U 11
L 4
R 6
L 2
U 12
L 13
U 5
L 17
R 16
D 10
U 12
L 7
R 4
U 8
D 17
R 13
L 2
D 5
L 1
R 2
D 16
U 9
D 15
L 8
U 14
R 9
D 18
U 16
L 17
U 9
D 11
U 17
R 8
D 17
U 14
D 8
U 8
R 8
U 14
R 5
L 1
R 3
D 5
U 10
R 16
U 18
D 16
U 11
D 18
U 13
L 11
D 2
R 16
D 15
L 9
D 12
R 11
L 8
U 8
R 10
L 2
D 6
L 5
D 9
L 3
D 1
U 18
D 12
U 13
L 6
R 17
D 10
R 9
L 6
R 3
U 1
R 1
U 6
L 15
U 8
D 15
U 14
R 10
L 6
U 1
L 12
R 9
D 13
U 1
L 16
U 16
L 13
R 4
U 3
D 11
L 12
R 11
U 17
R 18
L 4
R 6
L 18
D 10
L 16
R 2
D 4
R 14
D 11
L 12
R 7
L 9
U 12
D 12
R 4
L 1
D 14
R 14
L 3
U 2
L 6
R 7
D 6
U 18
L 17
U 12
R 12
L 5
D 13
R 7
D 8
L 16
D 13
U 4
D 3
R 16
L 9
U 8
D 15
R 8
L 12
R 5
L 1
U 11
D 11
L 10
U 7
D 6
L 15
D 9
R 10
D 6
U 14
L 7
U 19
R 17
L 12
U 1
L 9
R 17
D 12
U 3
L 15
R 16
D 15
R 15
L 1
U 16
R 19
D 9
L 16
D 12
R 8
L 2
D 16
L 17
U 16
D 9
L 9
U 8
L 9
R 16
L 3
D 8
U 7
D 10
U 17
R 2
D 16
R 6
U 9
R 4
L 17
D 10
U 10
L 14
D 9
R 8
L 9
R 18
U 13
L 16
R 2
U 16
L 11
U 4
L 13
R 8
L 19
U 4
D 10
R 10
U 14
R 13
L 17
U 17
R 12
D 18
R 2
D 5
L 12
U 6
D 7
R 9
L 13
D 15
R 9
U 16
D 14
R 8
L 8
U 10
L 8
D 18
U 8
D 9
L 6
R 8
U 4
D 14
L 13
D 4
R 3
U 13
L 2"""
