A. Kuroni and the Gifts

Kuroni has nn daughters. As gifts for them, he bought nn necklaces and nn bracelets:

• the ii-th necklace has a brightness aiai, where all the aiai are pairwise distinct (i.e. all aiai are different),
• the ii-th bracelet has a brightness bibi, where all the bibi are pairwise distinct (i.e. all bibi are different).

Kuroni wants to give exactly one necklace and exactly one bracelet to each of his daughters. To make sure that all of them look unique, the total brightnesses of the gifts given to each daughter should be pairwise distinct. Formally, if the ii-th daughter receives a necklace with brightness xixi and a bracelet with brightness yiyi, then the sums xi+yixi+yi should be pairwise distinct. Help Kuroni to distribute the gifts.

For example, if the brightnesses are a=[1,7,5]a=[1,7,5] and b=[6,1,2]b=[6,1,2], then we may distribute the gifts as follows:

• Give the third necklace and the first bracelet to the first daughter, for a total brightness of a3+b1=11a3+b1=11.
• Give the first necklace and the third bracelet to the second daughter, for a total brightness of a1+b3=3a1+b3=3.
• Give the second necklace and the second bracelet to the third daughter, for a total brightness of a2+b2=8a2+b2=8.

Here is an example of an invalid distribution:

• Give the first necklace and the first bracelet to the first daughter, for a total brightness of a1+b1=7a1+b1=7.
• Give the second necklace and the second bracelet to the second daughter, for a total brightness of a2+b2=8a2+b2=8.
• Give the third necklace and the third bracelet to the third daughter, for a total brightness of a3+b3=7a3+b3=7.

This distribution is invalid, as the total brightnesses of the gifts received by the first and the third daughter are the same. Don't make them this upset!

Input

The input consists of multiple test cases. The first line contains an integer tt (1≤t≤1001≤t≤100)  — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer nn (1≤n≤1001≤n≤100)  — the number of daughters, necklaces and bracelets.

The second line of each test case contains nn distinct integers a1,a2,…,ana1,a2,…,an (1≤ai≤10001≤ai≤1000)  — the brightnesses of the necklaces.

The third line of each test case contains nn distinct integers b1,b2,…,bnb1,b2,…,bn (1≤bi≤10001≤bi≤1000)  — the brightnesses of the bracelets.

Output

For each test case, print a line containing nn integers x1,x2,…,xnx1,x2,…,xn, representing that the ii-th daughter receives a necklace with brightness xixi. In the next line print nn integers y1,y2,…,yny1,y2,…,yn, representing that the ii-th daughter receives a bracelet with brightness yiyi.

The sums x1+y1,x2+y2,…,xn+ynx1+y1,x2+y2,…,xn+yn should all be distinct. The numbers x1,…,xnx1,…,xn should be equal to the numbers a1,…,ana1,…,an in some order, and the numbers y1,…,yny1,…,yn should be equal to the numbers b1,…,bnb1,…,bn in some order.

It can be shown that an answer always exists. If there are multiple possible answers, you may print any of them.

Example

input

Copy

2
3
1 8 5
8 4 5
3
1 7 5
6 1 2

output

Copy

1 8 5
8 4 5
5 1 7
6 2 1

Note

In the first test case, it is enough to give the ii-th necklace and the ii-th bracelet to the ii-th daughter. The corresponding sums are 1+8=91+8=9, 8+4=128+4=12, and 5+5=105+5=10.

The second test case is described in the statement.

给n个女儿分两种物品，，要求每个女儿分的两种物品的和不能一样，。，其实就是排一遍序然后输出，，以后这种题在想暴力我就吃shi。。。

#include <bits/stdc++.h>
using namespace std;
int a[111],b[111];
int main()
{
    ios::sync_with_stdio(false);
    int t,n;
    cin>>t;
    while(t--)
    {
        cin>>n;
        for(int i=1;i<=n;i++)
            cin>>a[i];
        for(int i=1;i<=n;i++)
            cin>>b[i];
        sort(a+1,a+n+1);
        sort(b+1,b+n+1);
        for(int i=1;i<=n;i++)
            cout<<a[i]<<" ";
        cout<<endl;
        for(int i=1;i<=n;i++)
            cout<<b[i]<<" ";
        cout<<endl;
    }
    return 0;
}

B. Kuroni and Simple Strings

Now that Kuroni has reached 10 years old, he is a big boy and doesn't like arrays of integers as presents anymore. This year he wants a Bracket sequence as a Birthday present. More specifically, he wants a bracket sequence so complex that no matter how hard he tries, he will not be able to remove a simple subsequence!

We say that a string formed by nn characters '(' or ')' is simple if its length nn is even and positive, its first n2n2 characters are '(', and its last n2n2 characters are ')'. For example, the strings () and (()) are simple, while the strings )( and ()() are not simple.

Kuroni will be given a string formed by characters '(' and ')' (the given string is not necessarily simple). An operation consists of choosing a subsequence of the characters of the string that forms a simple string and removing all the characters of this subsequence from the string. Note that this subsequence doesn't have to be continuous. For example, he can apply the operation to the string ')()(()))', to choose a subsequence of bold characters, as it forms a simple string '(())', delete these bold characters from the string and to get '))()'.

Kuroni has to perform the minimum possible number of operations on the string, in such a way that no more operations can be performed on the remaining string. The resulting string does not have to be empty.

Since the given string is too large, Kuroni is unable to figure out how to minimize the number of operations. Can you help him do it instead?

A sequence of characters aa is a subsequence of a string bb if aa can be obtained from bb by deletion of several (possibly, zero or all) characters.

Input

The only line of input contains a string ss (1≤|s|≤10001≤|s|≤1000) formed by characters '(' and ')', where |s||s| is the length of ss.

Output

In the first line, print an integer kk  — the minimum number of operations you have to apply. Then, print 2k2k lines describing the operations in the following format:

For each operation, print a line containing an integer mm  — the number of characters in the subsequence you will remove.

Then, print a line containing mm integers 1≤a1<a2<⋯<am1≤a1<a2<⋯<am  — the indices of the characters you will remove. All integers must be less than or equal to the length of the current string, and the corresponding subsequence must form a simple string.

If there are multiple valid sequences of operations with the smallest kk, you may print any of them.

Examples

input

Copy

(()((

output

Copy

1
2
1 3 

input

Copy

)(

output

Copy

0

input

Copy

(()())

output

Copy

1
4
1 2 5 6 

Note

In the first sample, the string is '(()(('. The operation described corresponds to deleting the bolded subsequence. The resulting string is '(((', and no more operations can be performed on it. Another valid answer is choosing indices 22 and 33, which results in the same final string.

In the second sample, it is already impossible to perform any operations.

简单模拟，如果一个字符串可以取最优解肯定是1次，两边跑。。。

#include <bits/stdc++.h>
using namespace std;
int main()
{
     ios::sync_with_stdio(false);
     string s;
     cin>>s;
     int l=0,r=s.size()-1;
     set<int>ss;
     while(l<r)
     {
         while(l<s.size()&&s[l]==')')
            l++;
         while(r>=0&&s[r]=='(')
                r--;
         if(r>=0&&l<s.size()&&l<r)
         {
             ss.insert(l+1);
             ss.insert(r+1);
             l++;
             r--;
         }
     }
         if(ss.size()==0)
            puts("0");
         else
         {
             cout<<1<<endl;
             cout<<ss.size()<<endl;
             for(set<int>::iterator it=ss.begin();it!=ss.end();it++)
                cout<<*it<<" ";
             cout<<endl;
         }
     return 0;
}