Īstās iekavu izteiksmes

Uzdevums

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.

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ā.

Ievaddati

Teksta faila iekavas4.dat 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.

Izvaddati

Teksta faila iekavas4.rez 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".

Piemērs

iekavas4.dat	iekavas4.rez
2 1	(())
iekavas4.dat	iekavas4.rez
2 2	()()
iekavas4.dat	iekavas4.rez
2 20	NAV

Atsauces