/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 200 点
問題文
AtCoder 市では、N 種類のゴミを定期的に収集しています。i\;(=1,2,\dots,N) 種類目のゴミは、日付を q_i で割ったあまりが r_i の日に収集されます。
Q 個の質問に答えてください。j\;(=1,2,\dots,Q) 番目の質問では、d_j 日に t_j 種類目のゴミが出たときに、次にそれが収集される日を答えてください。
ただし、i 種類目のゴミが出た日が、 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 日です。
Score : 200 points
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.