Prokopije i Simonid su najbolji matematičari u razredu. Njihov drug Đurađ je zbog toga ljubomoran na njih pa im stalno smišlja neke smicalice. Ovoga puta je zamislio dva (ne obavezno različita) broja iz intervala [a,b] i saopštio Prokopiju njihov proizvod a Simonidu njihovu sumu (njih dvojica znaju iz kog intervala su odabrani ti brojevi). Prokopije i Simonid dalje vode sledeći razgovor:

P: „Ja ne znam koji su to brojevi“.
S: „Ja ne znam koji su to brojevi“.
-------------------------------------------
P: „Ja ne znam koji su to brojevi“.
S: „Ja ne znam koji su to brojevi“.
-------------------------------------------
.
.
.
-------------------------------------------
P: „Ja ne znam koji su to brojevi“.
S: „Ja ne znam koji su to brojevi“.
-------------------------------------------
P: „Sad znam koji su to brojevi“.

Poznato je da su Prokopije i Simonid po n puta izrekli rečenicu „Ja ne znam koji su to brojevi“, pre nego što je Prokopije saopštio da zna koji su to brojevi. Koje brojeve je zamislio Đurađ?

Ulaz:

U prvom i jedinom redu ulazne datoteke prosim.in se nalaze prirodni brojevi a, b, n (1 ≤ a < b ≤ 1000, 1 ≤ n ≤ 10, b - a ≤ 128) razdvojeni prazninom, koji označavaju, redom, početak i kraj intervala i broj ponavljanja goreoznačenog bloka u razgovoru.

Izlaz:

U prvom i jedinom redu izlazne datoteke prosim.out ispisati brojeve koje je Đurađ zamislio razdvojene prazninom, najpre manji pa veći (ukoliko su različiti).

Primer:

1 9 1

1 4

Objašnjenje:

Prokopiju je saopšten broj 4, Simonidu broj 5. Prokopije razmišlja: „Pošto je 4=1*4=2*2, ne mogu znati koje je brojeve zamislio Đurađ jer su obe kombinacije moguće“, i kaže: P: „Ja ne znam koji su to brojevi“. Simonid razmišlja: „Moguće su kombinacije 1, 4 kao i 2, 3. U prvom slučaju Prokopiju bi bio saopšten broj 4 i tada bi on bio u dilemi između kombinacija 1, 4 i 2, 2. U drugom slučaju bi mu bio saopšten broj 6 i bio bi u dilemi između kombinacija 1, 6 i 2, 3. Dakle, u oba slučaja bi Prokopije bio u dilemi (kao što i jeste), pa ne mogu znati o kom od njih se radi“, i kaže: S: „Ja ne znam koji su to brojevi“. Prokopije razmišlja: „Znam da je Simonidu saopšten ili broj 5 ili broj 4. Ukoliko bi to bio broj 4 on bi zaključio da su u pitanju brojevi 2, 2 jer bi u suprotnom meni bio saopšten broj 3 i odmah bih znao da je kombinacija 1, 3, ne bih bio u dilemi. Pošto Simonid ne zna koje je brojeve Đurađ zamislio ostaje jedino kombinacija 1, 4“, i kaže: P: „Sad znam koji su to brojevi“.

Napomena:

Garantuje se da će za sve test-primere rešenje biti jedinstveno.

Za svaki proizvod p u niz pr_p.d_i pamtimo sume svake moguće kombinacije koja mu odgovara, a koja je prihvatljiva. Analogno za sume s pamtimo u niz sum_s.d_i. Na početku su sve kombinacije prihvatljive, a onda u svakoj od n iteracija iz svake sume izbacujemo one proizvode koji imaju jedinstvenu prihvatljivu sumu (njih smo ranije smestili u niz zaup). Istovremeno u niz zaus smeštamo one sume koje imaju jedinstven prihvatljiv proizvod, koje dalje analogno izbacujemo iz odgovarajućih proizvoda. Nakon završetka petlje imaćemo jedan proizvod u nizu zaup, i na osnovu njega i sume koje mu odgovara (jedinstvene) možemo lako izračunati zamišljenje brojeve.

Preudokod

za svaki proizvod/sumu formirati niz pr[p].d/sum[s].d svih odgovarajućih suma/proizvoda

formirati niz zaup[i] proizvoda koji imaju jedinstvenu prihvatljivu sumu

