package adventOfCode

import kotlin.system.measureTimeMillis

data class Cart(var x: Int, var y: Int, var dir: Char, var isDead: Boolean = false) {
    var turnCount = 0
    fun move(trackSection: Char) {
        when (trackSection) {
            '+' -> makeTurn()
            '\\' -> if (dir == '<' || dir == '>') right() else left()
            '/' -> if (dir == '<' || dir == '>') left() else right()
        }
        when (dir) {
            '^' -> y--
            '>' -> x++
            'v' -> y++
            '<' -> x--
        }
    }

    fun right() {
        dir = turnRight[dir]!!
    }

    fun left() {
        dir = turnLeft[dir]!!
    }

    fun makeTurn() {
        turnCount = (turnCount + 1) % turns.length
        when (turns[turnCount]) {
            'r' -> right()
            'l' -> left()
        }
    }

    fun collidedWith(other: Cart) = (x == other.x) && (y == other.y)

    fun position() = x to y

    companion object {
        val turns = "rls"
        val turnRight = mapOf<Char, Char>('>' to 'v', 'v' to '<', '<' to '^', '^' to '>')
        val turnLeft = mapOf<Char, Char>('>' to '^', 'v' to '>', '<' to 'v', '^' to '<')
    }
}

fun findCollisions(tracks: Array<Array<Char>>, carts: List<Cart>) = sequence {
    val movingCarts = carts.map { it.copy() }.toMutableList()
    while (movingCarts.size > 1) {
        movingCarts.sortWith(compareBy({ it.y }, { it.x }))
        movingCarts.forEach { cart ->
            if (!cart.isDead) {
                cart.move(tracks[cart.y][cart.x])
                if (movingCarts.collisonOccurred(cart)) {
                    movingCarts.forEach { if (it.collidedWith(cart)) it.isDead = true }
                    yield(cart.position())
                }
            }
        }
        movingCarts.removeIf { it.isDead }
    }
    // Output Position of Final Cart as a Collision
    yield(movingCarts[0].position())
}

fun List<Cart>.collisonOccurred(cart: Cart): Boolean = this.count { !it.isDead && it.collidedWith(cart) } > 1

fun solve(tracks: Array<Array<Char>>, carts: List<Cart>): Pair<Pair<Int, Int>, Pair<Int, Int>> {
    val collisions = findCollisions(tracks, carts)
    val firstCollision = collisions.first()
    val lastCollision = collisions.last()
    return firstCollision to lastCollision
}


fun main(args: Array<String>) {
    val time = measureTimeMillis {
        val (carts, tracks: Array<Array<Char>>) = parseLines(input)

        val (part1, part2) = solve(tracks, carts.toList())

        println("Part I: $part1")
        println("Part II: $part2")

    }
    println("Elapsed Time: ${time}ms")
}

private fun parseLines(lines: List<String>): Pair<MutableList<Cart>, Array<Array<Char>>> {
    val carts = mutableListOf<Cart>()
    val tracks: Array<Array<Char>> = lines.mapIndexed { y, line ->
        line.mapIndexed { x, c ->
            if (c in listOf('>', 'v', '<', '^')) {
                carts.add(Cart(x, y, c))
            }
            when (c) {
                'v' -> '|'
                '^' -> '|'
                '<' -> '-'
                '>' -> '-'
                else -> c
            }
        }.toTypedArray()
    }.toTypedArray()
    return Pair(carts, tracks)
}

