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.
