Azugand

Azugand, the city from the famous Prahovand Valley, is known for its peculiar structure: it has $N$ intersections, numbered from $1$ to $N$, all of which have an assigned value $V_i$. Two distinct intersections have a street between them if and only if the bitwise AND (represented as $\&$) of their values is non-zero.

Formally, you are given a graph with $N$ vertices, each vertex having a value $V_i$ assigned to it. We have an edge between two distinct vertices $i$ and $j$ iff $V_i\ \&\ V_j \neq 0$.

Task

Andrei, a well-known child from the valley, wants to make a table with the shortest distances between two points of interest, but he is overwhelmed by the number of queries he wants to solve, so he asks for your help! You are given $Q$ queries, in which you have to compute $\text{cost}(X,Y)$. We define $\text{cost}(X,Y)$ as the minimum number of edges that are in the shortest path in the graph between vertices $X$ and $Y$. If we can’t reach vertex $Y$ from vertex $X$, then the value of $\text{cost}(X,Y)$ is $-1$.

Input data

The first line of input contains two integers $N$ and $Q$, the number of vertices in the graph, and the number of queries, respectively.

The next line contains $N$ integers $V_1, V_2, \dots, V_N$, the values assigned to the vertices of the graph.

Each of the next $Q$ lines of the input contains two distinct integers $X_i$ and $Y_i$, the vertices for which you must compute $\text{cost}(X_i,Y_i)$.

Output data

Print $Q$ integers, each one on a separate line: the value of $\text{cost}(X_i, Y_i)$ for each query.

Constraints and clarifications

• $1 \leq N \leq 200 \ 000$
• $1 \leq Q \leq 200 \ 000$
• $0 \leq V_i < 2^{20}$ for each $1 \leq i \leq N$
• $1 \leq X_i \neq Y_i \leq N$ for each $1 \leq i \leq Q$

Example 1

stdin

4 4
9 3 16 6
1 2
2 4
4 1
2 3

stdout

1
1
2
-1

Explanation

In the first query, $V_1 = 9$ and $V_2 = 3$, $9\ \&\ 3 = 1$, so there is an edge between vertices $1$ and $2$, so the minimum distance is $1$.

In the second query, $V_2 = 3$ and $V_4 = 6$, $3\ \&\ 6 = 2$, so there is an edge between vertices $2$ and $4$, so the minimum distance is $1$.

In the third query, $V_4 = 6$ and $V_1 = 9$, $6\ \&\ 9 = 0$, so there is no edge between vertices $4$ and $1$, so the minimum distance is at least $2$. For the path $4, 2, 1$ the values are $6, 3, 9$ respectively which means that there is an edge between vertices $4$ and $2$ also between $2$ and $1$, so there is a path of length $2$ between vertices $4$ and $1$.

In the fourth query, $V_1\ \&\ V_3 = 0$, $V_2\ \&\ V_3 = 0$ and $V_4\ \&\ V_3 = 0$, which means that there are no edges connected to vertex $3$, so there is no path between vertices $2$ and $3$.

Example 2

stdin

7 5
3072 5120 67584 73728 49152 24576 40960
2 5
7 3
1 6
5 6
7 2

stdout

5
2
3
1
4