Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

VNBRACK - Dãy ngoặc bậc P

Xét định nghĩa 1 dãy ngoặc đúng:
- Nếu A không có ký tự nào thì A là dãy ngoặc đúng
- Nếu A là dãy ngoặc đúng thì (A) là dãy ngoặc đúng
- Nếu A và B là 2 dãy ngoặc đúng thì AB là dãy ngoặc đúng

Ta gọi bậc của dãy ngoặc đúng S là hàm deg(S). Gọi R là dãy ngoặc thu được bằng cách xóa đi N div 2 ký tự đầu và N div 2 ký tự cuối của S, trong đó 2*N là độ dài của S. Ta có công thức đệ quy tính deg(S) như sau:
- Nếu R không phải dãy ngoặc đúng thì deg(S) = 1
- Nếu R là dãy ngoặc đúng thì deg(S) = deg(R)+1

Ví dụ dãy (()()) có bậc là 2, dãy ()(()) có bậc là 1, dãy (()) có bậc lớn vô cùng ( áp dụng vô hạn lần công thức đệ quy trên ).
Yêu cầu: Xét cách dãy ngoặc có độ dài 2*N và bậc P, hãy in ra dãy ngoặc có thứ tự từ điển thứ K.

Input

Gồm một dòng duy nhất ghi ra 3 số N, P, K.

Output

Gồm một dòng duy nhất ghi ra dãy ngoặc tìm được.

Example

Input:
3 1 2

Output:
()(())

Giải thích: có 3 dãy ngoặc độ dài 6 và bậc 1 là: (())(), ()(()), ()()().
Giới hạn:
- 1 <= N <= 40, 1 <= P <= 6, K nguyên dương không vượt quá 10^18 và không vượt quá số lượng dãy ngoặc độ dài 2*N bậc P.
- Ký tự '(' có thứ tự từ điển nhỏ hơn ký tự ')'


Được gửi lên bởi:VOJ problem setters
Ngày:2008-03-31
Thời gian chạy:0.218s-0.436s
Giới hạn mã nguồn:10000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET
Nguồn bài:Thi vòng 2 - 2008

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.