skeep 팬클럽 임무

skeep 팬클럽의 멤버로 활동 중인 호반우는 임원진이 되고 싶어 클럽장인 skeep한테 부탁하여 다음과 같은 임무를 받게 되었다.

현재 호반우는 유명인사 skeep의 이름을 딴 대륙인 skeep land에 와 있다.

skeep land에는 $N$개의 지점이 존재하며, 지점들은 도로로 연결되어 하나의 트리를 이룬다.

각 지점에는 팬클럽이 하나씩 위치해 있으며, 해당 팬클럽의 소속을 나타내는 정수 $a_i$가 할당되어 있다. $a_i = 0$인 경우 해당 지점에는 skeep 팬클럽이 위치해 있음을 의미한다.

여기서 skeep 팬클럽이 아닌 두 지점 $u$, $v$ 중, 각 쿼리마다 주어지는 정수 $m_i$에 대해 $(a_u \operatorname{AND} m_i) \ne (a_v \operatorname{AND} m_i)$을 만족하는 두 지점을 점령하여 skeep 팬클럽 기지로 삼으려고 한다. 단, skeep은 두 신규 기지가 가까이 있는 걸 원치 않기 때문에 두 기지는 최대한 멀리 떨어져 있어야 한다.

여기서 각 쿼리마다 두 개의 기지를 점령했을 때 그 거리를 찾아야 한다.

호반우의 임무는 각 쿼리마다 두 개의 기지를 점령했을 때, 그 거리를 찾는 것이다.

각 쿼리는 서로 독립적이므로, 이전 쿼리에서 선택한 지점을 다음 쿼리에서도 다시 선택할 수 있다. 실제로 점령해서 $a_i$가 바뀌는 것은 아니다.

skeep의 말에 따르면, 이 임무를 완수하면 호반우는 임원이 될 수 있다고 한다.

호반우가 임무를 완수할 수 있게 도와주자!

첫 번째 줄에는 팬클럽 지점의 개수와 쿼리의 개수 $N$, $Q$가 공백으로 구분되어 주어진다. ($2 \le N \le 200\,000$), ($1 \le Q \le 200\,000$)

각 쿼리마다 조건을 만족하는 두 팬클럽 지점을 선택했을 때의 거리를 출력한다.

만약 조건을 만족하는 두 지점이 존재하지 않는다면, -1을 출력한다.