val input = listOf(
    "                   /-----------\\                                                                                     /--------\\                       ",
    "     /-------------+-----------+----------------------------------------------------------------------\\              |        |                       ",
    "     |             |  /--------+------------------------------\\                                       |              |        |                       ",
    "     |           /-+--+--------+------------------------------+---------------------------------------+---------\\    |  /-----+---------------------\\ ",
    "   /-+-----------+-+--+--\\/----+-----------\\                  |                         /-------------+-\\       |    |  |     |                     | ",
    "   | |      /----+-+--+--++----+-----------+------------------+---------------------\\   |             | |       |    |  |     |                     | ",
    "   | |      |    | |  |  ||    |           |/-------------\\   |               /-----+---+-------------+-+-------+----+--+-----+--------------------\\| ",
    " /-+-+------+----+-+\\ |  ||    |           ||    /------<-+---+---------------+-----+---+-------------+-+-------+----+--+-->--+--------------------++\\",
    " | | |      |/---+-++-+--++----+-----------++--\\ |        |   |               |     |   |             | |       |    |  |     |                    |||",
    " | | |      ||   | ||/+--++----+-----------++--+-+--------+--\\|               |     |   |  /----------+-+-------+\\   |  |     |                    |||",
    " | | |      ||   | ||||  ||    |           || /+-+--------+--++---------------+-----+---+--+----------+-+\\      ||   |  |     |                    |||",
    " | | |      ||   | ||||  ||    |         /-++-++-+--------+--++---------------+-----+---+--+----------+-++-----\\||   |  |     |                    |||",
    " | | |      ||   | ||||  ||    |         | || || |     /--+--++---------------+-----+---+--+----------+-++-----+++---+--+-----+-----\\              |||",
    " | | |      ||   | ||||  ||    |         | || || |     |  |  ||               |     |   |  |          | ||     |||   |  |   /-+-----+\\             |||",
    " | | |      || /-+-++++--++----+---------+-++-++-+-----+--+--++---------------+----\\|   |  |          | ||     |||   |  |   | |     ||             |||",
    " | | | /----++-+-+-++++--++----+---------+-++-++-+-----+--+--++--------------\\|    ||  /+--+----\\     | ||/----+++---+--+---+-+-----++\\            |||",
    " | | | |  /-++-+-+-++++--++----+---------+-++-++-+-----+--+--++--------------++----++--++--+----+-----+-+++\\   |||   |  |   | |     |||            |||",
    " | | | |  | || | | ||||  ||    |         | || || |     |  |  ||            /-++----++--++--+----+----\\| ||||   |||   |  |   | |     |||            |||",
    " | | | |  | || | | ||||  ||    |         | || || |     |  |  ||            | ||    ||  ||  |/---+----++-++++---+++---+--+--\\| |     |||            |||",
    " | | | |  | || | | ||||  ||    |         |/++-++-+-----+--+--++------\\     | ||    ||  ||  ||   | /--++<++++---+++---+--+--++-+-----+++------\\     |||",
    " | | | |/-+-++-+-+-++++--++----+---------++++-++-+-----+--+--++----\\ |     | ||    ||  ||  ||   | |  || ||||   |||   |  |  || | /---+++------+--\\  |||",
    " | | | || |/++-+-+-++++--++----+---------++++-++-+-----+--+--++----+-+-----+-++----++--++--++---+-+--++-++++---+++---+-\\|  || | |   |||      |  |  |||",
    " | | | || |||| | | ||||  ||    |         |||| || |     |  |  ||    | |     | ||    ||  ||  ||   | |  || ||||   |||   \\-++--++-/ |   |||      |  |  |||",
    " | | | || |||| | | ||||  ||    |         |||| || \\-----+--+--++----+-+-----+-++----++--++--++---+-+--++-++++---+++-----++--++---+---+++------+--+--++/",
    " | | | || |||| |/+-++++--++----+\\        |||| ||       | /+--++----+-+-----+-++\\   ||  ||  ||   | |  || ||||   |||     ||  ||   |   |||      |  |  || ",
    " | | | || |||| ||| ||||  ||    ||        |||| ||       | ||  ||    | |     | |||   ||  ||  ||   | |  || ||||   |||     ||  ||   |   |||      |  |  || ",
    " | | | \\+-++++-+++-++++--++----++--------++++-++-------+-++--++----+-+-----+-/||   ||  ||  || /-+-+--++-++++---+++-----++--++---+\\  |||      |  |  || ",
    " | | |  | |||| ||| ||||  ||    ||   /----++++-++-------+-++--++--\\ | |     |  ||   ||  ||  || | | |  || ||||   |||     ||  ||   ||  |||      |  |  || ",
    " | | \\--+-++++-+++-++++--++----++---+----++++-++-------+-++--++--+-+-+-----+--++---++--++--++-+-+-+--+/ ||||   |||     ||  ||   ||  |||      |  |  || ",
    " | |    |/++++-+++-++++--++----++\\  |/---++++-++-------+-++--++--+-+-+-----+--++\\  ||  |\\--++-+-+-+--+--/|||   |||     ||  ||   \\+--+++------+--/  || ",
    " | |    |||||| ||| ||||  ||    |||  ||   |||| ||       | ||  ||  | | |     \\--+++--++--+---++-+-+-+--/   |\\+---+++-----++--++----+--++/      |     || ",
    " | |    ||||\\+-+++-++++--++----+++--++---++++-++-------+-++--++--+-+-+--------+++--+/  |/--++-+-+-+------+-+---+++-----++--++\\   |  ||       |     || ",
    " | |    |||| | ||| ||||  ||    |||  ||   |||| ||       | ||  ||  | | |        |||  |   ||  || | | \\------+-+---+++-----++--+++---+--++-------/     || ",
    " | |    |||| | ||| ||||  ||    |||  ||   |||| ||   /---+-++--++--+-+-+---\\    |||  |   ||  \\+-+-+--------+-+---++/     ||  |||  /+--++------------\\|| ",
    " | |    |||| | ||| ||||/-++----+++--++---++++-++---+---+-++--++--+-+-+---+----+++--+---++---+-+-+--------+-+---++---\\  ||  |||  ||  ||            ||| ",
    " | |    |||| | ||| ||||| ||    |||  ||   |||| ||   |   | ||  ||  | | |   |    |||  |   ||   | | |        | |   ||   |  ||  |||  ||  ||            ||| ",
    " | |    |||| | ||| ||||| ||    |||  ||   |||| ||   |   | ||  ||  | | |   |    |||  |   ||   | | |        | |   ||   |  ||  |||  ||  ||            ||| ",
    " | |    |||| | ||| ||||| ||/---+++--++---++++-++---+---+-++--++--+-+-+---+----+++--+---++---+-+-+--------+-+-\\ ||   |  ||  |||  ||  ||            ||| ",
    " | |    |||| | ||\\-+++++-+++---+++--++---++++-++---+---+-++--++--+-+-+---+----+++--+---++---+-+-+--------+-+-+-+//--+--++--+++--++-\\||            ||| ",
    " | |    |||| | ||  \\++++-+++---/||  ||   |||| || /-+---+-++--++--+-+-+---+----+++--+---++---+-+-+--------+-+-+-+-+\\ |  ||  |||  || |||            ||| ",
    " | |    |\\++-+-++---++++-+++----+/  ||  /++++-++-+-+---+-++--++--+-+-+---+----+++--+---++---+-+-+--------+-+-+\\| || |  ||  |||  || |||            ||| ",
    " | |    | || | ||   |||| |||    |   ||  ||||| || | |   | ||  ||  | | |   |    |||  |   ||   | | |/-------+-+-+++-++-+--++--+++--++-+++---\\        ||| ",
    " | |    \\-++-+-++---++++-+++----+---++--+++++-++-+-+---+-++--++--+-/ |   |    ||| /+---++---+-+-++-------+-+-+++-++-+\\ ||  |||  || |||   |        ||| ",
    " | |      || | ||   |||| |\\+----+---++--+++/| || | |   | \\+--++--+---+---+----+/| ||   ||   | | ||       | | ||| || || ||  |||  || |||   |        ||| ",
    " | |      || | || /-++++-+-+----+---++--+++-+-++-+-+---+--+--++--+---+---+----+\\| ||   |\\---+-+-++-------+-+-+++-++-++-++--++/  || |||   |        ||| ",
    " | |      || | ||/+-++++-+-+----+---++--+++-+-++-+-+---+--+--++--+---+---+---\\||| ||   |    | | ||       | | ||| || || ||  ||   || |||   |        ||| ",
    " | |      || | |||| |\\++-+-+----+---++--+++-+-++-+-+---+--+--/|  |   | /-+---++++-++---+----+-+-++-------+-+-+++-++-++-++--++---++-+++---+--\\     ||| ",
    " | |/-----++-+-++++-+-++-+-+----+---++--+++-+-++-+-+---+--+---+--+\\/-+-+-+---++++-++---+----+-+-++--\\    | | ||| || || ||  ||   || |||   |  |     ||| ",
    " | ||     || | |||| | || | |    |   ||  ||| | || | |   |  |   |  ||| | | |   |||| ||   |    |/+-++--+----+-+-+++-++-++-++--++---++-+++---+--+-\\   ||| ",
    " | ||     || v |||| | \\+-+-+----+---++--+++-+-++-+-+---+--+---/  ||| | | |   |||| ||   | /--+++-++--+----+-+-+++-++-++-++--++---++-+++---+-\\| |   ||| ",
    " | ||     || | |||| |  | | |    |   ||  ||| | || | |   |  |      |||/+-+-+---++++-++---+-+--+++-++--+----+-+-+++-++-++-++-\\||   || |||   | || |   ||| ",
    " | ||     || | |||| |  | | |    |   ||  ||| | || | |   | /+------+++++-+-+---++++-++---+-+--+++-++--+-->-+-+-+++-++-++-++-+++---++-+++---+-++-+---+++\\",
    " | ||     || | |||| |  | | |    |   ||  ||| | || | |   | ||     /+++++-+-+---++++-++---+-+--+++-++--+----+-+-+++-++-++-++-+++--\\|| |||   | || |   ||||",
    " | ||     || | |||| |  | | | /--+---++--+++-+-++-+-+---+-++-----++++++-+\\|   |||| ||   | |  ||| ||  |    | | ||| || || || |||  ||| |||   | || |   ||||",
    " | ||/----++-+-++++\\|  |/+-+-+--+---++--+++-+-++-+-+---+-++-----++++++-+++---++++\\||   | |  ||| ||  |    | | ||| || || || |||  ||| |||   | || |   ||||",
    " | |||    ||/+-++++++--+++-+-+--+---++--+++-+-++-+-+---+-++-----++++++-+++---+++++++---+-+--+++-++--+-\\  | | ||| || || || |||  ||| |||   | || |   ||||",
    " | |||   /++++-++++++--+++-+-+--+---++--+++-+-++-+-+---+-++-----++++++-+++---+++++++---+-+--+++-++--+\\|  | | ||| || || || |||  ||| |||   | || |   ||||",
    " | |||   ||||| ||||||  ||| | |  |   ||  ||| \\-++-+-+---+-+/     |||||| |||   |||||||   \\-+--+++-/|  |||  | | ||| || || || |||  ||| |||   | || |   ||||",
    " | |||  /+++++-++++++--+++-+\\|  |   ||  |||   || | |   | |      |||||| |||   |||||||     |  |||  |  |||  | | ||| || || || |||  ||| |||   | || |   ||||",
    " | |||  |||||| ||||||  ||| |||  |   ||  |||   || | |   | |  /---++++++-+++---+++++++-----+--+++--+--+++--+-+-+++-++-++-++-+++--+++-+++---+-++-+-\\ ||||",
    " | |||  |||||| |||\\++--+++-+++--+---++--+++---++-+-+---+-+--+---++++++-+++---++/||||     |  |||  |  |||  | |/+++-++-++-++-+++--+++-+++---+-++-+\\| ||||",
    " | \\++--++++++-+++-++--++/ |||  |   ||  |||/--++-+-+---+-+-\\|   |||\\++-+++---++-++++-----+--+++--+--/||  | ||||| || || || |||  ||| |||   | || ||| ||||",
    " |  ||  |||||| ||| ||  ||  |||/-+---++--++++--++-+-+---+-+-++---+++-++-+++---++-++++-----+--+++--+---++\\ | ||||| || || || |^|  ||| |||   | || ||| ||||",
    " |  ||  |||||| ||| ||  ||  |||| |   ||  ||||  || | |   | | ||   ||| || |||   || ||||/----+--+++--+---+++-+-+++++-++-++-++-+++--+++-+++--\\| || ||| ||||",
    " |  ||  |||||| ||| ||  ||  |||| |   ||  ||||  || | |   |/+-++---+++-++-+++---++-+++++----+-\\|||  |   ||| | ||||| || || || |||  ||| |||  || || ||| ||||",
    " |  ||  |||||| ||| ||  ||  |||| |   \\+--++++--++-+-+---+++-++---+/| || |||  /++-+++++----+-++++-\\|   ||| | ||||| || || || |||  ||| |||  || || ||| ||||",
    " |  ||  |||||| ||| ||  ||  |||| |    |  ||||  || | |   ||| ||   | | || |||  ||| |||||    | |||| ||   ||| | ||||| \\+-++-++-+++--+++-/||  || || ||| ||||",
    " |  ||  |||||| ||| ||  ||  |||| |    |  ||||  || | |   ||| ||   | | || |||  ||| |||||    | |||| ||   ||| | |||||  | || || |||  |||  ||  || || ||| ||||",
    " |  ||  |||||| ||| ||  ||  |||| |  /-+--++++--++-+-+---+++-++---+-+-++-+++--+++-+++++----+-++++-++---+++-+-+++++--+-++-++-+++--+++--++\\ || || ||| ||||",
    " |  ||  |||||| ||| ||  |\\--++++-+--+-+--++++--++-+-+---+++-++---+-+-++-+++--+++-+/|||    | |||| ||   ||| | |||||  | || || |||  |||  ||| || || ||| ||||",
    " |  ||  |||||| ||| ||  |   |||| |  | |  ||||  || | |   |||/++---+-+\\|| |||  ||| | |||    | |||| ||   ||| | |||||  | || || |||  |||  ||| || || ||| ||||",
    " |  ||  |||||| ||| ||  |   |||| |  | |  ||||  || | |   ||\\+++---+-++++-+++--+++-+-+++----+-++++-++---+++-+-+++++--+-++-++-+++--+++--+++-++-++-+++-+++/",
    " |  ||  |||||| ||| ||  |   |||| |  | |  ||||  || | |   || |||   | |||| |||  ||| | |||    | |||| ||   ||| | |||||  | || || |||  |||  ||| || || ||| ||| ",
    " |  ||  |||||| ||| ||  |   |||| |  | |  ||||  || | |   || |||   | ||\\+-+++--+++-+-+++----+-++++-++---+++-+-+++++>-+-++-++-/||  |||  |^| || || ||| ||| ",
    "/+--++--++++++-+++-++--+---++++-+--+-+--++++--++\\| |   || |||   | || | |||  ||| | |||    | |||| ||   ||| | |||||  | || ||  ||  |||  ||| || || ||| ||| ",
    "||  ||  ||||||/+++-++--+---++++-+--+-+--++++--++++-+-\\ || |||   | || | |||  ||| | |||    | |||| ||   ||| | |||||  | || ||  ||  |||  ||| || || ||| ||| ",
    "||  ||  |||||||||| ||  |   |||| |  | |  ||||  |||| | | || |||   | || | |||  ||| | |||    | |||| |\\---+++-+-+++++--+-++-++--++--+++--+++-+/ || ||| ||| ",
    "||  || /++++++++++-++--+---++++-+--+-+--++++\\ |||| | | || |||   | || | |||  ||| | |||    | |||| |    ||| | |||||  | || ||  ||  |||  |||/+--++-+++\\||| ",
    "||  || ||||||||||| ||  |   |||| |  | |  ||||| |||| | | || |||   | ||/+-+++--+++-+-+++----+-++++-+----+++-+-+++++--+\\|| ||  ||  |||  |||||  || ||||||| ",
    "|| /++-+++++++++++-++--+---++++-+--+\\|  ||||| |||| | | || |||   | |||| |||  ||| | |||    | |||| |    ||| | |||||  |||| ||  || /+++--+++++\\ || ||||||| ",
    "|| ||| ||||||||||| ||  |   |||| |  |||  ||||| |||| | | || |||   | |||| \\++--+++-+-+++----+-++++-+----+++-+-+++++--++++-++--++-++++--++++++-+/ ||||||| ",
    "|| ||| ||||||||||| ||  |   |||| |  |||  ||||| |||| | | || |||   | ||||  ||/-+++-+-+++----+-++++-+----+++-+-+++++--++++-++--++-++++-\\|||||| |  ||||||| ",
    "|| ||| ||||||||||| ||  |   ||\\+-+--+++--+++++-++++-+-+-++-+++---+-++++--/|| ||| | |||    | |||| |    ||| | |||||  |||| ||  || |||| ||||||| |  ||||||| ",
    "|| ||| ||||||||\\++-++--+---++-+-+--+++--+++++-++++-+-+-++-+++---+-++++---++-+++-+-+/|    | |||| |    ||| | |||||  |||| ||  || |||| ||||||| |  ||||||| ",
    "|| ||| |||||||| || ||  |   || | |  |||  ||||| |||| | | || |||   | ||||   || ||| | | |    | |||| |    ||| | |||||  |||| ||  || |||| ||||||| |  ||||||| ",
    "|| ||| |||||||| || ||  |   || | |  |||  ||||| |||| | | || |||/--+-++++---++-+++-+-+-+----+-++++-+----+++-+-+++++-\\|||| ||  || |||| ||||||| |  ||||||| ",
    "|| ||| |||||||| || ||  |  /++-+-+--+++--+++++-++++-+-+-++-++++--+-++++---++-+++-+-+-+----+-++++-+----+++-+-+++++-+++++-++\\ || |||| ||||||| |  ||||||| ",
    "|| ||| |||||||\\-++-++--+--+++-+-+--+++--+++++-++++-+-/ || ||||  | ||||   || ||| | | |    | |||| |    ||| | ||||| ||||| ||| || |||| ||||||| |  ||||||| ",
    "|| \\++-+++++++--++-++--+--+++-+-+--+/|  ||||| \\+++-+---++-++++--+-++++---++-+++-+-+-+----+-++++-+----+++-/ ||||| ||||| ||| || |||| ||||||| |  ||||||| ",
    "||  || |||\\+++--++-++--+--+++-+-+--+-+--+++++--+++-+---++-++++--+-++++---++-+++-+-+-+----+-++++-+----+++---/|||| ||||| ||| || ||\\+-+++++++-+--++++/|| ",
    "||  || ||| \\++--++-++--+--+++-+-+--+-+--+++++--+++-+---++-++++--+-++++---++-+++-+-+-+----+-++++-+----+++----++++-+++++-/|| || || | ||||||| |  |||| || ",
    "||  || |||  ||  || ||/-+--+++-+-+--+-+--+++++--+++-+---++-++++--+-++++---++-+++-+-+-+----+-++++-+----+++----++++\\|||||  || || || | ||||||| |  |||| || ",
    "\\+--++-+++--++--++-+++-+--+++-+-+--+-+--+++++--+/| |   || ||||  | ||||   || ||| | | |    | |||| |    |||    ||||||||||  || || || | ||||||| |  |||| || ",
    " |  || |||  ||  || ||| |  ||| | |  | |  |||||  | | |  /++-++++--+-++++---++-+++-+-+-+----+-++++-+--\\ |||    ||||||||||  || || || | ||||||| |  |||| || ",
    " |  || |||  ||  || ||| |  ||| | |  | |  |||||  | | |  ||| ||\\+--+-++++---++-+++-+-+-+----+-++++-+--+-+++----++++++++++--++-++-++-+-+++++++-+--++/| || ",
    " |  || |||  ||  || ||| |  |||/+-+--+-+--+++++--+-+-+--+++-++-+--+-++++---++-+++-+-+-+----+-++++-+--+-+++----++++++++++-\\|| || || | ||||||| |  || | || ",
    " |  || |||  |\\--++-+++-+--+++++-+--+-+--+++++--/ | |  ||| || |  | ||||   |\\-+++-+-+-+----+-++++-+--+-+++----++++++++++-+++-++-++-+-/|||||| |  || | || ",
    " |  || |||  |   || ||| |  \\++++-+--+-+--+++++----+-+--+++-++-+--+-++++---+--+++-+-+-+----+-++++-+--+-+++----++++++++++-++/ || || |  |||||| |  || | || ",
    " |  || |||  |   || ||| |   |||| |  | |  |||||    | |  ||| || |  | ||||   |  ||\\-+-+-+----+-++++-+--+-+++----++++++++++-++--++-++-+--++++++-+--++-+-/| ",
    " |  || |||  |   || ||| |   |||\\-+--+-+--+++++----+-+--+++-++-+--+-++++---+--++--+-+-+----+-++++-+--+-++/    |||||||||| ||  || || |  |||||| |  || |  | ",
    " |  || |||  |   || ||| |   |||  |  | |  |||||    | |  ||| || |  | ||||   |  ||  | | |    | |||| |  | ||     |||||||||| ||  || || |  |||||| |  || |  | ",
    " |  || |||  |   || ||| |   |||  |  |/+--+++++----+-+--+++-++-+--+-++++\\  |  ||  | | |    | |||| |  | ||     |||||||||| ||  || || |  |||||| |  || |  | ",
    " |  || |||  |   || ||| |   |||  |  |||  |\\+++----+-+--+++-++-+--+-+++++--+--++--+-+-+----+-++++-+--+-++-----+++/|||||| ||  || || |  |||||| |  || |  | ",
    " |  || |||  |   || ||| |   |||  |  ||\\--+-+++----+-+--+++-++-+--+-+++++--+--++--/ | |    | |||| |  | ||     \\++-++++++-++--++-++-+--++++++-+--+/ |  | ",
    " |  || |||  |   || ||| |   |||  |  ||   | |||    | |  ||| || |  | |||||  |  ||    | |    | |||| |  | ||      || |||||| ||  || || |  |||\\++-+--+--/  | ",
    " |  || |||  |   || ||| |   ||\\--+--++---+-+++----+-+--+++-++-+--+-+++++--+--++----+-+----+-++++-+--+-++------++-++++++-/|  || || |  ||| || |  |     | ",
    " |  || |||  |   || ||| |   ||   |  ||   | ||| /--+-+--+++-++-+--+-+++++--+--++----+-+----+-++++-+--+-++------++-++++++--+--++-++\\|  ||| || |  |     | ",
    " |  || |||  |   || ||| |   ||   |  ||   v ||| |  | |  |||/++-+--+-+++++--+--++---\\| |    | |||| |  | ||      || ||||||  \\--++-++++--+++-++-+--+-----/ ",
    " |  || ||\\--+---++-+++-+---++---+--++---+-+++-+--+-+--++++++-+--+-+++++--+--++>--++-+----+-++++-+--+-/|      || ||||||     || \\+++--+++-+/ |  |       ",
    " |  || ||   |   || ||| |   \\+---+--++---+-+++-+--+-+--++++++-+--+-+++++--+--++---++-+----+-++++-+--+--+-->---/| ||||||     ||  |||  ||| |  |  |       ",
    " | /++-++---+---++-+++-+----+---+--++-\\ \\-+++-+--+-+--++++++-+--+-+++++--+--++---++-+----+-++++-+--+--+-------/ ||||||     ||  |||  ||| |  |  |       ",
    " \\-+++-++---+---++-+/| |    |   |  || |   \\++-+--+-+--++++++-+--+-+++/|  |  ||   || \\----+-++++-+--+--+---------++++++-----++--+++--+++-/  |  |       ",
    "   ||| ||   |   || | | |    |   |  || |    || |  | |  |||||| |  | ||| |  |  ||   ||   /--+-++++-+--+--+-------\\ ||||||     ||  |||  |||    |  |       ",
    "   ||| ||   |   || | | |    |   |  || |    || |  \\-+--++++++-+--+-+++-+--+--++---++---+--+-++++-+--+--+-------+-++/|||     ||  |||  |||    |  |       ",
    "   ||| ||   |   || | | |    |   |  || | /--++-+----+--++++++-+--+-+++-+--+--++--\\||   |  | |||\\-+--+--+-------+-++-+++-----++--++/  |||    |  |       ",
    "   ||| ||   |   || | | |    |   |  || | |  || |    \\--++++++-+--+-+++-+--/  ||  |||   |  | |||  |  |  |       | || |||     |\\--++---+/|    |  |       ",
    " /-+++-++-\\ |   || | | |    |   |  || | |  || |       |\\++++-+--+-+++-+-----++--+++---+--+-+++--+--+--+-------+-++-+++-----+---++---/ |    |  |       ",
    " | ||| || | |   || | | |    |   |  || | |  \\+-+-------+-+++/ |  | ||| |     ||  |||   |  | |||  |  |  |       | || |||     |   ||     |    |  |       ",
    " | ||| || | |   || | | | /--+---+--++-+-+--\\| |       |/+++--+--+-+++-+-----++--+++---+--+-+++--+--+--+-------+-++-+++-----+---++-----+---\\|  |       ",
    " | ||| || | |   ^| | | | |  |   |  || | |  || |       |||||  |  | ||| |     ||  |||   |  | |\\+--+--+--+-------+-++-+++-----/   ||     |   ||  |       ",
    " | ||| || | |   || | \\-+-+--+---+--++-+-+--++-+-------+++++--+--+-+++-+-----++--+++---+--+-+-+--+--+--+-------+-/| |||         ||     |   ||  |       ",
    " | ||^ || | |   || |   | |  |   |  || | |  || |       |||||  |  | ||| |     ||  |||   |  \\-+-+--+--+--+-------+--+-+++---------++-----+---+/  |       ",
    " | ||| || | |   \\+-+---+-+--+---/  || | |  || |       ||||\\--+--+-+/| |     \\+--+++---+----+-+--/  |  |       |  | |||         ||     |/--+---+-----\\ ",
    " | ||| || | |    | |   | |  |      || | |  || |       ||||   |  | | | |      |  |||   |    | |     |  |       |  | |||         ||     ||  |   |     | ",
    " | ||| \\+-+-+----+-+---+-+--+------++-+-+--+/ |       ||||   \\--+-+-+-+------+--+++---+----+-+-----+--+-------+--/ |||         ||     ||  |   |     | ",
    " | |||  | | |    | |   | |  |      || | |  |  |     /-++++------+-+-+-+------+--+++---+----+-+-----+--+-------+----+++------\\  ||     ||  |   |     | ",
    " | |||  | | |    | |   | |  |      || | |/-+--+-----+-++++------+-+-+-+-\\    |  |||   |    | |     |  |       |    |||      |  ||     ||  |   |     | ",
    " | |||  | | |    \\-+---+-+--+------++-+-++-+--+-----+-++++------+-+-+-+-+----/  |||   |    | |     |  |       |    |||      |  ||     ||  |   |     | ",
    " | \\++--+-+-+------+---+-+--+------++-/ || |  |     | ||||      | | \\-+-+-------+++---+----+-+-----+--+-------+----/||      |  ||     ||  |   |     | ",
    " |  ||  | | |      |   | |  |      ||   || |  |     | ||||      | |   | |       |||   |    | |     |  |       |     ||      |  ||     ||  |   |     | ",
    " |  ||  | | \\------+---+-+--+------++---++-+--+-----+-++++------+-+---+-+-------+++---+----+-+-----+--/       |     ||      |  ||     ||  |   |     | ",
    " |  ||  | |        |   | |  |      ||   || |  |     | ||\\+------+-+---+-+-------+++---+----/ \\-----+----------+-----++------+--++-----++--+---/     | ",
    " |  ||  | |        |   \\-+--+------++---++-+--+-----+-++-+------+-+---+-+--->---+++---+------------+----------+-----/|      |  ||     ||  |         | ",
    " |  ||  | |        |     |  |      ||   || |  |     | |\\-+------+-+---+-+-------+++---+------------+----------+------+------+--++-----++--/         | ",
    " |  ||  | |        |     |  |      ||   || |  |     | |  \\------+-+---+-+-------+/|/--+------------+----------+------+----\\ |  ||     ||            | ",
    " |  |\\--+-+--------/     |  |      ||   || |  |     | |         | |   | |       | ||  |            |          |      |    | |  ||     ||            | ",
    " |  |   | |              |  | /----++---++-+--+-----+-+---------+-+---+-+->-----+-++--+------------+----------+------+----+-+--++--\\  ||            | ",
    " |  \\---+-+--------------+--+-+----++---++-+--+-----+-+---------+-/   | |       | ||  |            |          |      |    | |  ||  |  ||            | ",
    " |      | |              |  | |    ||   || |  |     | \\---------+-----+-+-------+-++--+------------/          |      |    | |  ||  |  ||            | ",
    " |      | |              |  | |    ||   \\+-+--+-----+-----------+-----+-+-------/ \\+--+-------->--------------+------/    | |  ||  |  ||            | ",
    " \\------+-/              |  | |    ||    | |  |     ^           \\-----+-+----------+--+-----------------------+-----------+-+--/|  |  ||            | ",
    "        |                |  | |    ||    | |  |     |                 | |          |  \\-----------------------/           | |   |  |  ||            | ",
    "        |                |  | |    |\\----+-+--+-----+-----------------/ |          |                                      | |   |  |  ||            | ",
    "        \\----------------+--/ |    |     | |  |     |                   |          |                                      | |   |  |  ||            | ",
    "                         \\----+----+-----+-/  |     \\-------------------+----------+--------------------------------------+-/   |  |  |\\------------/ ",
    "                              |    |     \\----+-------------------------/          \\--------------------------------------/     |  |  |               ",
    "                              |    |          \\---------------------------------------------------------------------------------/  |  |               ",
    "                              \\----+-----------------------------------------------------------------------------------------------/  |               ",
    "                                   \\--------------------------------------------------------------------------------------------------/               ",
    "                                                                                                                                                      "
)
package adventOfCode