for k = 1 to n do
	for p in zaup
		izbaci(p,sum[pr[p].d[1]].d)
		if length(sum[pr[p].d[1]])=1
			ubaci(pr[p].d[1],zaus)
		else
			if length(sum[pr[p].d[1]])=0
				izbaci(pr[p].d[1],zaus)
	for s in zaus
		izbaci(s,pr[sum[s].d[1]].d)
		if length(pr[sum[s].d[1]])=1
			ubaci(sum[s].d[1],zaup)
		else
			if length(pr[sum[s].d[1]].d)=0
				izbaci(sum[s].d[1],zaup)

rešiti sistem jednacina x*y=zaup[1] i x+y=pr[zaup[1]].d[1]

traženi brojevi su x i y

const gr=1000;
      int=128;
type matrp=record
            br:longint;
            d:array[1..gr] of byte;
           end;
     matrs=record
            br:longint;
            d:array[1..gr] of longint;
           end;
     tzau=record
           br:longint;
           d:array[1..gr*gr] of longint;
          end;
var a,b,n,i,j,k:longint;
    zaup,zaus:tzau;
    sum:array[0..2*int] of matrs;
    pr:array[0..gr*gr-(gr-int)*(gr-int)] of matrp;
    f:text;
procedure izbacis(u:longint;var niz:matrs);
begin
 j:=1;
 while ((niz.d[j]<>u)and(j<=niz.br)) do
    inc(j);
 if j<=niz.br then begin
                    niz.d[j]:=niz.d[niz.br];
                    dec(niz.br);
                   end;
end;
procedure izbacip(u:longint;var niz:matrp);
begin
 j:=1;
 while ((niz.d[j]<>u)and(j<=niz.br)) do
    inc(j);
 if j<=niz.br then begin
                    niz.d[j]:=niz.d[niz.br];
                    dec(niz.br);
                   end;
end;
procedure izbaci(u:longint;var niz:tzau);
begin
 j:=1;
 while ((niz.d[j]<>u)and(j<=niz.br)) do
    inc(j);
 if j<=niz.br then begin
                    niz.d[j]:=niz.d[niz.br];
                    dec(niz.br);
                   end;
end;
procedure skini_pr;
begin
 zaus.br:=0;
 for i:=1 to zaup.br do
   begin
    izbacis(zaup.d[i],sum[pr[zaup.d[i]-a*a].d[1]]);
    if sum[pr[zaup.d[i]-a*a].d[1]].br=1 then begin
                                              inc(zaus.br);
                                              zaus.d[zaus.br]:=pr[zaup.d[i]-a*a].d[1];
                                             end
                                        else if sum[pr[zaup.d[i]-a*a].d[1]].br=0 then izbaci(pr[zaup.d[i]-a*a].d[1],zaus);
   end;
end;
procedure skini_sumu;
begin
 zaup.br:=0;
 for i:=1 to zaus.br do
   begin
    izbacip(zaus.d[i],pr[sum[zaus.d[i]].d[1]-a*a]);
    if pr[sum[zaus.d[i]].d[1]-a*a].br=1 then begin
                                              inc(zaup.br);
                                              zaup.d[zaup.br]:=sum[zaus.d[i]].d[1];
                                             end
                                        else if pr[sum[zaus.d[i]].d[1]-a*a].br=0 then izbaci(sum[zaus.d[i]].d[1],zaup);

   end;
end;
begin
 assign(f,'prosim.in');
 reset(f);
 readln(f,a,b,n);
 close(f);
 for i:=a*a to b*b do
   pr[i-a*a].br:=0;
 for i:=2*a to 2*b do
   sum[i-2*a].br:=0;
 for i:=a to b do
   for j:=i to b do
     begin
      inc(pr[i*j-a*a].br);
      pr[i*j-a*a].d[pr[i*j-a*a].br]:=i+j-2*a;
      inc(sum[i+j-2*a].br);
      sum[i+j-2*a].d[sum[i+j-2*a].br]:=i*j;
     end;
 zaup.br:=0;
 for i:=a*a to b*b do
   if pr[i-a*a].br=1 then begin
                           inc(zaup.br);
                           zaup.d[zaup.br]:=i;
                          end;
 for k:=1 to n do
   begin
    skini_pr;
    skini_sumu;
   end;
 assign(f,'prosim.out');
 rewrite(f);
 for i:=1 to zaup.br do
   writeln(f,trunc(((pr[zaup.d[i]-a*a].d[1]+2*a)-sqrt((pr[zaup.d[i]-a*a].d[1]+2*a)*(pr[zaup.d[i]-a*a].d[1]+2*a)-4*zaup.d[i]))/2),
            ' ',(pr[zaup.d[i]-a*a].d[1]+2*a)-
           trunc(((pr[zaup.d[i]-a*a].d[1]+2*a)-sqrt((pr[zaup.d[i]-a*a].d[1]+2*a)*(pr[zaup.d[i]-a*a].d[1]+2*a)-4*zaup.d[i]))/2));
 close(f);
