Tassadar vrea să exploreze un templu Xel’Naga, dar pentru a putea intra, trebuie să introducă un cod secret. În urma unor calcule matematice, a făcut câteva observaţii cu ajutorul cărora poate descoperi codul secret.
Fie o constantă $K$ şi un şir $V$ de $N$ numere întregi. Fiecare poziţie $i$ din şir are asociat un cost $C{~i~}$. Definim $Next{~i~} = max(i, min(j | i < j, V{~i~} < V{~j~}))$, iar $Next{~i~}^P^ = Next{~Next{~i~}~}^(P – 1)^$.
Fie şirul $S$ de $N$ numere întregi, $S{~i~} = min(C{~i~}, C{~Next{~i~}~}, Cost[Next^2[i]], ..., Cost[Next^K[i]])$. Codul secret este chiar şirul $S$!
Fie şirul $S$ de $N$ numere întregi, $S{~i~} = min(C{~i~}, C{~Next{~i~}~}, C{~Next{~i~}^2^~}, ..., C{~Next{~i~}^K^~})$. Codul secret este chiar şirul $S$!
Tassadar a reuşit să pătrundă în templul Xel’Naga. Voi puteţi?
h2. Date de intrare
Fişierul de intrare $temple.in$ ...
Fişierul de intrare $temple.in$ conţine pe prima linie două numere întregi $N$ şi $K$ cu semnificaţia din enunţt. Pe a doua linie se află $N$ numere întregi $V{~i~}$ reprezentând şirul $V$. Linia următoare conţine $N$ numere întregi $C{~i~}$ reprezentând costurile poziţiilor din şirul $V$.
h2. Date de ieşire
În fişierul de ieşire $temple.out$ ...
În fişierul de ieşire $temple.out$ veţi afişa pe prima linie $N$ numere întregi $S{~i~}$ reprezentând codul secret.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ K ≤ N ≤ 10^5^$
* $1 ≤ V{~i~} ≤ 10^9^$
* $-10^15^ ≤ C{~i~} ≤ 10^15^$
h2. Exemplu
