Esame
Problem
Lo sviluppatore principale del calcolo tilda-omega-lambda, Sir Charles, ha dichiarato in un'intervista di essersi interessato a questo problema per molto tempo.
Quando era bambino, Charles amava molto comunicare sui social network. Di solito esprimeva le sue emozioni (tristezza e divertimento) con una sequenza di parentesi di apertura e chiusura, dato che allora non c'erano emoji e, soprattutto, adesivi. Ma la causa a cui avrebbe dedicato tutta la sua vita in futuro, Sir Charles amava già allora, quindi era garantito che almeno una sequenza corretta di parentesi quadre potesse essere composta dai suoi messaggi al giorno.
Almeno questo è quello che ha detto. Tuttavia, recentemente hacker anonimi hanno violato la sua vecchia pagina sullo stesso social network e hanno pubblicato una cronologia dei messaggi. Purtroppo, non c'erano foto private e altre cose interessanti lì, ma lo scandalo è scoppiato comunque. Le persone attente hanno notato che i messaggi per alcuni giorni non si sommano alla PSP.
Charles ha presto rilasciato un videomessaggio in cui spiegava che per motivi personali doveva cancellare alcuni messaggi, ma non cancellava mai più di un messaggio al giorno, e tali messaggi non superavano i 5 caratteri di lunghezza.
Ti sei chiesto se questa volta Sir Charles stesse mentendo e hai deciso di scrivere un programma per verificarlo.
Inserimento:
La prima riga contiene N (\(1 <= N <= 6\)) - numero di Carlo ' post in un giorno sospetto. Le seguenti righe N contengono sequenze di parentesi con una lunghezza totale non maggiore di \(10^6\). Tieni presente che potrebbe esserci ancora un modo per farne una PSP: potresti semplicemente non accorgertene.
Uscita
Stampa "True" se Charles non ha mentito, e c'è un modo per assemblare la corretta sequenza di parentesi aggiungendo un altro messaggio. Emetti "Bugiardo" se non lo è.
Esempi
| # |
Input |
Uscita |
| 1 |
2
((()())
))))))
|
Vero |