P4777 [Template] Extended Chinese Remainder Theorem (EXCRT).

Given $n$ pairs of non-negative integers $a_i, b_i$, find the smallest non-negative integer solution to the system of equations in $x$. $$\begin{cases}x\equiv b_1\pmod{a_1}\\x\equiv b_2\pmod{a_2}\\\dots\\x\equiv b_n\pmod{a_n}\end{cases}$$

The first line contains an integer $n$. The next $n$ lines each contain two non-negative integers $a_i, b_i$.

Output one line: the smallest non-negative integer $x$ that satisfies the conditions.

For $100\%$ of the testdata, $1 \le n \le {10}^5$, $1 \le a_i \le {10}^{12}$, $0\leq b_i \leq 10^{12}$. It is guaranteed that the least common multiple of all $a_i$ does not exceed ${10}^{18}$. **Please note that during the execution of the program, multiplication operations may overflow.** It is guaranteed that a solution exists. Translated by ChatGPT 5