type Point = {
  x: number;
  y: number;
};

const addPoint = (p1: Point, p2: Point): Point => ({ x: p1.x + p2.x, y: p1.y + p2.y });
const goDown = (p: Point, slope: Point): Point => ({ x: p.x + slope.x, y: p.y - slope.y });
const bottomArea = (p: Point, slope: Point) => slope.x * p.y + (slope.x - 1) * (slope.y - 1) / 2;

const f = (x: number, n: number) => Math.floor(Math.sqrt(n - x * x));
const pointIn = (p: Point, n: number) => (p.y <= Math.sqrt(n - p.x * p.x));
const slopeOut = (s: Point, x: number, n: number) => ((s.y / s.x) > (x / Math.sqrt(n - x * x)));

const copy4 = (points: Point[]) => {
  const n = points.length;
  for (let i = 0; i < n; i++) {
    const { x, y } = points[i];
    if (y > 0) {
      points.push({ x, y: -y });
      points.push({ x: -x, y });
      points.push({ x: -x, y: -y });
    } else {
      points.push({ x: -x, y: 0 });
      points.push({ x: 0, y: x });
      points.push({ x: 0, y: -x });
    }
  }
  return points;
};
const solve = (n: number) => {
  let cnt = 0;
  const points: Point[] = [];
  const slopeStack: Point[] = [{ x: 0, y: 1 }, { x: 1, y: 0 }];

  const cbr = Math.floor(Math.cbrt(n));
  const sqr = Math.floor(Math.sqrt(n));

  const x_max = sqr;
  const naiveThreshold = Math.min(cbr + 1, x_max);

  for (let x = 1; x <= naiveThreshold; x++) {
    const y = f(x, n);
    cnt += y;
    if (x * x + y * y === n) {
      points.push({x, y});
    }
  }

  let cur: Point = { x: naiveThreshold, y: f(naiveThreshold, n) };
  while (true) {
    let l = slopeStack.pop()!;

    for (let nxt: Point; pointIn(nxt = goDown(cur, l), n); cur = nxt) {
      cnt += bottomArea(nxt, l);
      if (nxt.x * nxt.x + nxt.y * nxt.y === n) {
        points.push(nxt);
      }
    }
    if (cur.x >= x_max - naiveThreshold) break;
    while (!pointIn(goDown(cur, slopeStack[slopeStack.length - 1 | 0]), n)) {
      l = slopeStack.pop()!;
    }

    while (true) {
      const r = slopeStack[slopeStack.length - 1 | 0];
      const m = { x: l.x + r.x, y: l.y + r.y };
      const nxt = goDown(cur, m);

      if (pointIn(nxt, n)) {
        slopeStack.push(m);
      } else if (slopeOut(r, nxt.x, n)) {
        l = m;
      } else {
        break;
      }
    }
  }

  for (let x = cur.x + 1; x <= x_max; x++) {
    const y = f(x, n);
    cnt += y;
    if (x * x + y * y === n) {
      points.push({x, y});
    }
  }
  return {
    cnt: 4 * (cnt + sqr) + 1,
    points: copy4(points),
  };
};