Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

MWP5_1A - Nawiasy

Nawiasem mówiąc mały Jaś jest całkiem niezłym matematykiem. Opanował już sztukę dodawania, odejmowania, mnożenia oraz dzielenia, teraz jednak stanął przed wyzwaniem jakiego nie miał jeszcze w swojej krótkiej karierze - poprawnym stosowaniem nawiasów! Napisał mnóstwo skomplikowanych równań, w których użył większej lub mniejszej ich liczby, w żaden sposób jednak nie jest w stanie zweryfikować poprawności zastosowania nowego dla niego elementu.

Jako, że edukację młodzieży należy wspierać pomóż naszemu bohaterowi i napisz program, który zweryfikuje poprawność zastosowania nawiasów. Ponieważ Jaś jest pewien swych umiejętności co do wszystkich elementów poza nawiasami usunął je ze swych równań, tak żeby maksymalnie uprościć Twoje zadanie.

Wejście

W pierwszej linii wejścia znajduje się liczba n (1 ≤ n ≤ 500000) określająca liczbę zestawów danych. Każdą z kolejnych n linii tworzą poszczególne zestawy składające się z liczby m (1 ≤ m ≤ 106) oraz ciągu m nawiasów - "(" lub ")". Można założyć, że suma wszystkich liczb m ≤ 8000000.

Wyjście

Na wyjściu wypisz słowo "TAK" jeżeli układ nawiasów jest poprawny albo słowo "NIE" jeżeli jest inaczej.

Przykład

Wejście:

2
4 ()()
4 ((()

Wyjście:

TAK
NIE

Dodane przez:Maciej Boniecki
Data dodania:2013-03-01
Limit czasu wykonania programu:0.5s-2s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: ASM64 SCM qobi
Pochodzenie:V Mistrzostwa WWSI w Programowaniu

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.