В поселке функционируют три средние школы №1, №2 и №3. Администрация поселка выделила по k дачных участков для каждой школы. Участки расположены в ряд вдоль автотрассы и нумерованы от 1 до n (n = 3k). Учителя школы №1 уже выбрали себе участки, теперь предстоит распределить участки между учителями школы №2 таким образом, чтобы выбранные k участков имели наименьшую протяженность. (Выбирать участки подряд мешает выбор, сделанный учителями школы №1) Мерой протяженности для выбранных участков является число участков, находящихся между крайними участками (из выбранных участков). Например, если выбраны пять участков с номерами 3, 4, 8, 12, 14, то протяженность этих участков равна 14 – 3 – 1 = 10. Требуется написать программу, которая сделала бы правильный выбор участков для учителей школы №2.

Входные данные: Входной файл состоит двух строк; в первой - одно натуральное число: k – число участков, выделенных для каждой школы; 1  k  999999. Во второй строке - номера участков, выделенных для учителей школы №1. Выходные данные: Выходной файл состоит из k 4 натуральных чисел – номеров участков для учителей школы №2.

Формат ввода
6

1 4 7 12 15 17

Формат вывода
8 9 10 11 13 14

степень

Program Jopascal;  

Var  

 i, A: longint;  

 x,  

 u, j,  

 N, m : longint;  

Function FDiv (A, left : LongInt) : LongInt;  

var  

d,  

i : longint;  

begin  

d := 1;  

for i := left to Trunc (Sqrt (A)) do  

if (A mod i = 0)  

then  

begin  

d := i;  

Break;  

end;  

if (d <> 1)  

then  

FDiv := d  

else  

FDiv := A;  

end;  

Function g (N, u : longint) : longint;  

var  

i : longint;  

begin  

i := 0;  

while (N mod u = 0)  

do

begin  

Inc (i);  

N := N div u;  

end;  

g := i;  

end;  

Begin  

Assign (Input, 'input.txt');  

Assign (Output, 'output.txt');  

Reset (Input);  

Read (A);  

Close (Input);  

m := 0;  

N := 1;  

i := FDiv (A, 2);  

u := 2;  

while (A > 1)  

do  

begin  

N := N * i;  

j := 0;  

while (A mod i = 0)  

do  

begin  

Inc (j);  

A := A div i;  

end;  

if (j > m)  

then  

begin  

m := j;  

u := i;  

end;  

i := FDiv (A, i + 2);  

end;  

x := 1;  

while (g (N * x, u) * N * x < m)  

do  

Inc (x);  

N := N * x;  

ReWrite (Output);  

Write (N);  

Close (Output);  

End.