Exame
Problem
O principal desenvolvedor do cálculo tilda-ômega-lambda, Sir Charles, disse em uma entrevista que estava interessado neste problema há muito tempo.
Quando criança, Charles gostava muito de se comunicar nas redes sociais. Costumava expressar suas emoções (tristeza e diversão) com uma sequência de colchetes de abertura e fechamento, já que não havia emojis e, principalmente, stickers naquela época. Mas a causa à qual ele dedicou toda a sua vida no futuro, Sir Charles amava mesmo então, então era garantido que pelo menos uma sequência correta de colchetes poderia ser feita a partir de suas mensagens por dia.
Pelo menos foi o que ele disse. No entanto, recentemente hackers anônimos invadiram sua antiga página na mesma rede social e postaram um histórico de mensagens. Infelizmente, não havia fotos privadas e outras coisas interessantes lá, mas o escândalo ainda estourou. Pessoas observadoras notaram que as mensagens de alguns dias não batem no PSP.
Charles logo divulgou uma mensagem em vídeo na qual explicava que, por motivos pessoais, teve que deletar algumas mensagens, mas nunca deletou mais de uma mensagem por dia, e essas mensagens não ultrapassavam 5 caracteres.
Você se perguntou se Sir Charles estava mentindo desta vez e decidiu escrever um programa para verificar isso.
Entrada:
A primeira linha contém N (\(1 <= N <= 6\)) - número de Charles ' posts em um dia suspeito. As linhas N a seguir contêm sequências de colchetes com comprimento total não superior a \(10^6\). Observe que ainda pode haver uma maneira de transformá-los em um PSP - você pode simplesmente não perceber.
Saída
Imprima "True" se Charles não mentiu, e há uma maneira de montar a sequência correta de colchetes adicionando outra mensagem. Imprima "Liar" se não for.
Exemplos
| # |
Entrada |
Saída |
| 1 |
2
((()())
)))))))
|
Verdadeiro |