Zadanie

Komplikovaná rekonštrukcia permutácie

Počet bodov: 70

Daná je postupnosť $a_1,a_2,\dots$ celých čísel, inverzia je dvojica indexov $i,j$ taká, že $i<j$ ale $a_i > a_j$.

Permutácia rádu $n$ je postupnosť $p_1,\dots,p_n$ ktorá obsahuje každé číslo medzi 1 a $n$ práve raz.

Daná je permutácia $p$ a kladné celé číslo $k$, definujeme novú postupnosť $q_1,\dots,q_{n-k+1}$ nasledovne: pre každé $i$, nech $q_i$ je počet inverzií v postupnosťi $p_i,p_{i+1},\dots,p_{i+k-1}$.

Na príklad, nech $p=(3,1,2,5,4)$ a $k=3$. Potom:

• $q_1 = {\rm inverzie}(3,1,2) = 2$
• $q_2 = {\rm inverzie}(1,2,5) = 0$
• $q_3 = {\rm inverzie}(2,5,4) = 1$

Úloha

Na vstupe sú hodnoty $n$, $k$, postupnosť $q$, so zárukou, že pre dané dáta existuje aspoň jedna permutácia $p$ z ktorej vznikne postupnosť $q$. Zrekonštruujte ľubovolnú takú permutáciu.

Vstup a výstup

Prvý riadok obsahuje čísla $n$ a $k$.

Na druhom riadku sú hodnoty $q_1, \dots, q_{n-k+1}$.

Vypíšte jeden riadok s $n$ medzerou oddeleními číslami: permutáciou $p$.

Obmedzenia

Podúloha 1 (5 bodov):$2\leq n\leq 5$,$k=2$.

Podúloha 2 (10 bodov):$2\leq n\leq 5$,$2\leq k\leq n$.

Podúloha 3 (10 bodov):$2\leq n\leq 1000$,$k=2$.

Podúloha 4 (30 bodov):$5\leq n\leq 1000$,$2\leq k\leq 6$.

Podúloha 5 (10 bodov):$2\leq n\leq 100\,000$,$k=2$.

Podúloha 6 (30 bodov):$2\leq n\leq 100\,000$,$2\leq k\leq 6$.

Podúloha 7 (5 bodov):$2\leq n\leq 200\,000$,$2\leq k\leq 9$.

Príklad

Input:

5 3
2 0 1

Output:

3 1 2 5 4

Toto je príklad ukázaný v zadaní.