//    BitArray


public class BitArray {

    //  Variables
    
    public static final long MAX_LENGTH=(Integer.MAX_VALUE-8L)*64L;

    private static final long[] BITS={1L,2L,4L,8L,16L,32L,64L,128L,256L,512L,1024L,2048L,4096L,8192L,16384L,32768L,65536L,131072L,262144L,524288L,1048576L,2097152L,4194304L,8388608L,16777216L,33554432L,67108864L,134217728L,268435456L,536870912L,1073741824L,2147483648L,4294967296L,8589934592L,17179869184L,34359738368L,68719476736L,137438953472L,274877906944L,549755813888L,1099511627776L,2199023255552L,4398046511104L,8796093022208L,17592186044416L,35184372088832L,70368744177664L,140737488355328L,281474976710656L,562949953421312L,1125899906842624L,2251799813685248L,4503599627370496L,9007199254740992L,18014398509481984L,36028797018963968L,72057594037927936L,144115188075855872L,288230376151711744L,576460752303423488L,1152921504606846976L,2305843009213693952L,4611686018427387904L,-9223372036854775808L};
    private static final long[] COMP={-2L,-3L,-5L,-9L,-17L,-33L,-65L,-129L,-257L,-513L,-1025L,-2049L,-4097L,-8193L,-16385L,-32769L,-65537L,-131073L,-262145L,-524289L,-1048577L,-2097153L,-4194305L,-8388609L,-16777217L,-33554433L,-67108865L,-134217729L,-268435457L,-536870913L,-1073741825L,-2147483649L,-4294967297L,-8589934593L,-17179869185L,-34359738369L,-68719476737L,-137438953473L,-274877906945L,-549755813889L,-1099511627777L,-2199023255553L,-4398046511105L,-8796093022209L,-17592186044417L,-35184372088833L,-70368744177665L,-140737488355329L,-281474976710657L,-562949953421313L,-1125899906842625L,-2251799813685249L,-4503599627370497L,-9007199254740993L,-18014398509481985L,-36028797018963969L,-72057594037927937L,-144115188075855873L,-288230376151711745L,-576460752303423489L,-1152921504606846977L,-2305843009213693953L,-4611686018427387905L,9223372036854775807L};

    private long bitLength;
    private int arrayLength;

    private long[] array;

    //  Constructor
    
    /**
     * Creates new BitArray.
     */
    public BitArray(long length) {
        if (length<0L) {
            throw (new IllegalArgumentException("BitArray length can't be negative: "+length));
        }
        if (length>MAX_LENGTH) {
            throw (new IllegalArgumentException("BitArray length can't be over "+MAX_LENGTH+": "+length));
        }
        bitLength=length;
        arrayLength=(int)((length+63L)/64L);
        array=new long[arrayLength];
    }

    //  Accessors
    
    /**
     * Set value in specified index to true or false.
     */
    public void set(long index, boolean value) {
        if (index<0L || index>=bitLength) {
            throw (new IndexOutOfBoundsException("BitArray index is out of range: "+index));
        }
        int i=(int)(index/64L);
        int b=(int)(index%64L);
        innerSet(i,b,value);
    }

    /**
     * Get value in specified index.
     */
    public boolean get(long index) {
        if (index<0L || index>=bitLength) {
            throw (new IndexOutOfBoundsException("BitArray index is out of range: "+index));
        }
        int i=(int)(index/64L);
        int b=(int)(index%64L);
        return (((array[i]>>b)&1)>0);
    }

    /**
     * Set all values in range to true or false.
     */
    public void setRange(long startIndex, long length, boolean value) {
        if (startIndex<0L || startIndex>=bitLength) {
            throw (new IndexOutOfBoundsException("BitArray.setRange(...): Start index is out of range: "+startIndex));
        }
        if (length<0L) {
            throw (new IllegalArgumentException("BitArray.setRange(...): Length can't be negative: "+length));
        }
        if (length==0L) {
            return;
        }
        long endIndex=startIndex+length-1;
        if (endIndex>=bitLength) {
            throw (new IndexOutOfBoundsException("BitArray.setRange(...): End index is out of range: "+endIndex));
        }
        int startArrayIndex=(int)(startIndex/64L);
        int startBit=(int)(startIndex%64L);
        int endArrayIndex=(int)(endIndex/64L);
        int endBit=(int)(endIndex%64L);
        if (startArrayIndex==endArrayIndex) {
            for (int b=startBit; b<=endBit; b++) {
                innerSet(startArrayIndex,b,value);
            }
        } else {
            for (int b=startBit; b<64; b++) {
                innerSet(startArrayIndex,b,value);
            }
            innerSetArrayRange(startArrayIndex+1,endArrayIndex,(value?-1L:0L));
            for (int b=0; b<=endBit; b++) {
                innerSet(endArrayIndex,b,value);
            }
        }
    }

    /**
     * Set all values to true or false.
     */
    public void setAll(boolean value) {
        innerSetArrayRange(0,arrayLength,(value?-1L:0L));
    }

    /**
     * Get count of values that are true.
     */
    public long getTrueCount() {
        if (bitLength==0L) {
            return 0L;
        }
        long count=0L;
        int fulls=(int)(bitLength/64L);
        for (int n=0; n<fulls; n++) {
            count+=innerGetTrueCount(array[n]);
        }
        int leftOver=(int)(bitLength%64L);
        count+=innerGetTrueCount(array[arrayLength-1],leftOver);
        return count;
    }

    /**
     * Turn this instance to normal boolean array. Length of array have to be less or equal to Integer.MAX_VALUE
     */
    public boolean[] toBooleanArray() {
        if (bitLength>Integer.MAX_VALUE-8) {
            System.out.println("ERROR! BitArray.toBooleanArray(): Length of BitArray is too long to fit in normal array");
            return null;
        }
        boolean[] boolArray=new boolean[(int)(bitLength)];
        int boolIndex=0;
        int fulls=(int)(bitLength/64L);
        for (int n=0; n<fulls; n++) {
            if (array[n]==0L) {
                boolIndex+=64;
                continue;
            } else if (array[n]==-1L) {
                for (int m=0; m<64; m++) {
                    boolArray[boolIndex]=true;
                    boolIndex++;
                }
            } else {
                long i=array[n];
                for (int m=0; m<64; m++) {
                    boolArray[boolIndex]=((i&1)==1);
                    i>>=1;
                    boolIndex++;
                }
            }
        }
        int leftOver=(int)(bitLength%64L);
        if (leftOver>0) {
            long ip=array[fulls];
            for (int m=0; m<leftOver; m++) {
                boolArray[boolIndex]=((ip&1)==1);
                ip>>=1;
                boolIndex++;
            }
        }
        return boolArray;
    }

    //  Private
    
    private void innerSet(int i, int b, boolean value) {
        if (value) {
            array[i]=(array[i] | BITS[b]);
        } else {
            array[i]=(array[i] & COMP[b]);
        }
    }

    private void innerSetArrayRange(int startInclusive, int endExclusive, long arrayValue) {
        for (int n=startInclusive; n<endExclusive; n++) {
            array[n]=arrayValue;
        }
    }

    private long innerGetTrueCount(long i) {
        if (i==0L) {
            return 0L;
        } else if (i==-1L) {
            return 64L;
        }
        return innerGetTrueCount(i,64);
    }

    private long innerGetTrueCount(long i, int bitsToCount) {
        long count=0L;
        while (bitsToCount>0) {
            count+=(i&1L);
            i>>=1;
            bitsToCount--;
        }
        return count;
    }

}