Тачну секвенцу заграда дефинишемо на следећи начин: - Празна секвенца је тачна секвенца заграда. - Ако је \(A\) тачна секвенца заграда, онда је и (\(A\)) тачна секвенца заграда. - Ако су \(A\) и \(B\) тачне секвенце зграда, онда је и њихова конкатенација, \(AB\), тачна секвенца заграда.

\(K\)-тачна секвенца заграда је секвенца заграда таква да се може добити тачна секвенца заграда након што се обрише \(K\) или мање заграда из оригиналне секвенце. Дато је \(Q\) упита од којих сваки има следећи облик: Наћи \(T\)-ту по реду лексикографски најмању \(K\)-тачну секвенцу заграда дужине \(N\), ако се узима да је ( лексикографски мање од ).

Опис улаза

У првој линији стандардног улаза налази се број \(Q\). У наредних \(Q\) линија, налазе се по 3 цела броја \(N, K, T\).

Опис излаза

За сваки од \(Q\) упита исписати тражену секвенцу заграда или “Ne postoji” ако тражена секвенца заграда не постоји.

Пример 1

Улаз

6
1 1 1
1 1 2
1 1 3
3 1 1
4 4 9
8 0 2

Излаз

(
)
Ne postoji
(()
)(((
((()()))

Ограничења

• \(1\leq Q,N\leq1000\)
• \(0\leq K\leq100\)
• \(1\leq T<2^{60}\)

Тест примери су подељени у 5 дисјунктних група: - У тест примерима вредним 10 поена: \(N\leq 8\). - У тест примерима вредним 10 поена: \(K=N\). - У тест примерима вредним 10 поена: \(K=0\). - У тест примерима вредним 20 поена: \(N\leq100\). - У тест примерима вредним 50 поена: Без додатних ограничења.