Longest non regular parentheses subsequence

All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian as well.
Chef has recently learnt about sequences of parentheses. These are special sequences that contain only the characters '(' and ')'.
A regular parentheses sequence follows the following definition:
 An empty sequence is regular
 If S is a regular sequence, then (S) is also regular
 If A and B represent two regular sequences, then their concatenation AB is also regular.
Therefore, the sequences (), ()() and (())() are regular, while ()(, ) and ))() are nonregular.
Now, you need to find the longest subsequence of the given sequence which is nonregular. Amongst all such distinct answers, output the lexicographically K^{th} amongst them. If the number of distinct subsequences with maximum length is less than K, please output 1 instead.
Input:
The first line contains a single integer T, denoting the number of test cases to follow.
Each of the test cases have exactly two lines, the first contains the parentheses sequence and the second contains the value of K.
Output:
Output exactly T lines, each containing answer to the corresponding query.
Constraints:
 1 ≤ T ≤ 10
 1 ≤ S ≤ 10^{5}
 1 ≤ K ≤ 10^{9}
Example:
Sample Input:
5 () 2 (() 1 (() 2 (()) 2 (()) 3
Sample Output:
) (() 1 ()) 1
Explanation:
Case 1: Following are the subsequences:
Length Subsequence Regular/NonRegular 1 ( Nonregular 1 ) Nonregular 2 () Regular
There are two nonregular subsequences of equal length:'(' and ')'.
We are asked for the lexicographically 2nd, so output should be ')'.
Case 2: Following are the subsequences:
Length Subsequence Regular/NonRegular 1 ( NonRegular 1 ) NonRegular 2 (( NonRegular 2 () Regular 3 (() NonRegular
In this case, there are nonregular subsequences of lengths 1, 2, and 3. But, as 3 is the maximum among these, we choose, (().
Case 3:
The string is same as Case 2, and we realize that there is only one subsequence of the maximum length 3, thus we must output 1.
Case 4:
We can find that following subsequences have maximum length and are nonregular.
Length Subsequence 3 ()) 3 (()
In lexicographical order, we have following subsequences: [ ((), ()) ]
The query asks for 2nd subsequence, thus the required output is ()).
Case 5:
This is the same sequence as last case, and we know that there are exactly 2 distinct subsequences of maximum length. Thus, answer should be 1.
Notes:
 A subsequence of a given sequence A is a nonempty sequence obtained by removing zero or more characters from A. It does not need to be contiguous.
 A sequence A is called different from another sequence B, if there exists an integer k, such that 1 ≤ k ≤ N (N is the length of both sequences), and A_{k} != B_{k}.
 Consider two different Nlength sequences, A and B. Let k be the smallest integer such that A[k] != B[k] and 1 ≤ k ≤ N. If A[k] < B[k], then A is said to be lexicographically smaller than B, and viceversa.
Author:  code_master01 
Tester:  rubanenko 
Editorial  http://discuss.codechef.com/problems/ANKPAREN 
Tags  basicprog, code_master01, cook59, easymedium, pattern, stack 
Date Added:  9062015 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 6.3, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYPY, PYTH, PYTH 3.5, RUBY, SCALA, SCM chicken, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 