D. Петя болон түүний найзууд

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Удахгүй бяцхан Петягийн төрсөн өдөр болох гэж байгаа. Энэ өдрийг тохиолдуулан найзууд нь түүнд чихэр өгөхөөр шийдэв. Петя нийт $n$ найзтай.

Хамгийн их ерөнхий хуваагчийг тайлбарлая. $ХИЕХ(a_1, ... , a_k) = d$ энд $d$ нь бүх $a_i$ тоог үлдэгдэлгүй хуваадаг хамгийн их эерэг бүхэл тоо юм. $a_i$ тоонуудыг эерэг гэж үзнэ.

Петяг програмчлалд дуртайг мэдэх найзууд нь $1$ дэх найз $a_1$ чихэр өгнө, хоёрдох найз $a_2$ чихэр өгнө, ..., $n$ дэх найз $a_n$ чихэр өгнө гэж өмнө шийдэж тохиржээ. Ингэж өгөхдөө тэд дурын $i, j$ ($1 ≤ i, j ≤ n$) хоёрын $ХИЕХ$($a_i, a_j$) нэгээс ялгаатай байхаар мөн $ХИЕХ(a_1, ... , a_n) = 1$ байхаар $a_i$ тоонуудыг сонгохыг хүсэв. Бүх $a_i$ тоонууд нь ялгаатай байна.

Найзуудад $a_1, ... , a_n$ тоонуудыг сонгоход тусална уу.

Оролт

Нэг мөрөнд $n$ ($2 ≤ n ≤ 50$) тоо өгөгдөнө.

Гаралт

Хэрэв хариу олдохгүй бол $-1$ ийг хэвлэ. Үгүй бол хариу болох $n$ ялгаатай $a_1, a_2, ... , a_n$ тоонуудыг тус бүрийг нэг нэг мөрөнд хэвлэж гаргана уу. $a_i$ тоо нь урдаа тэг агуулаагүй байх ёстой ба хамгийн ихдээ $100$ оронтой байж болно. Хэрэв олон шийдтэй байвал хүссэн нэгээ хэвлэ.

Дараах 3 нөхцөл биелж байх ёстой анхаарна уу:

  • дурын $i, j$ ($1 ≤ i, j ≤ n$) хувьд $ХИЕХ(a_i, a_j) ≠ 1$
  • $ХИЕХ(a_1, ... , a_n) = 1$
  • дурын $i, j$ хувьд ($1 ≤ i, j ≤ n, i ≠ j)$: $a_i ≠ a_j$

C++ хэл дээр 64-битийн тоо хэрэглэх үед %lld-г хэрэглэхгүй байхыг зөвлөж байна. %I64d эсвэл cin, cout стриймийг ашиглана уу.

Орчуулсан: Энхсанаа

Жишээ тэстүүд

Оролт
3
Гаралт
99
55
11115
Оролт
4
Гаралт
385
360
792
8360
Сэтгэгдлүүдийг ачааллаж байна...