Tajna Komisija je ove godine dobila zadatak od Vojske Srbije da napiše jedan mali program koji će pomoći da vojska napravi što bolju formaciju pešadije u raznim prilikama. Međutim, Tajna Komisija je prezauzeta oko pripreme državnog takmičenja, pa je zamolila vas da napišete taj program, a zauzvrat ćete dobiti poene na takmičenju.

Zadatak se sastoji u tome da N vojnika treba rasporediti u R redova, tačno po C vojnika u svakom redu, tako da je razmak između svaka dva susedna vojnika jednak i razmak između svaka dva reda jednak. Formalnije, vojnike možemo rasporediti u koordinatnu mrežu veličine R x C tako da se u svakoj tački (x, y) za (1 ≤ x ≤ R, 1 ≤ y ≤ C) nalazi tačno jedan vojnik.

Formacija je bolja ako je međusobna preglednost vojnika bolja. Odnosno, ako označimo sa V (x,y) broj vojnika koje vidi vojnik koji se nalazi u tački (x, y), onda suma

S = Σ _{1 ≤ x ≤ R, 1 ≤ y ≤ C} V (x,y)

treba da bude što veća. Dva vojnika vide jedan drugog ukoliko se na pravoj liniji između njih (između tačaka u kojima se nalaze) ne nalazi ni jedan drugi vojnik.

Za dati broj vojnika N ispisati R i C za koje je suma S najveća moguća, i tu sumu S.

Ulaz.

(Ulazni podaci se učitavaju iz datoteke vojnici.in) U prvom i jedinom redu ulazne datoteke se nalazi broj N (1 ≤ N ≤ 300.000), broj vojnika za koje treba napraviti formaciju.

Izlaz.

(Izlazni podaci se ispisuju u datoteku vojnici.out) U prvom i jedinom redu izlazne datoteke ispisati brojeve R , C i S, tražene brojeve iz zadatka, razdvojene jednim razmakom.
Ukoliko ima više rešenja, ispisati bilo koje.

Primer 1.

12

3 4 98

Objašnjenje. Moguće podele vojnika su 1 x 12, 2 x 6, 3 x 4, 4 x 3, 6 x 2 i 12 x 1. Za podele 3 x 4 i 4 x 3 suma S je najveća moguća, tj. 98.

Primer 2.

4

2 2 12

Primer 2.

5

5 1 8

Napomena.
U 70% test primera je N ≤ 100.000

#include <cstdlib>
#include <cstdio>
#include <memory>

const int MaxN = 1000010;

struct Matrix 
{
  int rowNum;
  int colNum;
  bool m[MaxN];

  Matrix() {}

  void reset(int rows, int cols)
  {
    memset(m, false, sizeof(m));
    rowNum = rows;
    colNum = cols;
  }

  bool get(int i, int j)
  {
    return m[(i - 1) * colNum + (j - 1)];
  }

  void set(int i, int j, bool val)
  {
    m[(i - 1) * colNum + (j - 1)] = val;
  }
};

Matrix M;

long long count(int X, int Y)
{
  long long X1 = X, Y1 = Y;
  long long sol = 2 * (X1 * (Y1 - 1) + Y1 * (X1 - 1));
  int x1, y1;

  M.reset(X, Y);
  for (int x = 1; x < X; x++)
    for (int y = 1; y < Y; y++)
    {
      if (!M.get(x, y))
      {
        sol += 4*(X1 - x)*(Y1 - y);
        x1 = x; y1 = y;
        while (x1 < X && y1 < Y) 
        {
          M.set(x1, y1, true);
          x1 += x; y1 += y;
        }
      }
    }

  return sol;
}

int main()
{
  freopen("vojnici.in", "r", stdin);
  freopen("vojnici.out", "w", stdout);

  int n = 0;
  scanf("%d", &n);

  long long sol = 0, curr = 0;
  int x, y;
  for (int i = 1; i * i <= n; i++)
  {
    if (n % i == 0)
    {
      curr = count(i, n / i);
      if (curr > sol)
      {
        sol = curr;
        x = i;
        y = n / i;
      }
    }
  }

  printf("%d %d %lld\n", x, y, sol);
  return 0;
}

