问题陈述

在 AtCoder 市，有 $N$ 种垃圾定期收集。第 $i$ 种垃圾（$i=1,2,\dots,N$）在日期对 $q_i$ 取模等于 $r_i$ 的日子被收集。

回答 $Q$ 个查询。在第 $j$ 个查询（$j=1,2,\dots,Q$）中，给定第 $t_j$ 种垃圾在第 $d_j$ 天被扔出，回答它下一次将被收集的日期。

这里，如果第 $i$ 种垃圾在收集该种垃圾的日期被扔出，那么该垃圾会在同一天被收集。

约束

• $1 \leq N \leq 100$

• $0 \leq r_i < q_i \leq 10^9$

• $1 \leq Q \leq 100$

• $1 \leq t_j \leq N$

• $1 \leq d_j \leq 10^9$

• 所有输入值均为整数。

输入

输入从标准输入按以下格式给出：

$N$ $q_1 r_1$ $q_2 r_2$ $\vdots$ $q_N r_N$ $Q$ $t_1 d_1$ $t_2 d_2$ $\vdots$ $t_Q d_Q$

输出

输出 $Q$ 行。第 $j$ 行（$1\leq j \leq Q$）应包含第 $j$ 个查询的答案。

样例输入 1

2
7 3
4 2
5
1 1
1 3
1 4
1 15
2 7

样例输出 1

3
3
10
17
10

• 第 1 个查询：第 1 种垃圾在日期 1 或之后首次被收集是在日期 3。

• 第 2 个查询：第 1 种垃圾在日期 3 或之后首次被收集是在日期 3。

• 第 3 个查询：第 1 种垃圾在日期 4 或之后首次被收集是在日期 10。