Problem: Little Petya likes numbers a lot. Recently his mother has presented him a collection of n non-negative integers. There's only one thing Petya likes more than numbers: playing with little Masha. He immediately decided to give a part of his new collection to her. To make the game even more interesting, Petya decided to give Masha such collection of numbers for which the following conditions fulfill:

  * Let's introduce x1 to denote the xor of all numbers Petya has got left; and let's introduce x2 to denote the xor of all numbers he gave to Masha. Value (x1 + x2) must be as large as possible. 
  * If there are multiple ways to divide the collection so that the previous condition fulfilled, then Petya minimizes the value x1. 



The xor operation is a bitwise excluding "OR", that is denoted as "xor" in the Pascal language and "^" in C/C++/Java.

Help Petya divide the collection as described above. If there are multiple suitable ways to divide it, find any of them. Please note that after Petya gives a part of his numbers to Masha, he may have no numbers left. The reverse situation is also possible, when Petya gives nothing to Masha. In both cases we must assume that the xor of an empty set of numbers equals 0.

Input

The first line contains integer n (1 ≤ n ≤ 105), showing how many numbers Petya's mother gave him. The second line contains the actual space-separated numbers. They are all integer, non-negative and do not exceed 1018.

Output

Print n space-separated integers, the i-th of them should equal either 1, if Petya keeps the number that follows i-th in his collection, or it should equal 2, if Petya gives the corresponding number to Masha. The numbers are indexed in the order in which they are given in the input.

Examples

Input

6
1 2 3 4 5 6


Output

2 2 2 2 2 2


Input

3
1000000000000 1000000000000 1000000000000


Output

2 2 2


Input

8
1 1 2 2 3 3 4 4


Output

1 2 1 2 2 2 1 2

Solution (in JAVA):

Solution:
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.Random;
import java.util.Collection;
import java.io.IOException;
import java.util.Arrays;
import java.util.NoSuchElementException;
import java.util.TreeSet;
import java.math.BigInteger;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 * @author ogiekako
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        MyScanner in = new MyScanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskD solver = new TaskD();
        solver.solve(1, in, out);
        out.close();
    }
}

class TaskD {
    public void solve(int testNumber, MyScanner in, PrintWriter out) {
        int n = in.nextInt();
        long[] x = new long[n];
        for (int i = 0; i < n; i++) x[i] = in.nextLong();
        int L = 62;
        long xor = 0;
        for (long l : x) xor ^= l;
        debug("xor",Long.toBinaryString(xor));
        long[] matrix = new long[L + 2];
        int[] index = new int[L + 2];
        int rank = 0;
        for (int i = 0; i < n; i++) {
            matrix[rank] = x[i];
            index[rank] = i;
            if (LinearSystem.isIndependent(matrix,rank,x[i])) {
                rank++;
                LinearSystem.rank(matrix,rank);
            }
        }
        for (int i = 0; i < rank; i++)matrix[i] = x[index[i]];
        debug("rank = ", rank);
        debug("matrix");
        for(int i=0;i<rank;i++){
            debug(Long.toBinaryString(matrix[i]));
        }
        debug("index =", index);
        debug();
        int[] order = new int[L];
        {
            int p = 0;
            for (int i = L - 1; i >= 0; i--) if ((xor >> i & 1) == 0) order[p++] = i;
            for (int i = L - 1; i >= 0; i--) if ((xor >> i & 1) == 1) order[p++] = i;
        }
        debug("order = ", order);
        long[] coefficients = LinearSystem.gauss(matrix, rank, order);
        debug("matrix(after gauss)");
        for(int i=0;i<rank;i++){
            debug(Long.toBinaryString(matrix[i]));
        }
        debug("coefficients");
        for(long c:coefficients){
            debug(Long.toBinaryString(c));
        }
        boolean[] res = new boolean[n];
        long xor2 = 0;
        for (int i = 0, p = 0; i < rank; i++) {
            while((matrix[i]>>order[p]&1)==0)p++;
            
            boolean valid = false;
            
            if ((xor >> order[p] & 1) == 0) {
                if ((xor2>>order[p]&1)==0) {
                    valid = true;
                }
            } else {
                if ((xor2>>order[p]&1)==1) {
                    valid = true;
                }
            }
            
            if(valid){
                xor2 ^= matrix[i];
                for(int j=0;j<rank;j++)if((coefficients[i]>>j&1)==1){
                    res[index[j]] ^= true;
                }
            }
        }
        for (int i = 0; i < n; i++)out.printf("%d%c",res[i]?1:2,i==n-1 ? '\n' :' ');
    }
    static void debug(Object...os){
//        System.err.println(Arrays.deepToString(os));
    }

    }

