I - Segment CRT

問題

長さ $N$ の数列 $a, b$ と長さ $Q$ の配列 $L, R$ が与えられます。

$Q$ 以下のすべての $i$ について、$i$ の小さい順に以下の値を出力してください。

• $L_i \leq j\leq R_i$ を満たすすべての $j$ について、$G_i\equiv a_j \pmod {b_j}$ を満たす最小の自然数 $G_i$
• ただし、存在しないか $G_i > 2^{31} - 1$ であるなら $-1$

制約

• $1\leq N, Q\leq 10^5$
• $0\leq a_i< b_i\leq 2^{31} - 1$
• $1\leq L_i\leq R_i\leq N$
• 入力はすべて整数

小課題

1. (50点) $Q = 1$
2. (100点) 追加の制約はない

入力

$N$

$a_1~b_1$

$a_2~b_2$

$\vdots$

$a_{N-1}~b_{N-1}$

$a_N~b_N$

$Q$

$L_1~R_1$

$L_2~R_2$

$\vdots$

$L_{Q-1}~R_{Q-1}$

$L_Q~R_Q$

入力例1

5
4 5
4 9
3 8
2 7
5 13
1
1 5
Copy

出力例1

499
Copy

この入力例は小課題 1, 2 の制約を満たします。

入力例2

5
4 5
4 9
3 8
2 7
5 13
4
1 5
1 3
1 2
2 2
Copy

出力例2

499
139
4
4
Copy

この入力例は小課題 2 の制約を満たします。