import kotlin.system.measureTimeMillis

data class Cart(var x: Int, var y: Int, var dir: Char, var isDead: Boolean = false) {
    var turnCount = 0
    fun move(trackSection: Char) {
        when (trackSection) {
            '+' -> makeTurn()
            '\\' -> if (dir == '<' || dir == '>') right() else left()
            '/' -> if (dir == '<' || dir == '>') left() else right()
        }
        when (dir) {
            '^' -> y--
            '>' -> x++
            'v' -> y++
            '<' -> x--
        }
    }

    fun right() {
        dir = turnRight[dir]!!
    }

    fun left() {
        dir = turnLeft[dir]!!
    }

    fun makeTurn() {
        turnCount = (turnCount + 1) % turns.length
        when (turns[turnCount]) {
            'r' -> right()
            'l' -> left()
        }
    }

    fun collidedWith(other: Cart) = (x == other.x) && (y == other.y)

    fun position() = x to y

    companion object {
        val turns = "rls"
        val turnRight = mapOf<Char, Char>('>' to 'v', 'v' to '<', '<' to '^', '^' to '>')
        val turnLeft = mapOf<Char, Char>('>' to '^', 'v' to '>', '<' to 'v', '^' to '<')
    }
}

fun findCollisions(tracks: Array<Array<Char>>, carts: List<Cart>) = sequence {
    val movingCarts = carts.map { it.copy() }.toMutableList()
    while (movingCarts.size > 1) {
        movingCarts.sortWith(compareBy({ it.y }, { it.x }))
        movingCarts.forEach { cart ->
            if (!cart.isDead) {
                cart.move(tracks[cart.y][cart.x])
                if (movingCarts.collisonOccurred(cart)) {
                    movingCarts.forEach { if (it.collidedWith(cart)) it.isDead = true }
                    yield(cart.position())
                }
            }
        }
        movingCarts.removeIf { it.isDead }
    }
    // Output Position of Final Cart as a Collision
    yield(movingCarts[0].position())
}

