TopCoder

User's AC Ratio

NaN% (0/0)

Submission's AC Ratio

NaN% (0/0)

Tags

Description


In an archeology excavation in the Panda Land, the panda researchers found artifacts from the technologically advanced Bracket Panda civilization which lives around year 2008 BGP - Before Giant Panda. The artifacts are in the form of a big stone tablet with inscriptions on it (seems to be some kind of codes) and some locked treasure chests labeled as `bonus" by the ancient pandas, each chest have numbers inscribed on them as well as several switches labeled with(' and `)'.



After much research and decoding, the researchers found the following results:



  • Codes in the tablet describe a master sequence as the source of all possible switch positions (a.k.a. combination codes for opening the chest). In other words, all valid codes are defined as subsets of particular terms in the sequence. The terms of the master sequence are defined as being the concatenation of all previous terms of the sequence enclosed in the outer parenthesis `(' and `)', as follows: S1 = (), S2 = (()), S3 = (()(())), S4 = (()(())(()(()))), and so on.
  • There are three numbers in each treasure chest. The first number N , describes the term number in master sequence containing the code, the second number K , is a zero based index describing the position of starting character of the code in the N -th sequence term, and the last one M , describes the length of the sequence (number of the switches in the chest).


For larger values of N
, the master sequence's term can become extremely long as the term's length is in the order of 2N
(as you may have figured out previously). Therefore as an elite programmer in Panda Land, you are given a task to write a program for decoding the combination codes - all that the program needs to do is printing the correct combination code required to open the treasure box, given the three numbers (N, K, M)

inscribed on the treasure chest.

Input Format


The input consists of several cases. Each case contains three integer: N
<!-- MATH
$(1 \le N \le 31)$
-->
(1 WIDTH="18" HEIGHT="31" ALIGN="MIDDLE" BORDER="0"
SRC="/ntujudge/problemdata/629.png"
ALT="$ \le$">N WIDTH="18" HEIGHT="31" ALIGN="MIDDLE" BORDER="0"
SRC="/ntujudge/problemdata/629.png"
ALT="$ \le$">31)

, K
<!-- MATH
$(0 \le K < 2{N})$
-->
(0 WIDTH="18" HEIGHT="31" ALIGN="MIDDLE" BORDER="0"
SRC="/ntujudge/problemdata/629.png"
ALT="$ \le$">K < 2N)

and M

<!-- MATH
$(1 \le M \le \min{10000, 2{N} - K})$
-->
(1 WIDTH="18" HEIGHT="31" ALIGN="MIDDLE" BORDER="0"
SRC="/ntujudge/problemdata/629.png"
ALT="$ \le$">M WIDTH="18" HEIGHT="31" ALIGN="MIDDLE" BORDER="0"
SRC="/ntujudge/problemdata/629.png"
ALT="$ \le$">min{10000, 2N - K})

. The input is terminated by a line where <!-- MATH
$N = K = M = 0$
-->
N = K = M = 0

.

Output Format


For each case, output the correct combination of code required to open it (which is the substring from the N
-th master sequence term, with length M
starting from the K + 1

-th character of the term.)

Sample Input 1



3 0 6
3 4 4
3 5 2
3 6 1
3 7 1
0 0 0



Sample Output 1



(()(()
()))
))
)
)

Hints

Problem Source

Migrated from old NTUJ.

ACM ICPC regional Jakarta site 2008

Subtasks

No. Testdata Range Score

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 10000 65536 2000