After Misha's birthday he had many large numbers left, scattered across the room. Now it's time to clean up and Misha needs to put them in a basket. He ordered this task to his pet robot that agreed to complete the task at certain conditions. Before the robot puts a number x to the basket, Misha should answer the question: is it possible to choose one or multiple numbers that already are in the basket, such that their XOR sum equals x? 

If the answer is positive, you also need to give the indexes of these numbers. If there are multiple options of choosing numbers, you are allowed to choose any correct option. After Misha's answer the robot puts the number to the basket.

Initially the basket is empty. Each integer you put in the basket takes some number. The first integer you put into the basket take number 0, the second integer takes number 1 and so on.

Misha needs to clean up the place as soon as possible but unfortunately, he isn't that good at mathematics. He asks you to help him.

Input

The first line contains number m (1 ≤ m ≤ 2000), showing how many numbers are scattered around the room.

The next m lines contain the numbers in the order in which the robot puts them in the basket. Each number is a positive integer strictly less than 10600 that doesn't contain leading zeroes. 

Output

For each number either print a 0 on the corresponding line, if the number cannot be represented as a XOR sum of numbers that are in the basket, or print integer k showing how many numbers are in the representation and the indexes of these numbers. Separate the numbers by spaces. Each number can occur in the representation at most once.

Examples

Input

7
7
6
5
4
3
2
1


Output

0
0
0
3 0 1 2
2 1 2
2 0 2
2 0 1


Input

2
5
5


Output

0
1 0

Note

The XOR sum of numbers is the result of bitwise sum of numbers modulo 2.
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Random;
import java.util.Scanner;

public class F {

    boolean DEBUG = false;
    void run(){
//      BigInteger B = new BigInteger("999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999");
//      Long T = System.currentTimeMillis();
//      for(int i=0;i<2000;i++)for(int j=0;j<2000;j++){
////            B.testBit(i);
//          for(int k=0;k<5;k++){
//          int x = j%64;
//          }
//      }
//      System.out.println((System.currentTimeMillis()-T)+" ms");
        
        Scanner sc = new Scanner();
        int MAXBIT = 2000;
        int m;
        if (!DEBUG){
        m = sc.nextInt();
        }else {
        m = 100;
        }
        long[] test = new long[m];
        long[][] mat = new long[MAXBIT][(m>>6)+1];
        Random rand = new Random();
        for(int j=0;j<m;j++){
            BigInteger bi;
            if(!DEBUG){
//              bi = sc.nextBigInteger();
                bi = new BigInteger(sc.next());
            } else {
                bi = new BigInteger(rand.nextInt(9999)+1000+"");
            }
//          test[j] = bi.longValue();
            for(int i=0;i<bi.bitLength();i++){
                mat[i][j>>6] |= bi.testBit(i) ? (1L << (j%64)) : 0;
            }
        }
//      printMatrix(mat);
        int[] index = new int[MAXBIT];
        binaryGaussJordan(mat, MAXBIT, m, index);
//      printMatrix(mat);
//      debug(index);
//      debug(isIdentify);
//      for(int j=0;j<m;j++){
//          if(isIdentify[j])System.out.println(0);
//          else {
//              List<Integer> res = new ArrayList<Integer>();
//              for(int i=0;i<MAXBIT;i++)if((mat[i][j>>6]&(1L << (j%64)))!=0)res.add(index[i]);
//              System.out.print(res.size());
//              int xor = 0;
//              for(int r:res){
//                  xor^=test[r];
//                  System.out.print(" "+r);
//              }
//              System.out.println();
////                if(xor!=test[j])System.out.println(" XOR CHECK: "+xor+" OK? " + (xor == test[j])+" "+xor+" "+test[j]+" at "+j+" "+isIdentify[j]);
////                else System.out.println();
//          }
//      }
        if(DEBUG){
        System.out.println("Random input");
        System.out.println(m);
        for(int x=0;x<m;x++)System.out.println(test[x]);
        }
    }
    
