K-th Smallest XOR Value

Difficulty: 2200 4000 ms 128 MB

bitwise linear-algebra

Consider all distinct XOR values obtainable from subsets of the array (the empty subset gives 0). Print the K-th smallest distinct value, or −1 if fewer than K exist.

Input: the first line has N and K; the second line has N non-negative integers.

Output: the K-th smallest achievable XOR, or −1.

Constraints:

• 1 ≤ N ≤ 10⁵
• 0 ≤ a_i < 2³⁰

Sample Tests

3 3
1 2 3

2

2 4
1 2

3

Read the Editorial