And mex#11807
Given an array of length , let be the set of all possible ANDs of 's not empty subsets. We need to find (the minimum excluded value of ).
Initially, we compute this for the entire array. Then, additional elements are gradually added to the array; we need to determine the updated after each insertion.
Here, AND means bitwise AND operation.
The (minimum excluded value) of a set of non-negative integers is the smallest non-negative integer that is not present in the set. The of [1, 0, 2, 4] is . The of [1, 2, 3] is . The of [0, 2, 3] is .
The first line contains two integers (1 \le n, 0 \le m, n + m \le 10^6) — the length of an array and the number of additional elements.
The second line contains integers a_i (0 \le a_i < 2^{20}) — elements of an array .
The third line contains integers b_i (0 \le b_i < 2^{20}) — additional elements.
In a single line, output m + 1 integers, where the first one is a for array . The next are the s for the updated array after each insertion.
Example 1
Example 2
( points): n + m \le 15;
( points): a_i < 2^{12} (1 \le i \le n), b_i < 2^{12} (1 \le i \le m), n + m \le 2000;
( points): a_i < 2^{15} (1 \le i \le n), b_i < 2^{15} (1 \le i \le m);
( points): m = 0;
( points): a_i < 2^{18} (1 \le i \le n), b_i < 2^{18} (1 \le i \le m), n + m \le 10^5;
( points): no additional constraints;