    void binaryGaussJordan(long[][] a, int n, int m, int[] index){
//      boolean[] isIdentify = new boolean[m];
        Arrays.fill(index, -1); // index[i] has number of Vector (in 0 - m-1)
        int rank = 0;
//      long[][] a = new long[n][(m>>6)+1]; // packing 64 bits in one 64-bit integer
//      for(int i=0;i<n;i++)for(int j=0;j<m;j++)if(_a[i][j]==1)a[i][j>>6]|=(1L<<(j%64));
//      printMatrix(a);
        int[] res = new int[m];
        for(int j=0;j<m;j++){
            int J = j%64;
            boolean is = true;
            if(rank == n){
                // here, already matrix A becomes echelon forms
//              isIdentify[j] = false;
                is = false;
            } else if ((a[rank][j>>6]&(1L << (J)))==0){
                int i = rank+1;
                while(i < n && (a[i][j>>6]&(1L << (J)))==0)i++;
                if(i == n) {
                    // Vector j can represents some XOR among (Vector 0 -- (j-1))
//                  System.out.println("CAN: "+j);
//                  isIdentify[j] = false;
                    is = false;
//                  continue;
                } else {
                    // need row swap
                    // we can start k=j truely;
                    for(int k=(j>>6);k<a[0].length;k++){
                        long t = a[i][k];
                        a[i][k] = a[rank][k];
                        a[rank][k] = t;
                    }
                }
            }
            if (!is) {
//              debug(index);
                int c = 0;
                StringBuilder sb = new StringBuilder();
                for(int i=0;i<n;i++)if((a[i][j>>6]&(1L << (J)))!=0){
                    c++;
                    sb.append(" "+index[i]);
                }
                sb.append("\n");
                System.out.print(c);
                System.out.print(sb);
//              for(int i=0;i<c;i++){
//                  System.out.print(" "+res[i]);
//              }
//              System.out.println();
//              if(xor!=test[j])System.out.println(" XOR CHECK: "+xor+" OK? " + (xor == test[j])+" "+xor+" "+test[j]+" at "+j+" "+isIdentify[j]);
//              else System.out.println();
                continue;
            }
            // 1L << 63 will negative number. So never write like (a[i][j] & (1L << 63) > 0). !=0 is right.
            for(int i=0;i<n;i++)if(i!=rank && (a[i][j>>6]&(1L << (J)))!=0){
                for(int k=(j>>6);k<a[0].length;k++)a[i][k]^=a[rank][k];
            }
//          isIdentify[j] = true; // Vector J is Identified.
            index[rank++] = j; // Identity Vector that has 1 only at rank
            System.out.println(0);
//          System.out.println("IDENTIFY: "+j);
        }
//      for(int i=0;i<n;i++)for(int j=0;j<m;j++)_a[i][j]=((a[i][j>>6]&(1L << (j%64)))!=0)?1:0;
//      _a = a;
//      printMatrix(_a);
//      _a = a;
//      return isIdentify;
    }
    
    void debug(Object...o){
        System.out.println(Arrays.deepToString(o));
    }
    
    void printMatrix(long[][] a){
        int n = a.length, m = a[0].length;
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++)System.out.printf("%2d", a[i][j]);
            System.out.println();
        }
        System.out.println();
    }
    
    public static void main(String[] args) {
        new F().run();
    }
    class Scanner {
        int nextInt() {
            try {
                int c = System.in.read();
                while (c != '-' && (c < '0' || '9' < c))
                    c = System.in.read();
                if (c == '-') return -nextInt();
                int res = 0;
                do {
                    res *= 10;
                    res += c - '0';
                    c = System.in.read();
                } while ('0' <= c && c <= '9');
                return res;
            } catch (Exception e) {
                return -1;
            }
        }
        String next() {
            try {
                StringBuilder res = new StringBuilder("");
                int c = System.in.read();
                while (Character.isWhitespace(c))
                    c = System.in.read();
                do {
                    res.append((char) c);
                } while (!Character.isWhitespace(c = System.in.read()));
                return res.toString();
            } catch (Exception e) {
                return null;
            }
        }
    }
    /*
7
7 6 5 4 3 2 1

5
15 11 4 1 13

20
983
793
801
27
93
102
192
919
402
2
390
389
821
902
333
888
222
555
42
50

64
100
9233
9046
10126
4941
5145
2345
6761
10539
10433
4417
3054
1346
4469
7925
6305
9153
7498
2952
2474
6004
4604
6400
5683
8650
4350
5591
6958
1265
3633
7564
1330
2625
2654
4194
2681
1753
2058
5641
10858
8685
2377
4316
1358
10399
10783
9133
2056
4955
8331
3411
6844
8458
4343
3481
6834
8484
9569
4186
8790
1990
1172
4367
8591
3232

     */
}
