SPOJ Brasil

Futebol é o esporte mais popular na América Latina, mas isso não significa que não seja apreciado pelo resto do mundo. Na Inglaterra, por exemplo, existem fãs que exageram na agressividade e causam muitos problemas, os chamados hooligans.

Na Linearlândia, um torneio de futebol está em andamento. Lá, o ranking é calculado da seguinte forma: para cada partida, o vencedor ganha dois pontos e o perdedor zero; em caso de empate, ambos os times ganham um ponto cada. O campeão é o time com o maior número de pontos. Cada par de times joga exatamente a mesma quantidade de partidas entre si, e essa quantidade é chamada enfrentamento.

Você tem seu time favorito e fica imaginando se é possível que seu time ainda seja campeão. Você sabe o número de times, o enfrentamento e o resultado dos jogos que já aconteceram. Escreva um programa que decida se é possível que seu time seja o único campeão ao final do torneio, com estritamente mais pontos que todos os outros times.

Entrada

A entrada contém vários casos de teste. A primeira linha de cada caso contém três inteiros N, M e G, separados por espaços simples, representando o número de times jogando o torneio (2 ≤ N ≤ 40), o enfrentamento (1 ≤ M ≤ 4) e o número de jogos já disputados (1 ≤ G). O seu time é identificado pelo número 0, enquanto os outros times são identificados por inteiros de 1 até N-1, inclusive.

Cada uma das próximas G linhas descreve um jogo já jogado. Cada linha contém um inteiro I, um caractere C e um inteiro J, separados por espaços simples. Os números I e J são os times que jogadam a partida (I ≠ J e 0 ≤ I,J ≤ N-1). O caractere C é '<' se o time I perdeu para o time J ou '=' se o jogo acabou empatado.

O último caso de teste é seguido de uma linha contendo três zeros separados por um espaço simples.

Saída

Para cada caso de teste, seu programa deve imprimir uma única linha contendo um único caractere: 'Y' se seu time ainda pode ser campeão, ou 'N' caso contrário.

Exemplo

Entrada:
4 2 6
0 < 3
3 = 2
2 < 0
1 < 0
2 = 0
3 < 0
4 1 5
2 = 0
0 < 1
1 = 3
2 < 1
0 < 3
4 2 5
2 = 0
0 < 1
1 = 3
2 < 1
0 < 3
2 1 1
1 < 0
4 1 1
0 < 1
4 1 2
0 < 1
0 < 2
0 0 0

Saída:
Y
N
Y
Y
Y
N