pian

Note: este posibil ca această problemă să nu aibă soluția oficială corectă.

Ian este un copil pasionat de muzică, așa că părinții săi i-au cumpărat de ziua lui un pian. Pianul lui Ian este mai special, acesta are $N$ clape. Întrucât pianul nu este nou, clapele se mișcă mai greu, astfel apăsarea celei de-a $i$-a clape durează $t_i$ secunde.

Deoarece Ian este foarte nerăbdător, s-a hotarât să repare clapele pianului pentru ca apăsarea unei clape să fie cât mai rapidă. Acesta poate selecta două clape vecine $i$ și $i+1$ ce necesită $t_i$, respectiv $t_{i+1}$ secunde pentru a fi apăsate și le lustruiește. În urma lustruirii, cele două clape vor necesita doar $cmmdc(t_i, t_{i+1})$ secunde pentru apăsarea fiecăreia. Practic, o operație va efectua următoarea transformare asupra clapelor: $t_i$ = $t_{i + 1}$ = $cmmdc(t_i, t_{i+1})$.

Ian consideră ca pianul este lustruit dacă timpul de apăsare al fiecărei clape este minim posibil.

Cerința

1. Ian vrea să facă un riff (adică să apese fiecare clapă o singură dată) și vrea să știe care ar fi durata de timp a unui riff pe pianul lustruit.
2. Pentru că Ian nu are timp de pierdut cu lustruitul, acesta vrea o listă de instrucțiuni de lungime minimă asfel încât dupa efectuarea instrucțiunilor pianul să fie lustruit.

Date de intrare

Fișierul de intrare pian.in conține pe prima linie numărul $C$ ce reprezintă cerința care trebuie rezolvată. Pe următoarea linie se află $N$, numărul de clape ale pianului. Pe următoarea linie se vor afla $N$ numere separate prin câte un spațiu, al $i$-lea număr reprezentând durata inițială $t_i$ necesară pentru apăsarea clapei cu indicele $i$.

Date de ieșire

În fișierul pian.out se vor afișa în funcție de cerință următoarele:

Dacă $C = 1$, atunci fișierul va conține o singură linie cu un singur număr $S$, ce reprezintă răspunsul pentru prima cerință.
Dacă $C = 2$, atunci fișierul va conține pe prima linie un număr $M$ care reprezintă numarul minim de operații pe care Ian trebuie să le facă, iar pe următoarea linie $M$ numere separate prin câte un spatiu, al $i$-lea număr $x_i$, reprezentând faptul că a $i$-a operație de lustruire a clapelor se va face între clapele cu indicii $x_i$ și $x_i + 1$.

Restricții și precizări

• $C \in \{1, 2 \}$
• $1 \leq N \leq 100 \ 000$
• $1 \leq v_i \leq 1 \ 000 \ 000$, pentru orice $i \in \{1, 2, \dots, N \}$
• $1 \leq x_j < N$, pentru orice $j \in \{1, 2, \dots, M \}$
• Daca pentru cerința $2$ există mai multe soluții cu număr minim de operații se acceptă oricare.
• Pentru teste în valoare de $19$ de puncte: $C = 1$
• Pentru alte teste în valoare de $38$ de puncte: $C = 2$ si $1 \leq N \leq 1 \ 000$
• Pentru alte teste în valoare de $43$ de puncte: $C = 2$ si nu există alte restricții suplimentare.

Exemplul 1

pian.in

1
5
2 4 6 8 10

pian.out

10

Exemplul 2

pian.in

2
5
2 4 6 8 10

pian.out

2
2 4

Explicație

Ian poate lustrui pianul în doar $2$ instrucțiuni în următorul mod:

Aplicăm operația pe clapele $2$ și $3$. Obținem șirul $2 \ 2 \ 2 \ 8 \ 10$
Aplicăm operația pe clapele $4$ și $5$. Obținem șirul $2 \ 2 \ 2 \ 2 \ 2$

În final se va obține șirul de clape: $2 \ 2 \ 2 \ 2 \ 2$. Astfel, durata unui riff va fi de $10$ secunde.