Problem description


Pociąg Do Sum
(G)
Limit pamięci: 1024 MB
Limit czasu: 2.00 s

Bajtek jest odpowiedzialny za przygotowanie pociągu na coroczną paradę kolejową. Tegoroczny skład ma być wyjątkowy, dlatego Bajtek opracował specjalny plan jego budowy.

Plan jest permutacją a1, a2, …, ad liczb od 1 do d, gdzie d jest nieparzyste.

Na jego podstawie Bajtek buduje pociąg składający się z dwóch rodzajów wagonów: lekkich, ważących 1 tonę, oraz ciężkich, ważących P ton, gdzie

$$ P=1+2+\ldots+d=\frac{d(d+1)}{2}. $$

Wagony są ustawiane w następującej kolejności:

  • najpierw a1 lekkich wagonów,
  • następnie a2 ciężkich wagonów,
  • potem a3 lekkich wagonów,
  • następnie a4 ciężkich wagonów,
  • i tak dalej, aż do ustawienia wszystkich wagonów.

W ten sposób powstaje pociąg składający się z dokładnie P wagonów. Ponieważ d jest nieparzyste, pierwszy i ostatni wagon są lekkie.

Przed paradą pociąg musi przejść kontrolę techniczną. W tym celu pracownik stacji waży wszystkie możliwe niepuste spójne fragmenty pociągu, czyli fragmenty składające się z kolejnych wagonów.

Stacyjna waga ma jednak pewne ograniczenie: podczas jednego pomiaru może znajdować się na niej co najwyżej jedna grupa kolejnych ciężkich wagonów. Innymi słowy, ważony fragment nie może zawierać ciężkich wagonów należących do dwóch różnych grup w utworzonym pociągu.

Pracownik skrupulatnie zapisał wyniki wszystkich dozwolonych pomiarów. Niestety, przez nieuwagę pomieszał swoje notatki, a oryginalny plan budowy pociągu gdzieś zaginął.

Bajtek musi teraz odtworzyć plan, zanim rozpocznie się parada. Pomóż mu znaleźć dowolną permutację, na podstawie której mógł powstać pociąg dający dokładnie takie same wyniki pomiarów.

Wejście

W pierwszym wierszu wejścia znajdują się dwie liczby całkowite P i m, oznaczające odpowiednio liczbę wagonów w pociągu oraz liczbę wykonanych pomiarów.

W drugim wierszu znajduje się m liczb całkowitych s1, s2, …, sm - masy wszystkich niepustych spójnych fragmentów pociągu zawierających co najwyżej jedną grupę ciężkich wagonów, podane w dowolnej kolejności.

Jeżeli kilka różnych fragmentów ma taką samą masę, wynik ten występuje na wejściu odpowiednią liczbę razy.

Możesz założyć, że dane wejściowe zostały wygenerowane zgodnie z opisanym procesem dla pewnej permutacji liczb od 1 do d, gdzie d jest nieparzyste oraz $P=\frac{d(d+1)}2$. Dodatkowo 3 ≤ d ≤ 99 oraz m ≤ 800 000

Wyjście

Wypisz d liczb całkowitych - permutację a1, a2, …, ad, która mogła posłużyć do zbudowania opisanego pociągu.

Jeżeli istnieje wiele poprawnych odpowiedzi, możesz wypisać dowolną z nich.

Ograniczenia

Grupa Dodatkowe warunki Punkty
1 3 ≤ d ≤ 9, m ≤ 700 16
2 d ≤ 21, m ≤ 8 000 30
3 d ≤ 47, m ≤ 85 000 30
4 d ≤ 99, m ≤ 800 000 24

Przykład

Wejście Wyjście Wyjaśnienie
6 21
15 15 6 7 16 7 14 3 12 1 6 1 2 1 13 14 9 8 13 1 2 
1 2 3 

Dla d = 3 oraz permutacji [1,2,3] mamy

$$ P=\frac{3\cdot4}{2}=6. $$

Powstały pociąg składa się z wagonów o następujących masach:

[1,6,6,1,1,1].

Zawiera on tylko jedną grupę ciężkich wagonów, dlatego każdy jego niepusty spójny fragment może zostać zważony.

Łącznie istnieje $\frac{6\cdot7}{2}=21$ takich fragmentów. Ich masy, wraz z powtórzeniami, są dokładnie liczbami podanymi na wejściu.

Drugi test przykładowy powstał z permutacji [1, 2, 3, 4, 5]