fun List<Cart>.collisonOccurred(cart: Cart): Boolean = this.count { !it.isDead && it.collidedWith(cart) } > 1

fun solve(tracks: Array<Array<Char>>, carts: List<Cart>): Pair<Pair<Int, Int>, Pair<Int, Int>> {
    val collisions = findCollisions(tracks, carts)
    val firstCollision = collisions.first()
    val lastCollision = collisions.last()
    return firstCollision to lastCollision
}


fun main(args: Array<String>) {
    val time = measureTimeMillis {
        val (carts, tracks: Array<Array<Char>>) = parseLines(input)

        val (part1, part2) = solve(tracks, carts.toList())

        println("Part I: $part1")
        println("Part II: $part2")

    }
    println("Elapsed Time: ${time}ms")
}

private fun parseLines(lines: List<String>): Pair<MutableList<Cart>, Array<Array<Char>>> {
    val carts = mutableListOf<Cart>()
    val tracks: Array<Array<Char>> = lines.mapIndexed { y, line ->
        line.mapIndexed { x, c ->
            if (c in listOf('>', 'v', '<', '^')) {
                carts.add(Cart(x, y, c))
            }
            when (c) {
                'v' -> '|'
                '^' -> '|'
                '<' -> '-'
                '>' -> '-'
                else -> c
            }
        }.toTypedArray()
    }.toTypedArray()
    return Pair(carts, tracks)
}

