Korektu iekavu izteiksmi definē šādi:

• () ir korekta iekavu izteiksme;
• ja A ir korekta iekavu izteiksme, tad (A) arī ir korekta iekavu izteiksme;
• ja A un B ir korektas iekavu izteiksmes, tad AB arī ir korekta iekavu izteiksme.

Tā, piemēram, (()()) un ()()((())) ir korektas iekavu izteiksmes, bet )( un ()) -nav.

Aplūkosim visas korektās iekavu izteiksmes garumā 2N. Sakārtosim tās leksikogrāfiski augošā secībā, uzskatot, ka atverošā iekava mazāka par aizverošo, un sanumurēsim, sākot ar 1. Uzdevums – uzrakstīt programmu, kas atrod K-to izteiksmi šajā sakārtojumā.

Ievaddatu pirmajā rindā dots skaitlis N (1 ≤ N ≤ 100), bet otrajā – K (1 ≤ K ≤ 10¹⁰⁰⁰+255), meklējamās izteiksmes kārtas numurs. Skaitļa K pieraksta sākumā var būt liekas nulles un tā pieraksta kopējais garums var pārsniegt 1001 simbolu.

Izvaddatu vienīgajā rindā izvadiet K-to korekto iekavu izteiksmi garumā 2N. Izteiksme nedrīkst saturēt nekādus tukšumsimbolus.

Ja korekto iekavu izteiksmju skaits ir mazāks par K, izvadiet vārdu "NAV".

No Krievijas informātikas olimpiāžu treniņsacensībām 2001. g.