异或图

题号：NC205348
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

牛妹是一个喜欢无向图的女孩子。

牛妹现在有 $n$ 个点构成的点集 $V$ ，每个点有点权 $a_i$ 。

牛妹想用这 $n$ 个点构造 $q$ 个无向图 $G_i=(V,E_i)$ 。对于第 $i$ 个无向图，牛妹指定了一个参数 $k_i$ 。牛妹规定 $(u,v)\in E_i$ 当且仅当 $a_u \oplus a_v=k_i$ ，其中 $\oplus$ 表示二进制按位异或运算。

牛妹并不想知道这 $q$ 个无向图具体长什么样，所以对于第 $i$ 个无向图，你只需要告诉牛妹 $x_i$ 到 $y_i$ 的最短路径长度。

第一行两个整数 ，表示点集大小和无向图数量。
第二行 n 个整数 ， 表示第 i 个点的点权。
接下来 q 行，第 i 行三个整数 ， 表示第 i 个无向图的参数， 表示询问最短路的起点和终点。

输出 q 行，第 i 行一个整数，表示第 i 个无向图中  到  的最短路长度。若  和  不连通则输出 -1。

示例1

复制

复制