Problem Description

Let S = s1 s2...s2n be a well-formed string of parentheses. S can be encoded in two different ways:

  q By an integer sequence P = p1 p2...pn where pi is the number of left parentheses before the ith right parenthesis in S (P-sequence).

  q By an integer sequence W = w1 w2...wn where for each right parenthesis, say a in S, we associate an integer which is the number of right parentheses counting from the matched left parenthesis of a up to a. (W-sequence).

 

Following is an example of the above encodings:

 

S		(((()()()))) 	P-sequence	    4 5 6666 	W-sequence	    1 1 1456

Write a program to convert P-sequence of a well-formed string to the W-sequence of the same string.

 

 

Input

The first line of the input contains a single integer t (1 <= t <= 10), the number of test cases, followed by the input data for each test case. The first line of each test case is an integer n (1 <= n <= 20), and the second line is the P-sequence of a well-formed string. It contains n positive integers, separated with blanks, representing the P-sequence.

 

Output

The output file consists of exactly t lines corresponding to test cases. For each test case, the output line should contain n integers describing the W-sequence of the string corresponding to its given P-sequence.

 

Sample Input

2

6

4 5 6 6 6 6

9

4 6 6 6 6 8 9 9 9

 

Sample Output

1 1 1 4 5 6

1 1 2 4 5 1 1 3 9

 

题意：一行括号数列，分别给出第i个右括号前有多少个左括号；要求求出与第i个右括号相对应的左括号所形成的括号对中包括多少左括号（包括本身与第i个右括号对应的左括号）

输入：

第一行：输入一个数t，表示有t组数列需要处理；接下来的2*t行，没两行是一组需要处理的数据，上一行第n表示有n个右括号；接下来的一行有n个整数；

AC代码：

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5  6  7  8 using namespace std; 9 10 11 int main()12 {13     freopen("1.txt","r",stdin);14     int dp[50]={
    0};//模拟数组，初始值都为0；15     int n,num,i;16     int s,j;17     int sum;18     cin>>num;//输入样例的个数；19     while(num)20     {21 22         cin>>n;//输入右括号的个数；23         for(i=0;i
          
           >j;25             dp[j+i]=1;26         }27         s=n;28         n<<=1;29         i=0;30         while(s){31             while(dp[i++]<=0);32             sum=0;33             for(j=i-2;j>=0;j--)34             {35                 if(dp[j]<=0)sum++;//确定了一个左括号；36                 if(dp[j]==0){dp[j]=-1;break;}//到了与相应右括号对应的左括号处，跳出循环。37             }38             cout<
           
            <<" ";//输出左括号的个数。39 s--;40 }41 cout<