end.

/* Resenje takmicara Ivana Labata */


#include <cstdlib>
#include <iostream>

using namespace std;

class par
{
  public: 
    par() {};
    par(int ax, int ay, int as): x(ax), y(ay), s(as), rem(false) {};
    inline bool operator==(const par& rhs) const 
      {return (x == rhs.x && y == rhs.y);}
    inline bool operator<(const par& rhs) const
      {
        if (s < rhs.s) return true;
        if (s > rhs.s) return false;
        if (x < rhs.x) return true;
        if (x > rhs.x) return false;
        if (y < rhs.y) return true;
        return false;
      }
    int x,y,s;
    bool rem;
};

ostream & operator<< (ostream & o, const par & pr)
{
  char s[100];
  sprintf(s,"%(%d:%d,%d,%d)",pr.s,pr.x,pr.y,pr.rem);
  o << s;
}

int A = 0;
int B = 0;
int N = 0;
par * P;
par * Pn; //last+1
par * S;
par * Sn;


void 
read_from_file(const char * filename)
{
  FILE * fi = fopen(filename,"r");
  fscanf(fi,"%d %d %d",&A,&B,&N);
  fclose(fi);
}

void 
read_from_stdin()
{
  scanf("%d %d %d",&A,&B,&N);
}

inline void
add(int x, int y)
{
  Pn->x = x;
  Pn->y = y;
  Pn->s = x*y;
  Pn->rem = false;
  ++Pn;
  Sn->x = x;
  Sn->y = y;
  Sn->s = x+y;
  Sn->rem = false;
  ++Sn;
}

void 
make()
{
  int n = (B-A+1)*(B-A+2)/2;
  P = new par[n+5];  
  Pn = P;
  S = new par[n+5];  
  Sn = S;
  for (int i=A; i<=B; ++i)
    for (int j=i; j<=B; ++j)
      add(i,j);
  sort(P,Pn);
  sort(S,Sn);
}

void
rem(par p, par * s, par * sn)
{
  par * f = lower_bound(s, sn, p);
  if (*f == p)
    f->rem = true;
  else
    cerr << "No match for " << p << "lower bound is " << *f << endl;
}

void
remove_pro()
{
  par * n = P;
  par * l = P;
  while ((n < Pn) && (n->rem))
    ++n;
  while (n < Pn)
  {
    par * f = n;
    int c = 0;
    for (; f->s == n->s; ++n)
      if (!n->rem)
        ++c;
    if (c == 1)
    {
      rem(par(f->x, f->y, f->x + f->y), S, Sn);
    }
    else if (c > 1)
    {
      while (f < n)
      {
        if (!f->rem)
          *l++ = *f++;
        else
          ++f;
      }      
    }    
    while ((n < Pn) && (n->rem))
      ++n;
  }
  Pn = l;
}

void
remove_sim()
{
  par * n = S;
  par * l = S;
  while ((n < Sn) && (n->rem))
    ++n;
  while (n < Sn)
  {
    par * f = n;
    int c = 0;
    for (; f->s == n->s; ++n)
      if (!n->rem)
        ++c;
    if (c == 1)
    {
      rem(par(f->x, f->y, f->x * f->y), P, Pn);
    }
    else if (c > 1)
    {
      while (f < n)
      {
        if (!f->rem)
          *l++ = *f++;
        else
          ++f;
      }      
    }    
    while ((n < Sn) && (n->rem))
      ++n;
  }
  Sn = l;
}

void
find_pro()
{
  par * n = P;
  while ((n < Pn) && (n->rem))
    ++n;
  while (n < Pn)
  {
    par * f = n;
    int c = 0;
    for (; f->s == n->s; ++n)
      if (!n->rem)
        ++c;
    if (c == 1)
    {
      printf("%d %d\n",f->x, f->y);
    }
    while ((n < Pn) && (n->rem))
      ++n;
  }
}


void 
solve()
{
  for (int i=0; i<N; ++i)
  {
    remove_pro();
    remove_sim();
  } 
  find_pro();
}

int 
main(int argc, char *argv[])
{
  if (argc-1 >= 1)
    read_from_file(argv[1]);
  else
    read_from_stdin();
  make();
  solve();
  return EXIT_SUCCESS;
}