Voltar

uCoder | 1109 | Nível: 8 | Tempo Limite: 10

Loteria

Adaptado por Erich Rodrigues

Competição: SBC - ACM/ICPC - Maratona de Programação de 2015


A loteria BWS é feita anualmente. Nela N pessoas apostam escolhendo K números cada uma. De modo formal, podemos dizer que Bij é o j-ésimo valor apostado pela i-ésima pessoa. Então os organizadores escolhem K inteiros positivos. Os números escolhidos são chamados de W1 , W2 , . . . , WK .
Os vencedores são calculados da seguinte maneira:
• Um subconjunto não vazio dos N participantes é escolhido aleatoriamente, ou seja, alguns participantes são escolhidos por pura sorte.
• Para cada pessoa neste subconjunto é calculado o valor S1 , que é a soma de todos os primeiros números apostados por elas, ou seja, a soma de Bi1 , onde i seria o índice de cada pessoa escolhida.Da mesma maneira os valores S2 , . . . , SK são calculados.
• É feito um teste de paridade entre Wj e Sj , ou seja, é testado se as paridades (se o número é par ou ímpar) casam entre W1 e S1 , W2 e S2 , e assim por diante até WK e SK .
• Se todas as paridades casam, então este conjunto de pessoas é considerado vencedor!
Os organizadores querem saber: é possível escolher os números W1 , W2 , . . . , WK de forma que não exista nenhum subconjunto de participantes vencedor?


Entrada

A primeira linha contém os números N (1 ≤ N ≤ 10^4 ) e K (3 ≤ K ≤ 50), representando o número de participantes e a quantidade de números apostados por cada pessoa respectivamente. As pessoas apostam em inteiros maiores do que 1 e menores do que 50, inclusive. Cada uma das N linhas seguintes contém K números, representando as apostas de cada pessoa, uma pessoa por linha.


Saída

Imprima ‘S’ caso seja possível ou ‘N’ caso contrário.


Exemplo de Entrada Exemplo de Saída

4 3
9 4 7
4 4 4
2 7 2
2 2 1

N

3 3
3 2 1
6 5 4
4 4 4

S

2 3
1 2 3
5 6 7

S