C.Zəncirvari ƏBOB

Sizə bir tam ədəd $N$ verilir. Aşağıdakı şərtlərin hamısını ödəyən, uzunluğu $N$ olan

$$A = [a_1, a_2, \ldots, a_N]$$

ardıcıllığını qurun. Ardıcıllıqdakı bütün ədədlər müsbət və cüt-cüt fərqli olmalıdır.

1. Qonşuluq şərti. Hər iki qonşu elementin ən böyük ortaq böləni (ƏBOB) $1$-dən böyük olmalıdır:

   $$\gcd(a_i,a_{i+1}) > 1 \qquad (1 \le i < N).$$

2. Üçlük şərti. Ardıcıl hər üç elementin ƏBOB-u dəqiq $1$ olmalıdır:

   $$\gcd(a_i,a_{i+1},a_{i+2}) = 1 \qquad (1 \le i < N-1).$$

3. Qiymət aralığı. Hər bir element $1$ ilə $10^9$ arasında, sərhədlər daxil olmaqla, olmalıdır:

   $$1 \le a_i \le 10^9.$$

Verilən məhdudiyyətlər daxilində hər bir $N$ üçün düzgün ardıcıllığın mövcud olduğu təmin edilir.

Giriş verilənləri

Yeganə sətirdə bir tam ədəd $N$ ($3 \le N \le 10^5$) — tələb olunan ardıcıllığın uzunluğu verilir.

Çıxış verilənləri

Şərtlərin hamısını ödəyən, boşluqlarla ayrılmış $N$ tam ədəd çap edin. Bütün ədədlər cüt-cüt fərqli olmalıdır. Bir neçə düzgün cavab varsa, onlardan istənilən birini çap edə bilərsiniz.

Məhdudiyyətlər

• $3 \le N \le 10^5$
• $1 \le a_i \le 10^9$
• $a_i$ qiymətləri cüt-cüt fərqli olmalıdır.

Qiymətləndirmə

Məsələ ümumilikdə 150 bal təşkil edir. Nümunə yalnız izah üçündür və bal hesablanmasına daxil edilmir.

• Alt tapşırıq 1 — 20 bal: $3 \le N \le 100$.
• Alt tapşırıq 2 — 50 bal: $3 \le N \le 2000$.
• Alt tapşırıq 3 — 80 bal: əlavə məhdudiyyət yoxdur; əsas məhdudiyyət $3 \le N \le 10^5$ qüvvədədir.

Alt tapşırıq balları müstəqil test qrupları vasitəsilə hesablanır. Hər qrupun bütün testləri keçildikdə həmin qrupun balları verilir.

Nümunənin izahı

Bu çıxış üçün:

• $\gcd(14, 21) = 7 > 1$;
• $\gcd(21, 33) = 3 > 1$;
• $\gcd(33, 22) = 11 > 1$;
• $\gcd(14, 21, 33) = 1$;
• $\gcd(21, 33, 22) = 1$.

Dörd ədədin hamısı fərqlidir və $[1, 10^9]$ aralığındadır.

4

14 21 33 22