103781: [Atcoder]ABC378 B - Garbage Collection

Problem Statement

In AtCoder City, $N$ types of garbage are collected regularly. The $i$-th type of garbage $(i=1,2,\dots,N)$ is collected on days when the date modulo $q_i$ equals $r_i$.

Answer $Q$ queries. In the $j$-th query $(j=1,2,\dots,Q)$, given that the $t_j$-th type of garbage is put out on day $d_j$, answer the next day on which it will be collected.

Here, if the $i$-th type of garbage is put out on a day when that type of garbage is collected, then the garbage will be collected on the same day.

Constraints

• $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$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

$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$

Output

Print $Q$ lines. The $j$-th line $(1\leq j \leq Q)$ should contain the answer to the $j$-th query.

Sample Input 1

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

Sample Output 1

3
3
10
17
10

• 1st query: The 1st type of garbage is collected on day $3$ for the first time after day $1$.
• 2nd query: The 1st type of garbage is collected on day $3$ for the first time after day $3$.
• 3rd query: The 1st type of garbage is collected on day $10$ for the first time after day $4$.

问题陈述

在AtCoder市，定期收集N种垃圾。第i种垃圾（i=1,2,…,N）在日期除以$q_i$等于$r_i$的日子里被收集。

回答Q个查询。在第j个查询（j=1,2,…,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日首次被收集。