SPOJ Brasil

Albert Arnold Gore Jr é o nome completo do ex-vice-presidente dos Estados Unidos, Al Gore, ganhador do prêmio Nobel da Paz de 2007 pelo seu trabalho incessante de conscientizar a população mundial para as mudanças climáticas causadas pelo homem. O documentário "An Inconvenient Truth" vencedor do Oscar, mostra os efeitos causados pelo aquecimento global na paisagem do planeta e prevê um futuro catastrófico para a humanidade se a tendência de usurpar os recursos do planeta não for mudada.

Al Gore cresceu em Washington DC uma vez que seu pai foi deputado e depois senador pelo Tenessee. Graduou-se em Harvard em 1969 e foi um ativista contra a guerra do Vietnam e chegou a apoiar o líder Martin Luther King na sua luta contra a segregação racial. Sua atuação como vice-presidente dos Estados Unidos na administração de Bill Clinton também foi excepcional. Apesar de ter tido mais votos que o concorrente do partido republicano, perdeu as eleições presidenciais e afastou-se da disputa da presidência.

Um dos seus trabalhos mais importantes diz respeito ao posicionamento ótimo de fornos em produção de tijolos. O processo de fabricação de tijolos é bastante poluente, e exige a queima em alta temperatura do barro a fim de que o tijolo atinja a consistência desejada. A queima consome grandes quantidades de madeira, produzida em fazendas para este fim. Estudos da Universidade de Harvard mostram que há uma distância máxima para o posicionamento nesses fornos: se estiverem muito distantes, a dispersão do calor não permite que a queima seja feita por igual, trazendo prejuízos à produção de tijolos e também ao meio ambiente. Uma vez que os fornos são posicionados no meio da floresta (que é cortada para a queima), as distâncias são medidas usando a métrica de Manhattan, ou seja, a distância entre dois pontos é dada pela soma dos valores absolutos das diferenças das coordenadas. Sua tarefa é, dada a localização de vários fornos numa fazenda, e uma distância D, determinar, para cada um dos fornos, quantos fornos estão à distância no máximo D. Com estes dados será possível determinar quais fornos precisam ser acesos simultaneamente sem prejuízos econômico ou ambiental.

Entrada

A primeira linha do caso de testes contém um inteiro I que indica o número de instâncias subsequentes. A primeira linha de cada instância possui dois inteiros N e D (1 ≤ D ≤ 500000, 1 ≤ N ≤ 100000) representando o número de fornos e uma distância, respectivamente. Cada uma das próximas N linhas possui dois inteiros x e y (0 ≤ x, y ≤ 100000) que indicam a posição de um forno.

Saída

Para cada instância imprima uma linha contendo N inteiros que indicam quantos fornos estão à distância no máximo D dos fornos 1, 2, ..., N.

Exemplo de entrada
1
13 2
0 2
1 3
1 2
1 1
2 4
2 3
2 2
2 1
2 0
3 3
3 2
3 1
4 2
Exemplo de saída
4 7 7 7 4 7 12 7 4 7 7 7 4