13606번 - Loteria 다국어

A loteria BWS é feita anualmente. Nela N pessoas apostam escolhendo K números cada uma. De modo formal, podemos dizer que B_ij é 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 W₁, W₂, ..., W_K.

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 S₁, que é a soma de todos os primeiros números apostados por elas, ou seja, a soma de B_i1, onde i seria o índice de cada pessoa escolhida. Da mesma maneira os valores S₂, ..., S_K são calculados.
• E feito um teste de paridade entre W_j e S_j , ou seja, é testado se as paridades (se o número é par ou ímpar) casam entre W₁ e S₁, W₂ e S₂, e assim por diante até W_K e S_K.
• Se todas as paridades casam, então este conjunto de pessoas é considerado vencedor!

Os organizadores querem saber: é possível escolher os números W₁, W₂, ..., W_K de forma que não exista nenhum subconjunto de participantes vencedor?

A primeira linha contém os números N (1 ≤ N ≤ 10⁴) 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.

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