A xor-basis is a \(K \times K\) matrix, where each row is a \(K\)-dimensional vector with coordinates either \(0\) or \(1\). (In this problem, \(K = 60\), and we’d implement the basis with an array of \(K\) bitmasks)

It models a set, with the abilities to:

• insert a vector into the set,
• test if a vector is the xor-sum of zero or more vectors in the set.

Now let’s learn how to implement each operation:

• We maintain the invariant that each row in the basis is either the zero vector, or a vector where the lowest index of a nonzero column (let’s call it the degree of a vector) is equal to the row’s index, and is the xor-sum of some vectors in the set.
• The basis of an empty set starts with all zeros.
• To insert a vector \(x\), first we find its degree. If the corresponding row in the basis is zero, we put \(x\) into that row, otherwise we xor that row into \(x\). Now \(x\) is either a zero vector, in which case we’re done, or its degree must strictly increase, so we could try reinserting it until we’re done.
• To test a vector is similar to inserting, except that we report “yes” iff \(x\) goes to zero and “no” iff the corresponding row in the basis is zero, without actually modifying the basis.

These operations would take \(O(K)\) time each.

Now imagine this naive method of solving this problem: for each query, we add the corresponding vectors from sequence \(A\) from right to left to a new basis, then answer the query.

This is obviously too slow. Let’s try introducing an augmented basis, where each row vector in the basis also includes a birthdate, that is, the index of \(A\) that was responsible for inserting it. Now we only need \(N\) augmented bases to answer any query; to answer the query for \((l, r, x)\), we take the augmented basis that has the sequence of vectors from \(A_r ... A_1\) inserted, then ignore any rows whose birthdate is lower than \(l\) (i.e. pretend they are zero), to emulate the naive method.

All that remains is to generate and save those augmented bases. To do this, we have to insert elements of \(A\) from left to right, but the resulting basis must pretend that the elements were inserted from right to left. So we have to modify the insertion procedure slightly: if a row in a basis is occupied and it’s older (lower birthdate) than the vector we want to insert, the newer vector would “kick out” the older vector, and now the older vector must be reinserted into the basis.

Thus the problem is solved in \(O((N + Q)K)\) time and \(O(NK)\) space.

Challenge: Solve this Codeforces problem using similar techniques.