import scala.annotation.tailrec

object GraphDemo extends App {
  val graph = SimpleGraph(Nil)
  val from = SimpleNode(0, 0)
  val to = SimpleNode(15, 8)
  val moves = graph.shortestPath(from, to).getOrElse(Nil)
  moves.reverse.map(_.name).foreach(println)
}

//CodinGame
object Player extends App {
  val Array(startx, starty, exitx, exity) = for (i <- readLine split " ") yield i.trim.toInt
  val nbobstacles = readLine.trim.toInt // number of walls
  val obs = for (i <- 0 until nbobstacles) yield {
    val Array(posx, posy) = for (i <- readLine split " ") yield i.trim.toInt
    SimpleNode(posx, posy)
  }

  val graph = SimpleGraph(obs.toList)
  val from = SimpleNode(startx, starty)
  val to = SimpleNode(exitx, exity)
  val moves = graph.shortestPath(from, to).getOrElse(Nil)
  println(moves.reverse.map(_.name).mkString(" "))

}

trait Graph {
  type Node

  case class Move(from: Node, to: Node, name: String, cost: Double = 1)

  type Path = List[Move]

  def shortestPath(from: Node, to: Node): Option[Path] =
    pathImpl(to, List((from, Nil)), Nil)

  def validMoves(from: Node): List[Move]

  @tailrec
  private def pathImpl(
    to: Node,
    toExplore: List[(Node, Path)],
    explored: List[Node]): Option[Path] = toExplore match {
    case Nil               => None
    case (`to`, path) :: _ => Some(path)
    case (node, path) :: t =>
      def alreadyQueued(n: Node) = toExplore.exists {
        case (`n`, _) => true
        case _        => false
      }

      val newNodes = for {
        m <- validMoves(node)
        if !alreadyQueued(m.to)
        if !explored.contains(m.to)
      } yield (m.to, m :: path)
      pathImpl(to, t ::: newNodes, node :: explored)
  }
}

case class SimpleNode(x: Int, y: Int) {
  override def toString = s"($x, $y)"
}

case class SimpleGraph(impediments: List[SimpleNode], maxX: Int = 15, maxY: Int = 8, minX: Int = 0, minY: Int = 0) extends Graph {
  type Node = SimpleNode

  def validMoves(n: SimpleNode): List[Move] = for {
    (dx, dy, name) <- List((0, 1, "DOWN"), (-1, 0, "LEFT"), (1, 0, "RIGHT"), (0, -1, "UP"))
    x = n.x + dx
    y = n.y + dy
    if (x >= minX && y >= minY && x <= maxX && y <= maxY)
    if (!impediments.contains(SimpleNode(x, y)))
  } yield Move(n, SimpleNode(x, y), name)
}