\(n\) lopova natječe se u, pogodite čemu, naravno, u krađi. Lopov \(i\) ima \(a_i\) godina iskustva te kod sebe drži \(b_i\) eura. Godine iskustva kreću se od \(1\) do \(n\) te niti jedna dva lopova neće imati isti broj godina iskustva. Lopov može opljačkati drugog lopova samo ako ima strogo više godina iskustva od njega. Lopov može opljačkati najviše \(k\) drugih lopova bez da bude uhvaćen te nikada neće opljačkati istog lopova više puta.

Za svakog lopova ispišite najveću moguću svotu novca koju može ukrasti. Svaki lopov računa se zasebno te lopovi ne utječu međusobno jedan na drugog.

Ulazni podatci

U prvome retku nalaze se prirodni brojevi \(n\) (\(1 \leq n \leq 2 \cdot 10^5\)) i \(k\) (\(1 \leq k \lt n\)).

U drugome retku nalazi se \(n\) brojeva \(a_i\) (\(1 \leq a_i \leq n\)), broj godina iskustva i-tog lopova.

U trećem retku nalazi se \(n\) brojeva \(b_i\) (\(1 \leq b_i \leq 10^9\)), svota novca kod i-tog lopova.

Izlazni podatci

Ispišite odgovor za svakog lopova redom njihovih indeksa, odvojeno razmakom.

Podzadatci

Ulaz primjera 1

4 2
2 1 4 3
15 10 30 50

Izlaz primjera 1

10 0 65 25

Pojašnjenje primjera 1

Lopov \(1\) ukrade \(10\) eura od lopova \(2\). Lopov \(2\) ima najmanje iskustva, pa ne može ukrasti od nikoga. Lopov \(3\) ukrade \(15\) od lopova \(1\) i \(50\) od lopova \(4\). Lopov \(4\) ukrade od lopova \(1\) i \(2\).

Ulaz primjera 2

5 3
5 4 2 1 3
48 10 13 40 20

Izlaz primjera 2

73 73 40 0 53

Ulaz primjera 3

7 6
1 7 2 6 4 5 3
72 20 67 94 93 53 50

Izlaz primjera 3

0 429 72 335 189 282 139