Giải bài trực tuyến

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ự ')'