背景

GESP八级真题(202509)

描述

给定正整数 $p, q$ 以及常数 $N = 10^8$ 。现在构建一张包含 $N$ 个结点的带权无向图，结点依次以 $1, 2, ..., N$ 编号。对于任意满足 $1 \le u < v \le N$ 的 $u, v$，向图中加入一条连接结点 $u$ 与结点 $v$ 的无向边，边权取决于 $u, v$ 是否互质：

若 $u, v$ 互质（即 $u, v$ 的最大公因数为 1 ），则连接结点 $u$ 与结点 $v$ 的无向边长度为 $p$；

否则连接结点 $u$ 与结点 $v$ 的无向边长度为 $q$。

现在给定 $n$ 组询问，第 $i$（$1 \le i \le n$）组询问给定两个正整数 $a_i, b_i$ ，你需要回答结点 $a_i$ 与结点 $b_i$ 之间的最短距离。

格式

输入

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

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

输出

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

样例

4 4 3
1 2
2 3
4 2
3 5

4
4
3
4

5 2 6
1 2
2 3
4 2
3 5
6 6

2
2
4
2
0

数据规模

对于所有测试点，保证 $ 1 \le n \le 10^5，1 \le q \le 2 \times 10^4, 1 \le p_i \le n, 1 \le s_i \le n, k_i \ge 1 且 \sum k_i \le 10^5 $。

对于 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 $。

限制

时间限制：1.0 s

空间限制：512.0 MB