C - Removal of Multiples Editorial /

Time Limit: 4 sec / Memory Limit: 1024 MiB

配点 : 600 点

問題文

すべての正整数からなる集合 S があります．

Q 個のクエリを順に処理してください．i 番目のクエリでは，2 以上の整数 A_i および，正整数 B_i が与えられるので，次の 2 つのことを順に行ってください．

  1. S から A_i の倍数である要素をすべて削除する．
  2. S の要素のうち小さい方から B_i 番目のものを出力する．なお本問の制約のもとで，S はこの時点で B_i 個以上の要素を含むことが証明できる．

制約

  • 1\leq Q\leq 10^5
  • 2\leq A_i\leq 10^9
  • 1\leq B_i\leq 10^5
  • 入力される値はすべて整数

入力

入力は以下の形式で標準入力から与えられます．

Q
A_1 B_1
\vdots
A_Q B_Q

出力

Q 行出力してください．i 行目には i 番目のクエリにおいて，S から A_i の倍数である要素をすべて削除した後の，S の要素のうち小さい方から B_i 番目のものを出力してください．

入力例 1

5
5 10
6 1
6 10
9 10
123456789 111

出力例 1

12
1
14
16
178

S の要素を昇順に並べたときの先頭に近い部分がどうなるかを説明します．

  • 初期状態では，S=\lbrace 1,2,3,4,5,6,7,8,9,10,\ldots\rbrace です．
  • 1 番目のクエリでは 5 の倍数を削除して，S=\lbrace1,2,3,4,6,7,8,9,11,12,\ldots\rbrace となります．
  • 2 番目のクエリでは 6 の倍数を削除して，S=\lbrace1,2,3,4,7,8,9,11,13,14,\ldots\rbrace となります．
  • 3 番目のクエリでは 6 の倍数を削除して，S=\lbrace1,2,3,4,7,8,9,11,13,14,\ldots\rbrace となります．
  • 4 番目のクエリでは 9 の倍数を削除して，S=\lbrace1,2,3,4,7,8,11,13,14,16,\ldots\rbrace となります．
  • 5 番目のクエリでは 123456789 の倍数を削除して，S=\lbrace1,2,3,4,7,8,11,13,14,16,\ldots\rbrace となります．

Score : 600 points

Problem Statement

Let S be the set of all positive integers.

Process Q queries in order. The i-th query gives you an integer A_i not less than 2 and a positive integer B_i, so perform the following two steps in order.

  1. Remove from S all elements that are multiples of A_i.
  2. Print the B_i-th smallest element of S. It can be shown that under the given constraints, S contains at least B_i elements at this point.

Constraints

  • 1\le Q\le 10^5
  • 2\le A_i\le 10^9
  • 1\le B_i\le 10^5
  • All input values are integers.

Input

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

Q
A_1 B_1
\vdots
A_Q B_Q

Output

Print Q lines. The i-th line should contain the B_i-th smallest element of S after removing all multiples of A_i from S.

Sample Input 1

5
5 10
6 1
6 10
9 10
123456789 111

Sample Output 1

12
1
14
16
178

When the elements of S are listed in ascending order, the beginning of the list evolves as follows.

  • Initially, S=\lbrace 1,2,3,4,5,6,7,8,9,10,\ldots\rbrace.
  • The first query removes multiples of 5, resulting in S=\lbrace1,2,3,4,6,7,8,9,11,12,\ldots\rbrace.
  • The second query removes multiples of 6, resulting in S=\lbrace1,2,3,4,7,8,9,11,13,14,\ldots\rbrace.
  • The third query removes multiples of 6, resulting in S=\lbrace1,2,3,4,7,8,9,11,13,14,\ldots\rbrace.
  • The fourth query removes multiples of 9, resulting in S=\lbrace1,2,3,4,7,8,11,13,14,16,\ldots\rbrace.
  • The fifth query removes multiples of 123456789, resulting in S=\lbrace1,2,3,4,7,8,11,13,14,16,\ldots\rbrace.