[GESP202509 八级] 最短距离

给定正整数 $p,q$ 以及常数 $N=10^{18}$。现在构建一张包含 $N$ 个结点的带权无向图，结点依次以 $1,2,\ldots,N$ 编号。对于任意满足 $1\le u

第一行，三个正整数 $n,p,q$，分别表示询问数量，结点编号互质时的边权，以及结点编号不互质时的边权。

接下来 $n$ 行，每行两个正整数 $a_i,b_i$，表示一组询问。

输出共 $n$ 行，每行一个整数，表示结点 $a_i$ 与结点 $b_i$ 之间的最短距离。

对于 $30\%$ 的测试点，保证 $1\le n\le 10$，$1\le a_i,b_i\le 50$。

对于另外 $30\%$ 的测试点，保证 $1\le a_i,b_i\le 250$。

对于所有测试点，保证 $1\le n\le 10^4$，$1\le a_i,b_i\le 10^9$，$1\le p,q\le 10^9$。