val input = listOf(
    "                   /-----------\\                                                                                     /--------\\                       ",
    "     /-------------+-----------+----------------------------------------------------------------------\\              |        |                       ",
    "     |             |  /--------+------------------------------\\                                       |              |        |                       ",
    "     |           /-+--+--------+------------------------------+---------------------------------------+---------\\    |  /-----+---------------------\\ ",
    "   /-+-----------+-+--+--\\/----+-----------\\                  |                         /-------------+-\\       |    |  |     |                     | ",
    "   | |      /----+-+--+--++----+-----------+------------------+---------------------\\   |             | |       |    |  |     |                     | ",
    "   | |      |    | |  |  ||    |           |/-------------\\   |               /-----+---+-------------+-+-------+----+--+-----+--------------------\\| ",
    " /-+-+------+----+-+\\ |  ||    |           ||    /------<-+---+---------------+-----+---+-------------+-+-------+----+--+-->--+--------------------++\\",
    " | | |      |/---+-++-+--++----+-----------++--\\ |        |   |               |     |   |             | |       |    |  |     |                    |||",
    " | | |      ||   | ||/+--++----+-----------++--+-+--------+--\\|               |     |   |  /----------+-+-------+\\   |  |     |                    |||",
    " | | |      ||   | ||||  ||    |           || /+-+--------+--++---------------+-----+---+--+----------+-+\\      ||   |  |     |                    |||",
    " | | |      ||   | ||||  ||    |         /-++-++-+--------+--++---------------+-----+---+--+----------+-++-----\\||   |  |     |                    |||",
    " | | |      ||   | ||||  ||    |         | || || |     /--+--++---------------+-----+---+--+----------+-++-----+++---+--+-----+-----\\              |||",
    " | | |      ||   | ||||  ||    |         | || || |     |  |  ||               |     |   |  |          | ||     |||   |  |   /-+-----+\\             |||",
    " | | |      || /-+-++++--++----+---------+-++-++-+-----+--+--++---------------+----\\|   |  |          | ||     |||   |  |   | |     ||             |||",
    " | | | /----++-+-+-++++--++----+---------+-++-++-+-----+--+--++--------------\\|    ||  /+--+----\\     | ||/----+++---+--+---+-+-----++\\            |||",
    " | | | |  /-++-+-+-++++--++----+---------+-++-++-+-----+--+--++--------------++----++--++--+----+-----+-+++\\   |||   |  |   | |     |||            |||",
    " | | | |  | || | | ||||  ||    |         | || || |     |  |  ||            /-++----++--++--+----+----\\| ||||   |||   |  |   | |     |||            |||",
    " | | | |  | || | | ||||  ||    |         | || || |     |  |  ||            | ||    ||  ||  |/---+----++-++++---+++---+--+--\\| |     |||            |||",
    " | | | |  | || | | ||||  ||    |         |/++-++-+-----+--+--++------\\     | ||    ||  ||  ||   | /--++<++++---+++---+--+--++-+-----+++------\\     |||",
    " | | | |/-+-++-+-+-++++--++----+---------++++-++-+-----+--+--++----\\ |     | ||    ||  ||  ||   | |  || ||||   |||   |  |  || | /---+++------+--\\  |||",
    " | | | || |/++-+-+-++++--++----+---------++++-++-+-----+--+--++----+-+-----+-++----++--++--++---+-+--++-++++---+++---+-\\|  || | |   |||      |  |  |||",
    " | | | || |||| | | ||||  ||    |         |||| || |     |  |  ||    | |     | ||    ||  ||  ||   | |  || ||||   |||   \\-++--++-/ |   |||      |  |  |||",
    " | | | || |||| | | ||||  ||    |         |||| || \\-----+--+--++----+-+-----+-++----++--++--++---+-+--++-++++---+++-----++--++---+---+++------+--+--++/",
    " | | | || |||| |/+-++++--++----+\\        |||| ||       | /+--++----+-+-----+-++\\   ||  ||  ||   | |  || ||||   |||     ||  ||   |   |||      |  |  || ",
    " | | | || |||| ||| ||||  ||    ||        |||| ||       | ||  ||    | |     | |||   ||  ||  ||   | |  || ||||   |||     ||  ||   |   |||      |  |  || ",
    " | | | \\+-++++-+++-++++--++----++--------++++-++-------+-++--++----+-+-----+-/||   ||  ||  || /-+-+--++-++++---+++-----++--++---+\\  |||      |  |  || ",
    " | | |  | |||| ||| ||||  ||    ||   /----++++-++-------+-++--++--\\ | |     |  ||   ||  ||  || | | |  || ||||   |||     ||  ||   ||  |||      |  |  || ",
    " | | \\--+-++++-+++-++++--++----++---+----++++-++-------+-++--++--+-+-+-----+--++---++--++--++-+-+-+--+/ ||||   |||     ||  ||   ||  |||      |  |  || ",
    " | |    |/++++-+++-++++--++----++\\  |/---++++-++-------+-++--++--+-+-+-----+--++\\  ||  |\\--++-+-+-+--+--/|||   |||     ||  ||   \\+--+++------+--/  || ",
    " | |    |||||| ||| ||||  ||    |||  ||   |||| ||       | ||  ||  | | |     \\--+++--++--+---++-+-+-+--/   |\\+---+++-----++--++----+--++/      |     || ",
    " | |    ||||\\+-+++-++++--++----+++--++---++++-++-------+-++--++--+-+-+--------+++--+/  |/--++-+-+-+------+-+---+++-----++--++\\   |  ||       |     || ",
    " | |    |||| | ||| ||||  ||    |||  ||   |||| ||       | ||  ||  | | |        |||  |   ||  || | | \\------+-+---+++-----++--+++---+--++-------/     || ",
    " | |    |||| | ||| ||||  ||    |||  ||   |||| ||   /---+-++--++--+-+-+---\\    |||  |   ||  \\+-+-+--------+-+---++/     ||  |||  /+--++------------\\|| ",
    " | |    |||| | ||| ||||/-++----+++--++---++++-++---+---+-++--++--+-+-+---+----+++--+---++---+-+-+--------+-+---++---\\  ||  |||  ||  ||            ||| ",
    " | |    |||| | ||| ||||| ||    |||  ||   |||| ||   |   | ||  ||  | | |   |    |||  |   ||   | | |        | |   ||   |  ||  |||  ||  ||            ||| ",
    " | |    |||| | ||| ||||| ||    |||  ||   |||| ||   |   | ||  ||  | | |   |    |||  |   ||   | | |        | |   ||   |  ||  |||  ||  ||            ||| ",
    " | |    |||| | ||| ||||| ||/---+++--++---++++-++---+---+-++--++--+-+-+---+----+++--+---++---+-+-+--------+-+-\\ ||   |  ||  |||  ||  ||            ||| ",
    " | |    |||| | ||\\-+++++-+++---+++--++---++++-++---+---+-++--++--+-+-+---+----+++--+---++---+-+-+--------+-+-+-+//--+--++--+++--++-\\||            ||| ",
    " | |    |||| | ||  \\++++-+++---/||  ||   |||| || /-+---+-++--++--+-+-+---+----+++--+---++---+-+-+--------+-+-+-+-+\\ |  ||  |||  || |||            ||| ",
    " | |    |\\++-+-++---++++-+++----+/  ||  /++++-++-+-+---+-++--++--+-+-+---+----+++--+---++---+-+-+--------+-+-+\\| || |  ||  |||  || |||            ||| ",
    " | |    | || | ||   |||| |||    |   ||  ||||| || | |   | ||  ||  | | |   |    |||  |   ||   | | |/-------+-+-+++-++-+--++--+++--++-+++---\\        ||| ",
    " | |    \\-++-+-++---++++-+++----+---++--+++++-++-+-+---+-++--++--+-/ |   |    ||| /+---++---+-+-++-------+-+-+++-++-+\\ ||  |||  || |||   |        ||| ",
    " | |      || | ||   |||| |\\+----+---++--+++/| || | |   | \\+--++--+---+---+----+/| ||   ||   | | ||       | | ||| || || ||  |||  || |||   |        ||| ",
    " | |      || | || /-++++-+-+----+---++--+++-+-++-+-+---+--+--++--+---+---+----+\\| ||   |\\---+-+-++-------+-+-+++-++-++-++--++/  || |||   |        ||| ",
    " | |      || | ||/+-++++-+-+----+---++--+++-+-++-+-+---+--+--++--+---+---+---\\||| ||   |    | | ||       | | ||| || || ||  ||   || |||   |        ||| ",
    " | |      || | |||| |\\++-+-+----+---++--+++-+-++-+-+---+--+--/|  |   | /-+---++++-++---+----+-+-++-------+-+-+++-++-++-++--++---++-+++---+--\\     ||| ",
    " | |/-----++-+-++++-+-++-+-+----+---++--+++-+-++-+-+---+--+---+--+\\/-+-+-+---++++-++---+----+-+-++--\\    | | ||| || || ||  ||   || |||   |  |     ||| ",
    " | ||     || | |||| | || | |    |   ||  ||| | || | |   |  |   |  ||| | | |   |||| ||   |    |/+-++--+----+-+-+++-++-++-++--++---++-+++---+--+-\\   ||| ",
    " | ||     || v |||| | \\+-+-+----+---++--+++-+-++-+-+---+--+---/  ||| | | |   |||| ||   | /--+++-++--+----+-+-+++-++-++-++--++---++-+++---+-\\| |   ||| ",
    " | ||     || | |||| |  | | |    |   ||  ||| | || | |   |  |      |||/+-+-+---++++-++---+-+--+++-++--+----+-+-+++-++-++-++-\\||   || |||   | || |   ||| ",
    " | ||     || | |||| |  | | |    |   ||  ||| | || | |   | /+------+++++-+-+---++++-++---+-+--+++-++--+-->-+-+-+++-++-++-++-+++---++-+++---+-++-+---+++\\",
    " | ||     || | |||| |  | | |    |   ||  ||| | || | |   | ||     /+++++-+-+---++++-++---+-+--+++-++--+----+-+-+++-++-++-++-+++--\\|| |||   | || |   ||||",
    " | ||     || | |||| |  | | | /--+---++--+++-+-++-+-+---+-++-----++++++-+\\|   |||| ||   | |  ||| ||  |    | | ||| || || || |||  ||| |||   | || |   ||||",
    " | ||/----++-+-++++\\|  |/+-+-+--+---++--+++-+-++-+-+---+-++-----++++++-+++---++++\\||   | |  ||| ||  |    | | ||| || || || |||  ||| |||   | || |   ||||",
    " | |||    ||/+-++++++--+++-+-+--+---++--+++-+-++-+-+---+-++-----++++++-+++---+++++++---+-+--+++-++--+-\\  | | ||| || || || |||  ||| |||   | || |   ||||",
    " | |||   /++++-++++++--+++-+-+--+---++--+++-+-++-+-+---+-++-----++++++-+++---+++++++---+-+--+++-++--+\\|  | | ||| || || || |||  ||| |||   | || |   ||||",
    " | |||   ||||| ||||||  ||| | |  |   ||  ||| \\-++-+-+---+-+/     |||||| |||   |||||||   \\-+--+++-/|  |||  | | ||| || || || |||  ||| |||   | || |   ||||",
    " | |||  /+++++-++++++--+++-+\\|  |   ||  |||   || | |   | |      |||||| |||   |||||||     |  |||  |  |||  | | ||| || || || |||  ||| |||   | || |   ||||",
    " | |||  |||||| ||||||  ||| |||  |   ||  |||   || | |   | |  /---++++++-+++---+++++++-----+--+++--+--+++--+-+-+++-++-++-++-+++--+++-+++---+-++-+-\\ ||||",
    " | |||  |||||| |||\\++--+++-+++--+---++--+++---++-+-+---+-+--+---++++++-+++---++/||||     |  |||  |  |||  | |/+++-++-++-++-+++--+++-+++---+-++-+\\| ||||",
    " | \\++--++++++-+++-++--++/ |||  |   ||  |||/--++-+-+---+-+-\\|   |||\\++-+++---++-++++-----+--+++--+--/||  | ||||| || || || |||  ||| |||   | || ||| ||||",
    " |  ||  |||||| ||| ||  ||  |||/-+---++--++++--++-+-+---+-+-++---+++-++-+++---++-++++-----+--+++--+---++\\ | ||||| || || || |^|  ||| |||   | || ||| ||||",
    " |  ||  |||||| ||| ||  ||  |||| |   ||  ||||  || | |   | | ||   ||| || |||   || ||||/----+--+++--+---+++-+-+++++-++-++-++-+++--+++-+++--\\| || ||| ||||",
    " |  ||  |||||| ||| ||  ||  |||| |   ||  ||||  || | |   |/+-++---+++-++-+++---++-+++++----+-\\|||  |   ||| | ||||| || || || |||  ||| |||  || || ||| ||||",
    " |  ||  |||||| ||| ||  ||  |||| |   \\+--++++--++-+-+---+++-++---+/| || |||  /++-+++++----+-++++-\\|   ||| | ||||| || || || |||  ||| |||  || || ||| ||||",
    " |  ||  |||||| ||| ||  ||  |||| |    |  ||||  || | |   ||| ||   | | || |||  ||| |||||    | |||| ||   ||| | ||||| \\+-++-++-+++--+++-/||  || || ||| ||||",
    " |  ||  |||||| ||| ||  ||  |||| |    |  ||||  || | |   ||| ||   | | || |||  ||| |||||    | |||| ||   ||| | |||||  | || || |||  |||  ||  || || ||| ||||",
    " |  ||  |||||| ||| ||  ||  |||| |  /-+--++++--++-+-+---+++-++---+-+-++-+++--+++-+++++----+-++++-++---+++-+-+++++--+-++-++-+++--+++--++\\ || || ||| ||||",
    " |  ||  |||||| ||| ||  |\\--++++-+--+-+--++++--++-+-+---+++-++---+-+-++-+++--+++-+/|||    | |||| ||   ||| | |||||  | || || |||  |||  ||| || || ||| ||||",
    " |  ||  |||||| ||| ||  |   |||| |  | |  ||||  || | |   |||/++---+-+\\|| |||  ||| | |||    | |||| ||   ||| | |||||  | || || |||  |||  ||| || || ||| ||||",
    " |  ||  |||||| ||| ||  |   |||| |  | |  ||||  || | |   ||\\+++---+-++++-+++--+++-+-+++----+-++++-++---+++-+-+++++--+-++-++-+++--+++--+++-++-++-+++-+++/",
    " |  ||  |||||| ||| ||  |   |||| |  | |  ||||  || | |   || |||   | |||| |||  ||| | |||    | |||| ||   ||| | |||||  | || || |||  |||  ||| || || ||| ||| ",
    " |  ||  |||||| ||| ||  |   |||| |  | |  ||||  || | |   || |||   | ||\\+-+++--+++-+-+++----+-++++-++---+++-+-+++++>-+-++-++-/||  |||  |^| || || ||| ||| ",
    "/+--++--++++++-+++-++--+---++++-+--+-+--++++--++\\| |   || |||   | || | |||  ||| | |||    | |||| ||   ||| | |||||  | || ||  ||  |||  ||| || || ||| ||| ",
    "||  ||  ||||||/+++-++--+---++++-+--+-+--++++--++++-+-\\ || |||   | || | |||  ||| | |||    | |||| ||   ||| | |||||  | || ||  ||  |||  ||| || || ||| ||| ",
    "||  ||  |||||||||| ||  |   |||| |  | |  ||||  |||| | | || |||   | || | |||  ||| | |||    | |||| |\\---+++-+-+++++--+-++-++--++--+++--+++-+/ || ||| ||| ",
    "||  || /++++++++++-++--+---++++-+--+-+--++++\\ |||| | | || |||   | || | |||  ||| | |||    | |||| |    ||| | |||||  | || ||  ||  |||  |||/+--++-+++\\||| ",
    "||  || ||||||||||| ||  |   |||| |  | |  ||||| |||| | | || |||   | ||/+-+++--+++-+-+++----+-++++-+----+++-+-+++++--+\\|| ||  ||  |||  |||||  || ||||||| ",
    "|| /++-+++++++++++-++--+---++++-+--+\\|  ||||| |||| | | || |||   | |||| |||  ||| | |||    | |||| |    ||| | |||||  |||| ||  || /+++--+++++\\ || ||||||| ",
    "|| ||| ||||||||||| ||  |   |||| |  |||  ||||| |||| | | || |||   | |||| \\++--+++-+-+++----+-++++-+----+++-+-+++++--++++-++--++-++++--++++++-+/ ||||||| ",
    "|| ||| ||||||||||| ||  |   |||| |  |||  ||||| |||| | | || |||   | ||||  ||/-+++-+-+++----+-++++-+----+++-+-+++++--++++-++--++-++++-\\|||||| |  ||||||| ",
    "|| ||| ||||||||||| ||  |   ||\\+-+--+++--+++++-++++-+-+-++-+++---+-++++--/|| ||| | |||    | |||| |    ||| | |||||  |||| ||  || |||| ||||||| |  ||||||| ",
    "|| ||| ||||||||\\++-++--+---++-+-+--+++--+++++-++++-+-+-++-+++---+-++++---++-+++-+-+/|    | |||| |    ||| | |||||  |||| ||  || |||| ||||||| |  ||||||| ",
    "|| ||| |||||||| || ||  |   || | |  |||  ||||| |||| | | || |||   | ||||   || ||| | | |    | |||| |    ||| | |||||  |||| ||  || |||| ||||||| |  ||||||| ",
    "|| ||| |||||||| || ||  |   || | |  |||  ||||| |||| | | || |||/--+-++++---++-+++-+-+-+----+-++++-+----+++-+-+++++-\\|||| ||  || |||| ||||||| |  ||||||| ",
    "|| ||| |||||||| || ||  |  /++-+-+--+++--+++++-++++-+-+-++-++++--+-++++---++-+++-+-+-+----+-++++-+----+++-+-+++++-+++++-++\\ || |||| ||||||| |  ||||||| ",
    "|| ||| |||||||\\-++-++--+--+++-+-+--+++--+++++-++++-+-/ || ||||  | ||||   || ||| | | |    | |||| |    ||| | ||||| ||||| ||| || |||| ||||||| |  ||||||| ",
    "|| \\++-+++++++--++-++--+--+++-+-+--+/|  ||||| \\+++-+---++-++++--+-++++---++-+++-+-+-+----+-++++-+----+++-/ ||||| ||||| ||| || |||| ||||||| |  ||||||| ",
    "||  || |||\\+++--++-++--+--+++-+-+--+-+--+++++--+++-+---++-++++--+-++++---++-+++-+-+-+----+-++++-+----+++---/|||| ||||| ||| || ||\\+-+++++++-+--++++/|| ",
    "||  || ||| \\++--++-++--+--+++-+-+--+-+--+++++--+++-+---++-++++--+-++++---++-+++-+-+-+----+-++++-+----+++----++++-+++++-/|| || || | ||||||| |  |||| || ",
    "||  || |||  ||  || ||/-+--+++-+-+--+-+--+++++--+++-+---++-++++--+-++++---++-+++-+-+-+----+-++++-+----+++----++++\\|||||  || || || | ||||||| |  |||| || ",
    "\\+--++-+++--++--++-+++-+--+++-+-+--+-+--+++++--+/| |   || ||||  | ||||   || ||| | | |    | |||| |    |||    ||||||||||  || || || | ||||||| |  |||| || ",
    " |  || |||  ||  || ||| |  ||| | |  | |  |||||  | | |  /++-++++--+-++++---++-+++-+-+-+----+-++++-+--\\ |||    ||||||||||  || || || | ||||||| |  |||| || ",
    " |  || |||  ||  || ||| |  ||| | |  | |  |||||  | | |  ||| ||\\+--+-++++---++-+++-+-+-+----+-++++-+--+-+++----++++++++++--++-++-++-+-+++++++-+--++/| || ",
    " |  || |||  ||  || ||| |  |||/+-+--+-+--+++++--+-+-+--+++-++-+--+-++++---++-+++-+-+-+----+-++++-+--+-+++----++++++++++-\\|| || || | ||||||| |  || | || ",
    " |  || |||  |\\--++-+++-+--+++++-+--+-+--+++++--/ | |  ||| || |  | ||||   |\\-+++-+-+-+----+-++++-+--+-+++----++++++++++-+++-++-++-+-/|||||| |  || | || ",
    " |  || |||  |   || ||| |  \\++++-+--+-+--+++++----+-+--+++-++-+--+-++++---+--+++-+-+-+----+-++++-+--+-+++----++++++++++-++/ || || |  |||||| |  || | || ",
    " |  || |||  |   || ||| |   |||| |  | |  |||||    | |  ||| || |  | ||||   |  ||\\-+-+-+----+-++++-+--+-+++----++++++++++-++--++-++-+--++++++-+--++-+-/| ",
    " |  || |||  |   || ||| |   |||\\-+--+-+--+++++----+-+--+++-++-+--+-++++---+--++--+-+-+----+-++++-+--+-++/    |||||||||| ||  || || |  |||||| |  || |  | ",
    " |  || |||  |   || ||| |   |||  |  | |  |||||    | |  ||| || |  | ||||   |  ||  | | |    | |||| |  | ||     |||||||||| ||  || || |  |||||| |  || |  | ",
    " |  || |||  |   || ||| |   |||  |  |/+--+++++----+-+--+++-++-+--+-++++\\  |  ||  | | |    | |||| |  | ||     |||||||||| ||  || || |  |||||| |  || |  | ",
    " |  || |||  |   || ||| |   |||  |  |||  |\\+++----+-+--+++-++-+--+-+++++--+--++--+-+-+----+-++++-+--+-++-----+++/|||||| ||  || || |  |||||| |  || |  | ",
    " |  || |||  |   || ||| |   |||  |  ||\\--+-+++----+-+--+++-++-+--+-+++++--+--++--/ | |    | |||| |  | ||     \\++-++++++-++--++-++-+--++++++-+--+/ |  | ",
    " |  || |||  |   || ||| |   |||  |  ||   | |||    | |  ||| || |  | |||||  |  ||    | |    | |||| |  | ||      || |||||| ||  || || |  |||\\++-+--+--/  | ",
    " |  || |||  |   || ||| |   ||\\--+--++---+-+++----+-+--+++-++-+--+-+++++--+--++----+-+----+-++++-+--+-++------++-++++++-/|  || || |  ||| || |  |     | ",
    " |  || |||  |   || ||| |   ||   |  ||   | ||| /--+-+--+++-++-+--+-+++++--+--++----+-+----+-++++-+--+-++------++-++++++--+--++-++\\|  ||| || |  |     | ",
    " |  || |||  |   || ||| |   ||   |  ||   v ||| |  | |  |||/++-+--+-+++++--+--++---\\| |    | |||| |  | ||      || ||||||  \\--++-++++--+++-++-+--+-----/ ",
    " |  || ||\\--+---++-+++-+---++---+--++---+-+++-+--+-+--++++++-+--+-+++++--+--++>--++-+----+-++++-+--+-/|      || ||||||     || \\+++--+++-+/ |  |       ",
    " |  || ||   |   || ||| |   \\+---+--++---+-+++-+--+-+--++++++-+--+-+++++--+--++---++-+----+-++++-+--+--+-->---/| ||||||     ||  |||  ||| |  |  |       ",
    " | /++-++---+---++-+++-+----+---+--++-\\ \\-+++-+--+-+--++++++-+--+-+++++--+--++---++-+----+-++++-+--+--+-------/ ||||||     ||  |||  ||| |  |  |       ",
    " \\-+++-++---+---++-+/| |    |   |  || |   \\++-+--+-+--++++++-+--+-+++/|  |  ||   || \\----+-++++-+--+--+---------++++++-----++--+++--+++-/  |  |       ",
    "   ||| ||   |   || | | |    |   |  || |    || |  | |  |||||| |  | ||| |  |  ||   ||   /--+-++++-+--+--+-------\\ ||||||     ||  |||  |||    |  |       ",
    "   ||| ||   |   || | | |    |   |  || |    || |  \\-+--++++++-+--+-+++-+--+--++---++---+--+-++++-+--+--+-------+-++/|||     ||  |||  |||    |  |       ",
    "   ||| ||   |   || | | |    |   |  || | /--++-+----+--++++++-+--+-+++-+--+--++--\\||   |  | |||\\-+--+--+-------+-++-+++-----++--++/  |||    |  |       ",
    "   ||| ||   |   || | | |    |   |  || | |  || |    \\--++++++-+--+-+++-+--/  ||  |||   |  | |||  |  |  |       | || |||     |\\--++---+/|    |  |       ",
    " /-+++-++-\\ |   || | | |    |   |  || | |  || |       |\\++++-+--+-+++-+-----++--+++---+--+-+++--+--+--+-------+-++-+++-----+---++---/ |    |  |       ",
    " | ||| || | |   || | | |    |   |  || | |  \\+-+-------+-+++/ |  | ||| |     ||  |||   |  | |||  |  |  |       | || |||     |   ||     |    |  |       ",
    " | ||| || | |   || | | | /--+---+--++-+-+--\\| |       |/+++--+--+-+++-+-----++--+++---+--+-+++--+--+--+-------+-++-+++-----+---++-----+---\\|  |       ",
    " | ||| || | |   ^| | | | |  |   |  || | |  || |       |||||  |  | ||| |     ||  |||   |  | |\\+--+--+--+-------+-++-+++-----/   ||     |   ||  |       ",
    " | ||| || | |   || | \\-+-+--+---+--++-+-+--++-+-------+++++--+--+-+++-+-----++--+++---+--+-+-+--+--+--+-------+-/| |||         ||     |   ||  |       ",
    " | ||^ || | |   || |   | |  |   |  || | |  || |       |||||  |  | ||| |     ||  |||   |  \\-+-+--+--+--+-------+--+-+++---------++-----+---+/  |       ",
    " | ||| || | |   \\+-+---+-+--+---/  || | |  || |       ||||\\--+--+-+/| |     \\+--+++---+----+-+--/  |  |       |  | |||         ||     |/--+---+-----\\ ",
    " | ||| || | |    | |   | |  |      || | |  || |       ||||   |  | | | |      |  |||   |    | |     |  |       |  | |||         ||     ||  |   |     | ",
    " | ||| \\+-+-+----+-+---+-+--+------++-+-+--+/ |       ||||   \\--+-+-+-+------+--+++---+----+-+-----+--+-------+--/ |||         ||     ||  |   |     | ",
    " | |||  | | |    | |   | |  |      || | |  |  |     /-++++------+-+-+-+------+--+++---+----+-+-----+--+-------+----+++------\\  ||     ||  |   |     | ",
    " | |||  | | |    | |   | |  |      || | |/-+--+-----+-++++------+-+-+-+-\\    |  |||   |    | |     |  |       |    |||      |  ||     ||  |   |     | ",
    " | |||  | | |    \\-+---+-+--+------++-+-++-+--+-----+-++++------+-+-+-+-+----/  |||   |    | |     |  |       |    |||      |  ||     ||  |   |     | ",
    " | \\++--+-+-+------+---+-+--+------++-/ || |  |     | ||||      | | \\-+-+-------+++---+----+-+-----+--+-------+----/||      |  ||     ||  |   |     | ",
    " |  ||  | | |      |   | |  |      ||   || |  |     | ||||      | |   | |       |||   |    | |     |  |       |     ||      |  ||     ||  |   |     | ",
    " |  ||  | | \\------+---+-+--+------++---++-+--+-----+-++++------+-+---+-+-------+++---+----+-+-----+--/       |     ||      |  ||     ||  |   |     | ",
    " |  ||  | |        |   | |  |      ||   || |  |     | ||\\+------+-+---+-+-------+++---+----/ \\-----+----------+-----++------+--++-----++--+---/     | ",
    " |  ||  | |        |   \\-+--+------++---++-+--+-----+-++-+------+-+---+-+--->---+++---+------------+----------+-----/|      |  ||     ||  |         | ",
    " |  ||  | |        |     |  |      ||   || |  |     | |\\-+------+-+---+-+-------+++---+------------+----------+------+------+--++-----++--/         | ",
    " |  ||  | |        |     |  |      ||   || |  |     | |  \\------+-+---+-+-------+/|/--+------------+----------+------+----\\ |  ||     ||            | ",
    " |  |\\--+-+--------/     |  |      ||   || |  |     | |         | |   | |       | ||  |            |          |      |    | |  ||     ||            | ",
    " |  |   | |              |  | /----++---++-+--+-----+-+---------+-+---+-+->-----+-++--+------------+----------+------+----+-+--++--\\  ||            | ",
    " |  \\---+-+--------------+--+-+----++---++-+--+-----+-+---------+-/   | |       | ||  |            |          |      |    | |  ||  |  ||            | ",
    " |      | |              |  | |    ||   || |  |     | \\---------+-----+-+-------+-++--+------------/          |      |    | |  ||  |  ||            | ",
    " |      | |              |  | |    ||   \\+-+--+-----+-----------+-----+-+-------/ \\+--+-------->--------------+------/    | |  ||  |  ||            | ",
    " \\------+-/              |  | |    ||    | |  |     ^           \\-----+-+----------+--+-----------------------+-----------+-+--/|  |  ||            | ",
    "        |                |  | |    ||    | |  |     |                 | |          |  \\-----------------------/           | |   |  |  ||            | ",
    "        |                |  | |    |\\----+-+--+-----+-----------------/ |          |                                      | |   |  |  ||            | ",
    "        \\----------------+--/ |    |     | |  |     |                   |          |                                      | |   |  |  ||            | ",
    "                         \\----+----+-----+-/  |     \\-------------------+----------+--------------------------------------+-/   |  |  |\\------------/ ",
    "                              |    |     \\----+-------------------------/          \\--------------------------------------/     |  |  |               ",
    "                              |    |          \\---------------------------------------------------------------------------------/  |  |               ",
    "                              \\----+-----------------------------------------------------------------------------------------------/  |               ",
    "                                   \\--------------------------------------------------------------------------------------------------/               ",
    "                                                                                                                                                      "
)