Obeleži sve kategorije koje odgovaraju problemu

Dat je niz prirodnih brojeva a od n elemenata. U jednom potezu dozvoljeno je odabrati proizvoljna dva susedna broja u nizu i zameniti ih njihovim zbirom. Na primer, ukoliko smo odabrali brojeve a_i i a_{i + 1}, niz (a₁, a₂, ..., a_i, a_{i + 1}, ... a_n) postaje (a₁, a₂, ..., a_i + a_{i + 1}, ... a_n). Ovo zatim možemo ponavljati na novodobijenim nizovima (primetimo da se broj elemenata niza svaki put smanjuje za 1).

Primeniti određeni broj poteza nad početnim nizom, tako da na kraju dobijemo tačno k brojeva čiji je najveći zajednički delilac najveći moguć.

U prvom redu standardnog ulaza nalaze se 2 prirodna broja n i k koji predstavljaju, redom, broj elemenata u početnom nizu i broj elemenata koji treba ostati na kraju. Sledeći red sadrži n prirodnih brojeva a_i (razdvojenih razmakom) koji predstavljaju početni niz. 

U prvom redu standardnog ispisati maksimalni moguć najveći zajednički delilac preostalih brojeva. U drugom redu ispisati k prirodnih brojeva razdvojenih razmakom - izgled niza nakon svih poteza, čiji je najveći zajednički delilac maksimalan. Ukoliko ima više rešenja, štampati bilo koje.

1 ≤ k < n ≤ 100.000

1 ≤ a_i ≤ 1.000.000

Suma svih elemenata niza a nije veća od 1.000.000.

Ukoliko izvršimo poteze (12, 7, 3, 2, 15, 15) → (12, 10, 2, 15, 15) → (12, 10, 2, 30) → (12, 12, 30) dobijamo brojeve 12, 12 i 30 čiji je najveći zajednički delilac jednak 6. Nije moguće dobiti 3 broja sa većim najvećim zajedničkim deliocem.