XOR Minimum

View as PDF

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

Authors:
Problem type

Given a 0-indexed list of non-negative integers, and queries each consisting of one non-negative integer , output the smallest index of the minimum value in the list after each number in the list is XOR'd with 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, , and .

The second line will contain space-separated integers, .

The next lines will each contain one integer .

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 .

For 5 out of the 17 available marks, and

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