const
  MaxN = 1000010;

var
  inFile, outFile : text;
  rowNum, colNum, x, y, n, i : longint;
  m : array[0..MaxN] of boolean;
  sol, curr : int64;
  
procedure resetMatrix(rows, cols : longint);
begin
  fillchar(m, sizeof(m), false);
  rowNum := rows;
  colNum := cols;
end;

function get(i, j : longint) : boolean;
begin
  get := m[(i - 1) * colNum + (j - 1)];
end;

procedure put(i, j : longint; val : boolean);
begin
  m[(i - 1) * colNum + (j - 1)] := val;
end;

function count(X, Y : longint) : int64;
var
  X1, Y1, sol : int64;
  i, j, dx, dy : longint;
begin
  X1 := X; Y1 := Y;
  sol := 2 * (X1 * (Y1 - 1) + Y1 * (X1 - 1));

  resetMatrix(X, Y);
  for i := 1 to X - 1 do
    for j := 1 to Y - 1 do
      if (NOT get(i, j)) then
      begin
        sol := sol + 4*(X1 - i)*(Y1 - j);
        dx := i; dy := j;
        while ((dx < X) and (dy < Y)) do
        begin
          put(dx, dy, true);
          dx := dx + i; dy := dy + j;
        end;
      end;

  count := sol;
end;

BEGIN

  assign(inFile, 'vojnici.in');
  assign(outFile, 'vojnici.out');
  reset(inFile); rewrite(outFile);
  
  readln(inFile, n);
  sol := 0;
  i := 1;
  
  while (i * i <= n) do
  begin
    if (n mod i = 0) then
    begin
      curr := count(i, n div i);
      if (curr > sol) then
      begin
        sol := curr;
        x := i; y := n div i;
      end;
    end;
    i := i + 1;
  end;

  writeln(outFile, x, ' ', y, ' ', sol);
  close(inFile);
  close(outFile);

END.

#include<stdio.h>
using namespace std;

int x,y;
long long d[1000555];
bool nzd[1000555];

int get(int r, int c) {
    return r*y+c;
}

int main() {

    freopen("vojnici.in", "r", stdin);
    freopen("vojnici.out", "w", stdout);

    int n,i,j,r,c,l,k,pr,pc,resx,resy;
    long long s,res;

    scanf("%d", &n);

    resx = 1;
    resy = n;
    res = (2*(n-2) + 2);

    for(i=2; i*i<=n; i++) if (n % i == 0) {

        x = i; y = n/i;

        for(j=0; j<=n; j++) { d[j]=0; nzd[j]=true; }

        for(r=1; r<x; r++) {
            for(c=1; c<y; c++) {
                //d[get(r,c)] = d[get(r-1,c)] + d[get(r,c-1)] - d[get(r-1,c-1)] + ( nzd[get(r,c)] == true );
                d[r*y+c] = d[(r-1)*y + c] + d[r*y + c-1] - d[(r-1)*y + c-1] + ( nzd[r*y+c] == true );

                for(k=2; k*r < x && k*c < y; k++) {
                    nzd[ k*r*y + k*c ] = false;
                }
            }
        }

        s=0;
        for(r=0; r<x; r++) {
            for(c=0; c<y; c++) {
                s+=4;
                if (r==0) s--;
                if (r==x-1) s--;
                if (c==0) s--;
                if (c==y-1) s--;
                //s += d[get(r,c)] + d[get(x-r,c)] + d[get(r,y-c)] + d[get(x-r,y-c)];
                s += d[r*y+c] + d[(x-r)*y + c] + d[r*y + y-c] + d[(x-r)*y + y-c];
            }
        }

        if (s > res) {
            resx=x; resy=y;
            res=s;
        }
    }

    printf("%d %d %I64d\n", resx, resy, res);

    return 0;
}