Uses crt;
Var a:array[1..1000] of longint;
    i,j,n,tam,aint_p,aint_d,cout:longint;
 function nt(n:longint):boolean;
 Var i:longint;
 begin
  if n<=1 then nt:=false else
   begin
     for i:=2 to (n div 2)+1 do 
      If n mod i=0 then begin nt:=false; break; end;
    If i=(n div 2)+1 then nt:=true;
   end
 end;
begin
 write('n: ');readln(n);           
 For i:=1 to n do 
 Begin
  read(A[i]);
     For j:=1 to n do 
     If A[i]<A[j] then Begin Tam:=A[i]; A[i]:=A[j]; A[j]:=Tam; End;
    End;
    writeln('-');
    For i:=1 to n do write(a[i],' '); writeln;
    For i:=1 to n do 
    begin
     If nt(a[i]) then write(a[i],' ') else
      Begin aint_p:=a[i]; aint_d:=a[i];
      While (nt(aint_p)=false)and(cout<=100) do inc(aint_p); 
         While (nt(aint_d)=false)and(aint_d>=2)and(cout<=100) do dec(aint_d);
         If (aint_p-a[i])<(a[i]-aint_d) then write(aint_p,' ') else 
         If (aint_p-a[i])>(a[i]-aint_d) then write(aint_d,' ') else write(aint_p,' ');
         End;
    end;
readln
end.