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ć.

Ulaz:

(Ulazni podaci se nalaze u datoteci nzd.in.) U prvom redu ulazne datoteke 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 (1 ≤ k < n ≤ 10⁵). Sledeći red sadrži n prirodnih brojeva a_i koji predstavljaju početni niz (a_i ≤ 10⁶). Suma svih brojeva nije veća od 10⁶.

Izlaz:

(Izlazne podatke upisati u datoteku nzd.out) U prvom redu izlazne datoteke ispisati maksimalan moguć najveći zajednički delilac preostalih brojeva. U drugom redu izlazne datoteke ispisati k prirodnih brojeva - izgled niza nakon svih poteza, čiji je najveći zajednički delilac maksimalan. Ukoliko ima više rešenja, štampati bilo koje.

Primer:

6 3
12 7 3 2 15 15

6
12 12 30

Objašnjenje.

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.

#include <cstdlib>
#include <cstdio>

const int MaxN = 100010;
const int MaxDivNum = 1010;

int n, k, s, divNum, groupCount, sol;
int a[MaxN], b[MaxN], divisors[MaxDivNum];

int main()
{
  FILE* inFile = fopen("nzd.in", "r");
  FILE* outFile = fopen("nzd.out", "w");

  fscanf(inFile, "%d%d", &n, &k);
  s = 0;
  for (int i = 0; i < n; i++)
  {
    fscanf(inFile, "%d", &a[i]);
    s += a[i];
  }
  
  divNum = 0;  // nalazimo sve delioce sume
  for (int i = 1; i <= s; i++)
  {
    if (s % i == 0)
      divisors[divNum++] = i;
  }

  for (int j = divNum - 1; j >= 0; j--)
  {
    sol = divisors[j]; // proveravamo da li j-ti delilac moze biti NZD
    groupCount = 0;
    for (int i = 0; i < n; i++) 
      b[i] = 0;

    for (int i = 0; i < n; i++)  // pravimo uzastopne grupe, prelazimo
    {               // na sledecu cim je suma deljiva sa sol
      b[groupCount] += a[i];
      if (b[groupCount] % sol == 0)
      {
        groupCount++;
      }
    }

    if (groupCount >= k)  // ako je broj grupa dovoljno veliki
    {
      break;
    }
  }

  // "spajamo" visak grupa u k-tu
  for (int i = k; i < groupCount; i++)
  {
    b[k - 1] += b[i];
  }

  fprintf(outFile, "%d\n", sol);
  for (int i = 0; i < k - 1; i++)
    fprintf(outFile, "%d ", b[i]);
  fprintf(outFile, "%d\n", b[k - 1]);

  fclose(inFile);
  fclose(outFile);
  return 0;
}

CONST
  MaxN = 100010;
  MaxDivNum = 1010;

VAR
        inFile, outFile : TEXT;
  a, b : array[0..MaxN] of longint;
  divisors : array[0..MaxDivNum] of longint;
  n, k, s, divNum, groupCount, sol, i, j : longint;

BEGIN

  assign(inFile, 'nzd.in');
  assign(outFile, 'nzd.out');
  reset(inFile); rewrite(outFile);

  read(inFile, n, k);
  s := 0;
  for i := 1 to n do begin
    read(inFile, a[i]);
    s := s + a[i];
  end;

  divNum := 0;
  for i := 1 to s - 1 do
    if ((s MOD i) = 0) then begin
      divNum := divNum + 1;
      divisors[divNum] := i;
    end;
  
  for j := divNum downto 1 do begin
  
    sol := divisors[j];
    groupCount := 0;
    for i := 1 to n do b[i] := 0;
    
    for i := 1 to n do begin
      b[groupCount + 1] := b[groupCount + 1] + a[i];
      if ((b[groupCount + 1] MOD sol) = 0) then
        groupCount := groupCount + 1;
    end;
  
    if (groupCount >= k) then break;
  
  end;

  for i := k + 1 to groupCount do
    b[k] := b[k] + b[i];

  writeln(outFile, sol);
  for i := 1 to k - 1 do
    write(outFile, b[i], ' ');
  writeln(outFile, b[k]);

  close(inFile);
  close(outFile);

END.