Biblioteca Alfabetizada
time limit per test
1 segundo
memory limit per test
256 megabytes
input
entrada padrão
output
saída padrão

As bibliotecas públicas de Nlogônia estão um caos! Os livros estão todos fora do lugar nas prateleiras! Para nossa sorte, todos os sistemas são informatizados, então temos uma verdadeira bagunça organizada, que é terrível de se consultar manualmente, mas com o auxílio do sistema, é possível encontrar a localização de todos os livros.

O ministério dos livros não está muito feliz com essa situação, porque se o sistema parar de funcionar, ninguém sabe onde os livros estão. Pensando em resolver esse problema, o ministério então recrutou uma equipe de bibliotecários para resolver esse problema. O problema é que não se sabe quais lugares estão mais desorganizados que outros.

Para medir o trabalho que vai levar para organizar os livros de cada biblioteca, eles pensaram numa métrica que eles chamam de grau de desorganização. O grau de desorganização é dado pela quantidade de conjuntos de dois livros que estão na ordem errada.

O livro "problemas que ninguem quer resolver parte 5" por exemplo está fora de ordem apenas em relação aos livros "a sequencia que ninguem esperava 2" e "promessas vazias". Isto é contrastado por exemplo ao livro "a sequencia que ninguem esperava 2" que está fora de ordem em relação a todos os outros livros. Lembre-se que são conjuntos, então a relação {"a sequencia que ninguem esperava 2", "problemas que ninguem quer resolver parte 5"} é contada apenas uma vez. O grau de desorganização dessa estante é $$$15$$$.

O ministério então precisa da sua ajuda para distribuir a equipe! Sabendo do grau de desorganização de cada biblioteca, distribua a equipe, dizendo quantos devem trabalhar em cada biblioteca. Cada biblioteca desorganizada inicialmente deve ter um bibliotecário, e em seguida, o restante deve ser distribuído conforme a proporção dada pelo grau de desorganização. Caso sobre bibliotecários, eles deverão ser distribuídos um a um em ordem para os lugares mais desorganizados, escolhendo no caso de empate os listados primeiro.

Input

A primeira linha é dada pelo inteiro $$$N$$$ $$$(1 \le N \le 10^5)$$$, a quantidade de bibliotecas e o inteiro $$$K$$$ $$$(1 \le K \le 10^{10})$$$, o tamanho da equipe que deve ser dividida entre as bibliotecas. É garantido que $$$K$$$ é maior ou igual ao número de bibliotecas desorganizadas.

Em seguida, cada biblioteca é descrita por uma linha com um inteiro $$$L$$$ $$$(1 \le L \le 10^5)$$$ seguida de $$$L$$$ linhas, cada uma contendo a descrição de cada livro da biblioteca em sua ordem original na prateleira.

A descrição do livro é composta por um inteiro $$$M$$$ $$$(1 \le M \le 60)$$$ que determina o tamanho do nome do livro, um espaço e o nome do livro (que não possui espaços no começo ou no final). O nome dos livros possui apenas caracteres de espaço, números e o alfabeto latino minúsculo, que tem ordem lexicográfica definida nesta ordem.

É garantido que a soma de todos os $$$M$$$ de todas as bibliotecas não excede $$$10^5$$$.

Output

Imprima uma linha para cada biblioteca na ordem listada na entrada, dizendo quantos bibliotecários devem ser alocados para aquela biblioteca. A soma deve totalizar $$$K$$$ ou $$$0$$$ quando todas as bibliotecas estiverem organizadas.

Examples

Input
3 17
7
31 guia do mochileiro das galaxias
16 promessas vazias
46 guia de contabilidade com tabuletas cuneiforme
43 animais fantasticos e quando foram extintos
44 fazendo computadores usando bolinhas de gude
43 problemas que ninguem quer resolver parte 5
34 a sequencia que ninguem esperava 2
3
19 dicionario de s a z
19 dicionario de a a f
19 dicionario de g a l
4
31 computadores e outros problemas
33 discussoes sobre provas de np e p
24 prova que np e igual a p
28 prova que np nao e igual a p
Output
15
2
0
Input
5 9
2
36 jeitos de criar habitos improdutivos
32 5 provas matematicas gigantescas
3
32 ate mais e obrigado pelos peixes
32 o restaurante no fim do universo
29 a vida o universo e tudo mais
3
11 the minds i
19 i am a strange loop
17 godel escher bach
4
60 problemas tipograficos causados pelo uso de titulos muito gr
60 a longa lista dos livros que tem titulos extremamente longos
58 problemas nao resolvidos da computacao que estao em aberto
60 lista de titulos tautologicos que tem titulos com tautologia
10
40 the art of computer programming volume 1
40 the art of computer programming volume 2
41 the art of computer programming volume 4d
40 the art of computer programming volume 3
41 the art of computer programming volume 4a
41 the art of computer programming volume 4b
40 the art of computer programming volume 5
41 the art of computer programming volume 4c
40 the art of computer programming volume 6
40 the art of computer programming volume 7
Output
1
1
1
3
3