【模板】扩展中国剩余定理(EXCRT)

题目描述

给定 $n$ 组非负整数 $a_i, b_i$ ,求解关于 $x$ 的方程组的最小非负整数解。 $$\begin{cases} x \equiv b_1\ ({\rm mod}\ a_1) \\ x\equiv b_2\ ({\rm mod}\ a_2) \\ ... \\ x \equiv b_n\ ({\rm mod}\ a_n)\end{cases}$$

输入输出格式

输入格式


输入第一行包含整数 $n$。 接下来 $n$ 行,每行两个非负整数 $a_i, b_i$。

输出格式


输出一行,为满足条件的最小非负整数 $x$。

输入输出样例

输入样例 #1

3
11 6
25 9
33 17

输出样例 #1

809

说明

$n \leq 10^5, 1 \leq a_i \leq 10^{12}, 0 \leq b_i \leq 10^{12}, b_i < a_i$,保证答案不超过 $10^{18}$。 **请注意程序运行过程中进行乘法运算时结果可能有溢出的风险。** 数据保证有解