object Main {
def main(args: Array[String]) {
  import Naval.{Point, Field, Ship, Fleet, Game}
  import Lesson.field

  var game: Game = (field, Map() : Fleet)
  var ships: List[String] = List()

  val N = readLine().toInt

  for (i <- 1 to N) {
      val name = readLine().split(" ")
      val toPShip = Stream.continually(readLine()).take(name.last.toInt).sorted
      val ship: Ship = toPShip.toList.map(in => in.split(" ").map(_.toInt)).collect{case Array(a, b) => (a, b)}
      val temp = game
      game = tryAddShip(temp, name.head, ship)
      if (temp != game){
          ships = name.head :: ships
      }
  }

  ships.reverse.foreach(println(_))

  def validateShip(ship: Ship): Boolean = (ship.length <= 4) &&
    (ship.map(_._2).forall(_ == ship.head._2) || ship.map(_._1).forall(_ == ship.head._1))

  def validatePosition(ship: Ship, field: Field): Boolean = {
      ((if (ship.forall(_._2 == ship.head._2)) {
          ((try {!field(ship.head._1 - 1)(ship.head._2)} catch {case unknown => true}) : Boolean) &&
          ((try {!field(ship.last._1 + 1)(ship.head._2)} catch {case unknown => true}) : Boolean) &&
          ((try {!field(ship.head._1 - 1)(ship.head._2-1)} catch {case unknown => true}) : Boolean) &&
          ((try {!field(ship.last._1 + 1)(ship.head._2-1)} catch {case unknown => true}) : Boolean) &&
          ((try {!field(ship.head._1 - 1)(ship.head._2+1)} catch {case unknown => true}) : Boolean) &&
          ((try {!field(ship.last._1 + 1)(ship.head._2+1)} catch {case unknown => true}) : Boolean) &&
          ((try {!ship.forall(in => field(in._1)(in._2+1))} catch {case unknown => true}) : Boolean) &&
          ((try {!ship.forall(in => field(in._1)(in._2-1))} catch {case unknown => true}) : Boolean)
      } else {
          ((try {!field(ship.head._1)(ship.head._2-1)} catch {case unknown => true}) : Boolean) &&
          ((try {!field(ship.head._1)(ship.last._2+1)} catch {case unknown => true}) : Boolean) &&
          ((try {!field(ship.head._1 - 1)(ship.head._2-1)} catch {case unknown => true}) : Boolean) &&
          ((try {!field(ship.last._1 + 1)(ship.head._2-1)} catch {case unknown => true}) : Boolean) &&
          ((try {!field(ship.head._1 - 1)(ship.head._2+1)} catch {case unknown => true}) : Boolean) &&
          ((try {!field(ship.last._1 + 1)(ship.head._2+1)} catch {case unknown => true}) : Boolean) &&
          ((try {!ship.forall(in => field(in._1-1)(in._2))} catch {case unknown => true}) : Boolean) &&
          ((try {!ship.forall(in => field(in._1+1)(in._2))} catch {case unknown => true}) : Boolean)
      }) : Boolean) && (!ship.forall(in => field(in._1)(in._2)))
  }
  def enrichFleet(fleet: Fleet, name: String, ship: Ship): Fleet = fleet + (name -> ship)

  def markUsedCells(field: Field, ship: Ship): Field = {
      var newField = field
      for (point <- ship) {
      val (i, j) = point
      newField = newField.updated(i, newField(i).updated(j, true))
      }
      newField
  }

  def tryAddShip(game: Game, name: String, ship: Ship): Game = {
      if (validateShip(ship)){
          if (validatePosition(ship, game._1)){
               val newFleet = game._2 + (name -> ship)
               val newField = markUsedCells(game._1, ship)
               val newGame = (newField, newFleet)
               newGame
          } else {
              game
          }
      } else {
          game
      }
  }

}
}