asd

const readline = require("readline").createInterface({
  input: process.stdin,
  output: process.stdout
});

let N = 10000;
let board = [];
let queensByRow = [];
let queensByMinorDiagonal = [];
let queensByMajorDiagonal = [];

const getRandomInt = max => Math.floor(Math.random() * Math.floor(max));

const generateBoard = () => {
  board = [];
  queensByRow = [];
  queensByMinorDiagonal = [];
  queensByMajorDiagonal = [];

  for (let i = 0; i < N; i++) {
    board.push(i);
    queensByRow.push(0);
  }
  for (let i = 0; i < 2 * N; i++) {
    queensByMinorDiagonal.push(0);
    queensByMajorDiagonal.push(0);
  }

  for (let i = 0; i < N; i++) {
    const ind = getRandomInt(N);
    const temp = board[i];
    board[i] = board[ind];
    board[ind] = temp;
  }
  for (let i = 0; i < N; i++) {
    const queenRow = board[i];
    queensByRow[queenRow]++;
    queensByMinorDiagonal[queenRow + i]++;
    queensByMajorDiagonal[N - queenRow - 1 + i]++;
  }
};

const getConflictCount = (row, col, hasQueenOnCell) =>
  queensByRow[row] +
  queensByMinorDiagonal[row + col] +
  queensByMajorDiagonal[N - row - 1 + col] -
  (hasQueenOnCell ? 3 : 0);

const solve = () => {
  const MAX_STEPS = 2 * N;
  let step = 0;
  let candidates = [];

  while (step++ < MAX_STEPS) {
    let maxConflicts = 0;
    candidates = [];

    for (let c = 0; c < board.length; c++) {
      let conflicts = getConflictCount(board[c], c, true);

      if (conflicts === maxConflicts) {
        candidates.push(c);
      } else if (conflicts > maxConflicts) {
        maxConflicts = conflicts;
        candidates = [c];
      }
    }

    if (maxConflicts === 0) {
      return true;
    }
    const worstQueenColumn = candidates[getRandomInt(candidates.length)];
    let minConflicts = N;
    candidates = [];
    for (let r = 0; r < board.length; r++) {
      let conflicts = getConflictCount(
        r,
        worstQueenColumn,
        board[worstQueenColumn] === r
      );
      if (conflicts === minConflicts) {
        candidates.push(r);
      } else if (conflicts < minConflicts) {
        minConflicts = conflicts;
        candidates = [r];
      }
    }

    if (candidates.length > 0) {
      const newRow = candidates[getRandomInt(candidates.length)];
      const oldRow = board[worstQueenColumn];
      board[worstQueenColumn] = newRow;

      queensByRow[oldRow]--;
      queensByRow[newRow]++;
      queensByMinorDiagonal[oldRow + worstQueenColumn]--;
      queensByMinorDiagonal[newRow + worstQueenColumn]++;
      queensByMajorDiagonal[N - oldRow - 1 + worstQueenColumn]--;
      queensByMajorDiagonal[N - newRow - 1 + worstQueenColumn]++;
    }
  }

  return false;
};

const main = () => {
  console.time("l");
  while (true) {
    generateBoard();
    if (solve()) {
      break;
    }
  }
  console.timeEnd("l");
  console.log("end");
};

readline.on("line", line => {
  N = Number(line);
  main();
  readline.close();
});