配点 : 600 点
問題文
长度 N 的正整数序列 对于 A = (A_1, \dots, A_N), B = (B_1, \dots, B_N) 。
k = 1, \dots, M ,满足以下所有条件的正整数序列: C = (C_1, \dots, C_N) 的总数 输出 998244353 求余数。
- A_i \leq C_i \leq B_i \, (1 \leq i \leq N)
- \mathrm{gcd} (C_1, \dots, C_N) = k
制約
- 1 \leq N \leq 10^5
- 1 \leq M \leq 10^5
- 1 \leq A_i \leq B_i \leq 10^5 \, (1 \leq i \leq N)
- 所有输入均为整数。
入力
输入将以以下形式从标准输入给出。
N M A_1 B_1 \vdots A_N B_N
出力
M 行。i \, (1 \leq i \leq M) 行中,k = i 满足问题陈述中的条件 打印除以 C 的总数 输出 998244353 后的余数。 当
入力例 1
3 10 1 9 4 8 7 10
出力例 1
151 20 3 3 1 0 1 1 0 0
k = 4 时,C = (4, 4, 8), (8, 4, 8), (4, 8, 8) 满足条件。
入力例 2
1 1 2 100000
出力例 2
0