The lead developer of the tilda-omega-lambda calculus, Sir Charles, said in an interview that he had been interested in this problem for a long time.
When he was a child, Charles was very fond of communicating on social networks. He usually expressed his emotions (sadness and fun) with a sequence of opening and closing brackets, since there were no emojis and, especially, stickers then. But the cause to which he devoted his whole life in the future, Sir Charles loved even then, so it was guaranteed that at least one correct bracket sequence could be made from his messages per day.
At least that's what he said. However, recently anonymous hackers hacked into his old page on the same social network and posted a message history. Alas, there were no private photos and other interesting things there, but the scandal still broke out. Observant people have noticed that messages for some of the days do not add up to the PSP.
Charles soon released a video message in which he explained that for personal reasons he had to delete some messages, but he never deleted more than one message a day, and such messages did not exceed 5 characters in length.
You wondered if Sir Charles was lying this time, and you decided to write a program to check it.
Input:
The first line contains N (\(1 <= N <= 6\)) - number of Charles' posts on a suspicious day. The following N lines contain bracket sequences with a total length no greater than \(10^6\). Please note that there may still be a way to make a PSP out of them - you might just not notice it.
Output
Print "True" if Charles didn't lie, and there's a way to assemble the correct bracket sequence by adding another message. Output "Liar" if it is not.
Examples
| # |
Input |
Output |
| 1 |
2
((()())
))))))
|
True |