Subset XOR First Occurrence Index

Given a sequence \(A\) of \(n\) positive integers (indexed from 1), define \(S = \{1,2,\ldots,n\}\) and its power set \(2^S\) (i.e. the set of all subsets of \(S\)). For any subset \(T \subseteq S\) define a function \(f(T)\) as follows:

\(f(\emptyset)=0\) and for \(T\neq\emptyset,\; f(T)=\bigoplus_{t\in T}A_t\), where \(\oplus\) denotes the bitwise XOR operation.

After computing \(f(T)\) for every \(T\) in \(2^S\), all values are sorted in non-decreasing order to form a sequence \(B\) (with indices starting from 1). Given a number \(x\), determine the 1-indexed position of its first occurrence in \(B\). If \(x\) does not appear in \(B\), output -1.

Note: Since each subset is considered, the total number of elements in \(B\) is \(2^n\). You are guaranteed that \(n\) is small enough (e.g. \(n\leq20\)) to allow enumeration of all subsets.

inputFormat

The input consists of two lines:

• The first line contains two integers \(n\) and \(x\) separated by a space, where \(n\) is the length of the sequence and \(x\) is the target number.
• The second line contains \(n\) positive integers \(A_1, A_2, \ldots, A_n\) separated by spaces.

It is guaranteed that \(n\) is small (e.g., \(n\leq20\)).

outputFormat

Output a single integer: the 1-indexed position of the first occurrence of \(x\) in the sorted sequence \(B\). If \(x\) does not appear in \(B\), output -1.

sample

3 0
1 2 3

1