Direitos Humanos

Um evento internacional sobre direitos humanos promoverá uma mesa redonda. Várias autoridades de campos distintos já aceitaram os convites, restanto apenas $N$ cadeiras ainda em aberto. Dentre os possíveis candidatos há homens e mulheres, mas com o intuito de manter o equilíbrio da composição final, a escolha dos membros restantes tem uma única restrição: deve haver, no mínimo, dois representantes de cada sexo.

Dados os nomes dos candidatos e seus respectivos sexos, determine todas as possíveis escolhas para as vagas restantes na mesa.

Entrada

A primeira linha da entrada contém o número $M$ ($4 \leq M \leq 25$) de candidatos e o número $N$ ($4 \leq N \leq 6$) de vagas restantes na mesa redonda. Cada uma das $M$ linhas seguintes contém o nome de um candidato, seguido de seu sexo: (masculino) ou (feminino). Entre o nome e o sexo há um espaço em branco.

Pode-se assumir que não haverão nomes repetidos dentre os candidatos apresentados, e que o nome é composto, no máximo, de 100 caracteres alfabéticos, maiúsculos e minúsculos.

Saída

A saída deverá ser a listagem de todas as possíveis escolhas de candidatos. A primeira linha da saída deve ser o número de escolhas distintas possíveis para ocupar as $N$ vagas na mesa redonda.

As próximas $D$ linhas devem listar as escolhas distintas possíveis. Cada escolha deve ser representada pelos nomes dos $N$ candidatos, separados por vírgulas e sem espaços entre eles, em ordem alfabética, em uma única linha. As escolhas devem aparecer também em ordem alfabética.

Caso não exista nenhuma escolha possível que atenda o critério estabelecido, a saída será composta apenas pelo número 0 (zero).

Exemplo de entrada 1

4 4
Maria F
Jose M
Ana F
Pedro M

Exemplo de saída 1

1
Ana,Jose,Maria,Pedro

Exemplo de entrada 2

4 4
Maria F
Jose M
Ana F
Mara F

Exemplo de saída 2

0

Exemplo de entrada 3

7 4
Maria F
Jose M
Ana F
Pedro M
Paulo M
Beatriz F
Rosa F

Exemplo de saída 3

18
Ana,Beatriz,Jose,Paulo
Ana,Beatriz,Jose,Pedro
Ana,Beatriz,Paulo,Pedro
Ana,Jose,Maria,Paulo
Ana,Jose,Maria,Pedro
Ana,Jose,Paulo,Rosa
Ana,Jose,Pedro,Rosa
Ana,Maria,Paulo,Pedro
Ana,Paulo,Pedro,Rosa
Beatriz,Jose,Maria,Paulo
Beatriz,Jose,Maria,Pedro
Beatriz,Jose,Paulo,Rosa
Beatriz,Jose,Pedro,Rosa
Beatriz,Maria,Paulo,Pedro
Beatriz,Paulo,Pedro,Rosa
Jose,Maria,Paulo,Rosa
Jose,Maria,Pedro,Rosa
Maria,Paulo,Pedro,Rosa