Squeeze OR

 Chef has an array 

A$A$ of N$N$ integers. He asks you Q$Q$ queries. For each query, you are given the following:

• An integer X$X$ (0≤X<220)$(0\le X<2^{20})$.
• An array B$B$ of size M$M$ such that 1≤Bj≤N$1\le B_j\le N$.

You need to erase minimum number of elements from A$A$ such that the bitwise-OR of the remaining elements is at most X$X$ and no element having index Bj$B_j$ is erased.

For each query, find the maximum number of remaining elements such that the bitwise OR of the remaining elements is at most X$X$ and no element with index Bj$B_j$ is erased. If it is impossible to get an OR of at most X$X$, print −1$-1$.

Note: The bitwise OR of an empty array is considered 0$0$.

Input Format

• The first line of the input consists of integers N$N$ and Q$Q$, the number of elements in the array and the number of queries.
• The next line contains N$N$ space separated integers, the elements of the array A$A$. The descriptions of the Q$Q$ queries follow.
• The first line of each query consists of integers X$X$ and M$M$, the integer X$X$ and the number of indices that cannot be erased.
• The last line of each query consists of M$M$ space separated integers Bj$B_j$ denoting that the elements ABj$A_{B_j}$ cannot be erased. Note that, this line is omitted if M=0$M=0$.

Output Format

Print Q$Q$ lines, the answers to each of the queries.
For each query, print -1 if it is impossible to get an OR of at most X$X$. Otherwise, print the maximum number of remaining elements.

Constraints

• 1≤N≤2⋅105$1\le N\le 2\cdot {10}^5$
• 0≤M≤N$0\le M\le N$
• 1≤Q≤2⋅105$1\le Q\le 2\cdot {10}^5$
• 0≤Ai,X<220$0\le A_i,X<2^{20}$
• 1≤Bj<Bj+1≤N$1\le B_j<B_{j+1}\le N$, ∀j$\mathrm{\forall }j$ such that 1≤j<M$1\le j<M$
• Sum of M$M$ over all queries does not exceed 2⋅105$2\cdot {10}^5$.

Subtasks

• Subtask 1 (40 points): Q=1,M=0$Q=1,M=0$.
• Subtask 2 (60 points): No additional constraints.

Sample Input 1 

3 1
4 3 5
6 0

Sample Output 1 

2

Explanation

The given array A=[4,3,5]$A=[4,3,5]$. In binary representation, A=[1002,0112,1012]$A=[{100}_2,{011}_2,{101}_2]$. We are given that the size of array B$B$ is 0$0$. Thus, we can delete any element of the array A$A$.

• Erase 0$0$ elements: The remaining array A=[1002,0112,1012]$A=[{100}_2,{011}_2,{101}_2]$. Bitwise OR of the remaining elements is 1002${100}_2$ |$|$ 0112${011}_2$ |$|$ 1012=1112=7${101}_2={111}_2=7$. Since X<7$X<7$, we have to erase some elements of the array.
• Erase 1$1$ element: If we erase the element at index 2$2$, the remaining array A=[1002,1012]$A=[{100}_2,{101}_2]$. Bitwise OR of the remaining elements is:
  1002${100}_2$ |$|$ 1012=1012=5${101}_2={101}_2=5$. Since X≥5$X\ge 5$, all the required conditions are satisfied.

Thus, the maximum number of remaining elements is 2$2$.

Sample Input 2 

5 2
14 8 11 6 3
14 1
4
3 2
2 4

Sample Output 2 

3
-1

Explanation

The given array A=[14,8,11,6,3]$A=[14,8,11,6,3]$. In binary representation, A=[11102,10002,10112,01102,00112]$A=[{1110}_2,{1000}_2,{1011}_2,{0110}_2,{0011}_2]$.

• Query 1$1$: We are given that the element at index 4$4$ cannot be erased.
  A possible way to satisfy the given conditions is to erase the elements at indices 3$3$ and 5$5$. Thus, the remaining array would be A=[11102,10002,01102]$A=[{1110}_2,{1000}_2,{0110}_2]$. The bitwise OR of remaining elements would be 14$14$ which is less than equal to X$X$.
  It can be proven that the maximum number of remaining elements cannot exceed 3$3$.

• Query 2$2$: We are given that the elements at indices 2$2$ and 4$4$ cannot be erased. In the worst case that we erase all other elements, we are left with [10002,01102]$[{1000}_2,{0110}_2]$. The bitwise OR of these elements is 11102=14>3${1110}_2=14>3$. Thus, it is impossible to erase some elements leaving an OR of at most 3$3$.