## XOR Minimum

View as PDF

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$$.

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