Module: Korrekte Klammern-Sequenz (PSP)


Problem

5 /6


Prüfung

Problem

Der führende Entwickler von Tilda-Omega-Lambda-Kalkül, Sir Charles, sagte in einem Interview, dass er vor langer Zeit Interesse an diesem Problem hatte. 
Als er ein Kind war, hat Charles es sehr genossen, in sozialen Medien zu kommunizieren. Seine Emotionen (Traurigkeit und Spaß) drückte er normalerweise in einer Sequenz aus öffnenden und schließenden Klammern aus, da es damals keine Emojis und vor allem keine Sticker gab. Aber die Sache, der er in Zukunft sein ganzes Leben gewidmet hatte, liebte Sir Charles schon damals, so dass aus seinen Botschaften pro Tag garantiert mindestens eine richtige Klammern-Sequenz gebildet werden konnte. 
Zumindest hat er das gesagt. Vor kurzem haben anonyme Hacker jedoch seine alte Seite in demselben sozialen Netzwerk gehackt und eine Nachrichtenverlaufsgeschichte geschrieben. Leider gab es dort keine privaten Fotos und andere interessante Dinge, aber der Skandal brach immer noch aus. Aufmerksame Leute haben bemerkt, dass sich die Nachrichten an einigen Tagen nicht zu einem PSP addieren. 
Charles veröffentlichte bald eine Videobotschaft, in der er erklärte, dass er einige Nachrichten aus persönlichen Gründen löschen musste, aber er löschte nie mehr als eine Nachricht pro Tag und die Länge solcher Nachrichten betrug nicht mehr als 5 Zeichen. 
Sie haben sich gefragt, ob Sir Charles dieses Mal lügt, und Sie haben beschlossen, ein Programm zu schreiben, um es zu überprüfen. 

 
Eingabe:
Die erste Zeile enthält N (\(1 <= N <= 6\)) - Die Anzahl der Charles-Nachrichten an einem verdächtigen Tag. Die folgenden N Zeichenfolgen enthalten Klammern mit einer Gesamtlänge von \(10^6\). Beachten Sie, dass es immer noch eine Möglichkeit geben kann, aus ihnen eine PSP zu erstellen - Sie haben sie vielleicht einfach nicht bemerkt.

Ausgabe
Geben Sie "True" aus, es sei denn, Charles hat gelogen und es gibt eine Möglichkeit, die korrekte Klammern-Sequenz zu sammeln, indem Sie eine weitere Nachricht hinzufügen. Geben Sie "Liar" aus, wenn dies nicht der Fall ist.


Beispiele
Eingabe Ausgabe
1
2
((()())
))))))
True