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