Misha and XOR (Codeforces 504D)
Tags: Others, bitmasks

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.

Note: The XOR sum of numbers is the result of bitwise sum of numbers modulo 2.

Sample Inputs:
7
7
6
5
4
3
2
1

2
5
5

Sample Outputs:
0
0
0
3 0 1 2
2 1 2
2 0 2
2 0 1

0
1 0

Solution (Python):
m = int(input())
arr = []
bits = []
for i in range(m):
    x = int(input())
    bit = 0
    for j in range(len(arr)):
        p = arr[j] ^ x
        if p < x:
            x = p
            bit ^= bits[j]
    if x != 0:
        print(0)
        arr.append(x)
        bits.append(bit ^ 1 << i)
    else:
        ans = ''
        r = 0
        for j in range(i):
            if bit & 1 << j == 1 << j:
                r += 1
                ans += str(j) + ' '
        print(str(r) + ' ' + ans)

Solution (Python):
m = int(input())
arr = []
bits = []
for i in range(m):
    x = int(input())
    bit = 0
    for j in range(len(arr)):
        p = arr[j] ^ x
        if p < x:
            x = p
            bit ^= bits[j]
    if x != 0:
        print(0)
        arr.append(x)
        bits.append(bit ^ 1 << i)
    else:
        ans = ''
        r = 0
        for j in range(i):
            if bit & 1 << j == 1 << j:
                r += 1
                ans += str(j) + ' '
        print(str(r) + ' ' + ans)

Solution (Python):
import sys, os
numbs = [int(x) for x in sys.stdin.buffer.read().split()]
n = numbs.pop(0)
base = []
out = []
for i in range(n):
    x = numbs[i]
    how = 0
    for (b, rep) in base:
        if x.bit_length() == b.bit_length():
            x ^= b
            how ^= rep
    if x:
        how |= 1 << i
        a = 0
        b = len(base)
        while a < b:
            c = a + b >> 1
            if base[c][0] > x:
                a = c + 1
            else:
                b = c
        base.insert(a, (x, how))
        out.append(0)
    else:
        outind = len(out)
        out.append(-1)
        y = bin(how).encode('ascii')
        ylen = len(y)
        for i in range(2, len(y)):
            if y[i] == 49:
                out.append(ylen - 1 - i)
        out[outind] = len(out) - 1 - outind
os.write(1, b'\n'.join((str(x).encode('ascii') for x in out)))