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.
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$$$.
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.
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
15 2 0
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
1 1 1 3 3