class MyScanner {
    private final InputStream in;
    public MyScanner(InputStream in){
        this.in = in;
    }

    public int nextInt(){
        try{
            int c=in.read();
            if(c==-1) return c;
            while(c!='-'&&(c<'0'||'9'<c)){
                c=in.read();
                if(c==-1) return c;
            }
            if(c=='-') return -nextInt();
            int res=0;
            do{
                res*=10;
                res+=c-'0';
                c=in.read();
            }while('0'<=c&&c<='9');
            return res;
        }catch(Exception e){
            return -1;
        }
    }

    public long nextLong(){
        try{
            int c=in.read();
            if(c==-1) return c;
            while(c!='-'&&(c<'0'||'9'<c)){
                c=in.read();
                if(c==-1) return c;
            }
            if(c=='-') return -nextLong();
            long res=0;
            do{
                res*=10;
                res+=c-'0';
                c=in.read();
            }while('0'<=c&&c<='9');
            return res;
        }catch(Exception e){
            return -1;
        }
    }


    }

class LinearSystem {

    public static int rank(long[] bitVector, int n) {
        int mx = 64;
        int rank = 0;
        for (int i = mx-1; i >= 0 && rank < n; i--) {
            for (int j = rank; j < n; j++) {
                if ((bitVector[j] >>> i & 1) == 1) {
                    ArrayUtils.swap(bitVector, rank, j);
                    break;
                }
            }
            if ((bitVector[rank] >>> i & 1) == 0) continue;
            for (int j = rank + 1; j < n; j++) {
                if ((bitVector[j] >>> i & 1) == 1) {
                    bitVector[j] ^= bitVector[rank];
                }
            }
            rank++;
        }
        return rank;
    }

    /**
     * @param bitVector - bit vector. It should be already normalized.
     * @param rank - #vector used for calculation
     * @param newRow - the row which is judged independence
     * @return - true iff newRow is independent
     */
    public static boolean isIndependent(long[] bitVector,int rank,long newRow){
        int mx = 64;
        for(int i=mx-1,j=0;j<rank && i>=0;j++){
            while(bitVector[j]<<63-i>=0)i--;
            if(newRow<<63-i<0)newRow ^= bitVector[j];
        }
        return newRow != 0;
    }

    /**
     * @param bitVector - bit vector representing rows of boolean matrix
     * @param n - #vector used for gauss elimination
     * @param order - the order of bits used for gauss elimination
     * @return vector is modified. result vector[i] = \sum_j res[i][j] * (given vector[j])
     */
    public static long[] gauss(long[] bitVector, int n, int[] order) {
        int mx = order.length;
        int rank = 0;
        long[] res = new long[n];
        for (int i = 0; i < n; i++) res[i] = 1L << i;
        for (int i = 0; i < mx && rank < n; i++) {
            for (int j = rank; j < n; j++) {
                if ((bitVector[j] >>> order[i] & 1) == 1) {
                    ArrayUtils.swap(bitVector, rank, j);
                    ArrayUtils.swap(res, rank, j);
                    break;
                }
            }
            if ((bitVector[rank] >>> order[i] & 1) == 0) continue;
            for (int j = rank + 1; j < n; j++) {
                if ((bitVector[j] >>> order[i] & 1) == 1) {
                    bitVector[j] ^= bitVector[rank];
                    res[j] ^= res[rank];
                }
            }
            rank++;
        }
        return res;
    }

    }

class ArrayUtils {


    public static void swap(long[] array, int i, int j) {
        long tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }

    }