Informática - Nível Intermediário - Semana 41

??Comprando Bombons??

Valente está se preparando para o halloween e precisa comprar as guloseimas que vai distribuir no dia. Para isso ele vai até a loja OBI (Oásis dos Bombons Incríveis), um lugar extramamente conceituado no mundo dos doces. A loja tem n bombons disponíveis e eles são numerados de 1 até n, com um bombom de número menor que outro sendo sempre melhor que o de número maior. Por conta da data festiva ela só está vendendo os bombons em pacotes, tendo também n pacotes disponíveis; o i-ésimo pacote contém exatamente 1 bombom de cada tipo 1 \leq j \leq i e custa p_i moedas.

Sendo um estudante ele só tem m moedas em seu orçamento, e deseja comprar o máximo de bombons possíveis seguindo a regra de sempre priorizar a quantidade dos bombons melhores; em outras palavras, ele deseja ter a maior distrubuição lexicograficamente de bombons possível usando até m moedas. Como ele não sabe programar, pediu sua ajuda para encontrar a quantidade que ele vai conseguir comprar de cada bombom em uma distribuição ideal de suas moedas.

Entrada

O input consiste de múltiplos casos de teste. A primeira linha contém um inteiro t (1 \leq t \leq 10^4) - o número de casos de teste.

A primeira linha de cada caso de teste contém o inteiro n (1 \leq n \leq 2 \times 10^5), a quantidade de bombons e de pacotes disponíveis. A segunda linha contém n inteiros p_i (1 \leq p_i \leq 10^9), os preços de cada pacote. A terceira linha contém um inteiro m, a quantidade máxima de moedas que Valente pode usar.

É garantido que a soma de n sobre todos os casos de teste não excede 2 \times 10^5.

Saída

Para cada caso de teste imprima n inteiros b_1, b_2, ..., b_n - a maior distrubuição lexicograficamente de bombons possível usando até m moedas.

Exemplos

Entrada Saída
4
3
1 2 3
5
2
3 4
7
3
3 2 1
2
6
10 6 4 6 3 4
7
5 0 0 
2 1 
2 2 2 
2 2 2 2 2 1

Para submeter sua solução use esse link