A zárójelek pontos sorozatát a következőképpen definiáljuk:

• Az üres sorozat, a zárójelek pontos sorozata.
• Ha \(A\) a zárójelek pontos sorozata, akkor (\(A\)) is a zárójelek pontos sorozata.
• Ha \(A\) és \(B\) a zárójelek pontos sorozata, akkor \(AB\), amelyet konkatenálásukkal kapunk, ugyancsak a zárójelek pontos sorozata.

A zárójelek \(K\)-pontos sorozata a zárójelek olyan sorozata, amelyre érvényes, hogy a zárójelek pontos sorozatát kaphatjuk, ha \(K\) számú, vagy annál kevesebb zárójelet kitörlünk az eredeti sorozatból.

Adott \(Q\) számú kérdés, amelyek közül mindegyik alakja: megtalálni a T-edik, lexikográfiailag legkisebb \(K\)-pontos sorozatát a zárójeleknek, amelynek hossza \(N\). Feltételezzük, hogy ( lexikográfiailag kisebb, mint ).

Bemenet

A szabványos bemenet első sorában a \(Q\) szám áll. A következő \(Q\) sor mindegyikében pedig 3 egész szám található: \(N, K, T\).

Kimenet

A \(Q\) számú kérdés mindegyikére kiíratni a keresett \(N\) hosszúságú zárójel-sorozatot, vagy azt, hogy “Ne postoji”, ha a keresett zárójel-sorozat nem létezik.

1. példa

Bemenet

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

Kimenet

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

Korlátozások

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

A tesztpéldák 5 független csoportba oszthatók:

• Tesztpéldák, melyek 10 pontot érnek: \(N\leq 8\).
• Tesztpéldák, melyek 10 pontot érnek: \(K=N\).
• Tesztpéldák, melyek 10 pontot érnek: \(K=0\).
• Tesztpéldák, melyek 20 pontot érnek: \(N\leq100\).
• Tesztpéldák, melyek 50 pontot érnek: nincs külön korlátozás.