class Square
  attr_reader :row, :col
  def initialize(row, col)
    @row = row
    @col = col
  end

  # For debug.
  def to_s
    row_char = ('a'.ord + @row).chr
    col_char = (Board::HEIGHT - @col).to_s
    row_char + col_char
  end
end

class Queen
  def initialize(square)
    @square = square
  end

  def diagonal_squares
    up_rows = @square.row
    down_rows = Board::HEIGHT - 1 - @square.row
    left_cols = @square.col
    right_cols = Board::WIDTH - 1 - @square.col

    squares = []
    squares += (1..[up_rows, left_cols].min).map do |delta|
      Square.new(@square.row - delta, @square.col - delta)
    end
    squares += (1..[up_rows, right_cols].min).map do |delta|
      Square.new(@square.row - delta, @square.col + delta)
    end
    squares += (1..[down_rows, left_cols].min).map do |delta|
      Square.new(@square.row + delta, @square.col - delta)
    end
    squares += (1..[down_rows, right_cols].min).map do |delta|
      Square.new(@square.row + delta, @square.col + delta)
    end

    squares
  end
end

class Board
  WIDTH = 8
  HEIGHT = 8

  class << self
    def row_indexes
      0...HEIGHT
    end

    def col_indexes
      0...WIDTH
    end
  end

  def initialize
    @queen_squares = []
    @row_filled = Board.row_indexes.map { false }
    @col_filled = Board.col_indexes.map { false }
    @special_cell_filled =
      Board.col_indexes.map { Board.row_indexes.map { false } }
  end

  protected def direct_set(args)
    @queen_squares = args[:queen_squares]
    @row_filled = args[:row_filled]
    @col_filled = args[:col_filled]
    @special_cell_filled = args[:special_cell_filled]
  end

  def deep_dup
    new_board = Board.new
    new_board.direct_set(
      queen_squares: @queen_squares.dup,
      row_filled: @row_filled.dup,
      col_filled: @col_filled.dup,
      special_cell_filled: @special_cell_filled.map { |row| row.dup }
    )

    new_board
  end

  def put_queen(square)
    @queen_squares << square
    @row_filled[square.row] = true
    @col_filled[square.col] = true
    Queen.new(square).diagonal_squares.each do |sq|
      @special_cell_filled[sq.row][sq.col] = true
    end
  end

  def row_empty?(row_index)
    !@row_filled[row_index]
  end

  def empty_row_indexes
    Board.row_indexes.find_all { |i| row_empty?(i) }
  end

  def col_empty?(col_index)
    !@col_filled[col_index]
  end

  def empty_col_indexes
    Board.col_indexes.find_all { |i| col_empty?(i) }
  end

  def empty_col_indexes_in(empty_row_index)
    r = empty_row_index
    empty_col_indexes.find_all { |c| !@special_cell_filled[r][c] }
  end

  def to_ascii
    squares = Board.col_indexes.map { Board.row_indexes.map { '.' } }
    @queen_squares.each do |sq|
      squares[sq.row][sq.col] = 'Q'
    end

    squares.map { |rows| rows.join('') }.join("\r\n")
  end
end

board = Board.new

k = gets.chomp.to_i
k.times.each {
  r, c = gets.chomp.split(' ').map(&:to_i)
  sq = Square.new(r, c)
  board.put_queen(sq)
}

def put_queens(board)
  return board if board.empty_row_indexes.empty?

  row = board.empty_row_indexes.first
  return nil if board.empty_col_indexes_in(row).empty?

  board.empty_col_indexes_in(row).lazy.map do |col|
    new_board = board.deep_dup
    sq = Square.new(row, col)
    new_board.put_queen(sq)
    put_queens(new_board)
  end.find do |new_board|
    !new_board.nil?
  end
end

puts put_queens(board).to_ascii



Measured memory_bytes: 9008