XOR Minimum

View as PDF

Submit solution

Points: 17 (partial)
Time limit: 2.0s
Memory limit: 128M

Authors:
Problem type

Given a 0-indexed list of \(N\) non-negative integers, and \(Q\) queries each consisting of one non-negative integer \(x\), output the smallest index of the minimum value in the list after each number in the list is XOR'd with \(x\) for each query. Queries are persistent. That is, any previous queries change the list directly and affect the current query's answer.

Input Specification

The first line will contain two space-separated integers, \(N\ (1 \le N \le 10^5)\), and \(Q\ (1 \le Q \le 10^5)\).

The second line will contain \(N\) space-separated integers, \(a_1, a_2, \ldots, a_N\ (0 \le a_i \le 10^9)\).

The next \(Q\) lines will each contain one integer \(x\ (0 \le x \le 10^9)\).

Output Specification

For each query, output the smallest index of the minimum value in the list after every number in the list has been XOR'd with \(x\).

Subtasks

For all subtasks, \({1 \le N \le 10^5}\) and \({1 \le Q \le 10^5}\)

For 5 out of the 17 available marks, \({1 \le N \le 10^4}\) and \({1 \le Q \le 10^4}\)

Sample Input 1

8 4
2 15 8 1 6 2 16 8
0
2
10
7

Sample Output 1

3
0
2
1

Explanation for Sample Output 1

2 15 8 1 6 2 16 8

The array is unchanged after the first XOR operation. The minimum is simply 1 at index 3.

0 13 10 3 4 0 18 10

In this case, the first of the two zeroes is chosen (index 0).

10 7 0 9 14 10 24 0

The first occurrence of the minimum value (0) is at index 2.

13 0 7 14 9 13 31 7

The minimum value (0) is at index 1.

Sample Input 2

7 5
7 7 8 0 0 10 16
12
14
16
6
12

Sample Output 2

2
3
6
6
6

Comments

There are no comments at the moment.