mister

Se dă următorul algoritm misterios, care are ca date de intrare numerele naturale $N$ și $K$, precum și un șir de $N$ numere naturale $A$ ($A_1, A_2, \ldots, A_N$), iar ca date de ieșire termenii șirului $B$ ($B_1, B_2, \ldots, B_N$). De asemenea, algoritmul utilizează și un șir auxiliar $T$ ($T_0, T_1, \ldots, T_{N-1}$).

1: x ← 0
2: y ← -1
3: pentru i ← 1, N execută
4:     cât timp x ≤ y și A_i > T_y execută
5:         y ← y - 1
6:     sfârșit cât timp
7:     dacă x ≤ y și i - K ≥ 1 și T_x = A_{i-K} atunci
8:         x ← x + 1
9:     sfârșit dacă
10:    y ← y + 1
11:    T_y ← A_i
12:    B_i ← y - x + 1
13: sfârșit pentru

Cerință

Dându-se $N$, $K$ și cei $N$ termeni ai unui șir $B$, să se determine termenii unui șir $A$, cu $1 \le A_i \le N$, pentru orice $i$ de la $1$ la $N$, care ar trebui citiți ca date de intrare în cadrul algoritmului misterios, astfel încât în urma executării acestuia să se obțină ca date de ieșire termenii șirului $B$ dat. Dacă există mai multe soluții, oricare dintre acestea este considerată validă.

Date de intrare

Fișierul de intrare mister.in conține pe prima linie numerele naturale $N$ și $K$, cu semnificația din enunț, iar pe a doua linie $N$ numere naturale, reprezentând termenii șirului $B$. Numerele aflate pe aceeași linie a fișierului sunt separate prin câte un spațiu.

Date de ieșire

Fișierul de ieșire mister.out va conține $N$ numere naturale pe o singură linie, separate prin câte un spațiu, reprezentând, în ordine, termenii șirului $A$.

Restricții și precizări

• $1 \le K \le N \le 200 \ 000$;
• $1 \le B_i \le N$, pentru oricare $i = 1, \ldots, N$, și se garantează că există cel puțin o soluție validă.

Exemplul 1

mister.in

5 3
1 1 1 1 1

mister.out

1 2 3 4 5

Explicație

Pentru primul exemplu un posibil șir $A$, pentru care algoritmul va genera șirul $B = (1, 1, 1, 1, 1)$, este $A = (1, 2, 3, 4, 5)$.

Exemplul 2

mister.in

5 3
1 2 2 2 1

mister.out

5 2 4 3 5

Explicație

Pentru al doilea exemplu ni se cere să găsim un șir $A$ valid care ar produce $B = (1, 2, 2, 2, 1)$. Șirul $A = (5, 2, 4, 3, 5)$ din exemplul de ieșire este doar una dintre soluțiile posibile. O altă soluție validă pentru același șir $B$ ar fi putut fi, de exemplu, $A = (4, 1, 3, 2, 5)$. Orice soluție care respectă condițiile $1 \le A_i \le N$ și generează șirul $B$ în urma rulării algoritmului misterios va fi acceptată.