問題文

N 個の長方形があり、長方形 i の幅と高さはそれぞれ A_i, B_i です。

各長方形の面積を求めてください。

制約

入力は以下の条件を満たす。

• 1 \leq N \leq 2 \times 10^5
• 1 \leq A_i,B_i \leq 10^9
• 入力される値は全て整数

入力例 1

3
3 4
1000000000 1
111111111 111111111

出力例 1

12
1000000000
12345678987654321

問題文

N 個の以下の問題に答えてください。

• 整数 A_i を整数 B_i で割った余りを求めよ。

制約

入力は以下の条件を満たす。

• 1 \leq N \leq 2 \times 10^5
• 1 \leq A_i,B_i \leq 10^9
• 入力される値は全て整数

入力例 1

3
10 3
1000000000 1
11 92

出力例 1

1
0
11

問題文

整数のペアが N 組あります。i 番目の整数のペアは (A_i, B_i) です。

各ペアについて 2 つの整数の和を求め、それらのうちの最大値を答えてください。

制約

入力は以下の条件を満たす。

• 1 \leq N \leq 2 \times 10^5
• 1 \leq A_i,B_i \leq 10^9
• 入力される値は全て整数

入力例 1

3
4 4
3 7
8 1

出力例 1

10

各ペアの 2 つの整数の和は以下の通りです。

• 1 番目のペア： 4+4 = 8
• 2 番目のペア： 3+7 = 10
• 3 番目のペア： 8+1 = 9

このうちの最大値は 10 なので、10 を出力します。

入力例 2

2
12345678 111111111
103050709 20406080

出力例 2

123456789

和はいずれペアでも 123456789 になります。

問題文

整数のペアが N 組あります。i 番目の整数のペアは (A_i, B_i) です。

すぬけ君は各ペアからちょうど 1 つずつ整数を選ぼうとしています。選ばれた N 個の整数の和として考えられる最大値はいくらでしょうか？

制約

入力は以下の条件を満たす。

• 1 \leq N \leq 2 \times 10^5
• 1 \leq A_i,B_i \leq 10^9
• 入力される値は全て整数

入力例 1

2
20 19
1 100

出力例 1

120

1 番目のペアで 20 を選び、2 番目のペアで 100 を選ぶと和が 20+100 = 120 となり最大となります。

入力例 2

3
123456789 987654321
999999999 999999999
1000000000 888888888

出力例 2

2987654320

問題文

自分の魅力に気づいたカツサンドくんは、カツサンドのお店を開くことにしました。

お店は N 日間営業し、i 日目には A_i 枚のパンと B_i 枚のカツを入荷します。 パンを 2 枚、カツを 1 枚使うことで 1 個のカツサンドを作ることができます。

カツサンドくんが N 日間で作ることのできるカツサンドの個数の最大値を求めてください。 なお、余った材料はその日の夜に廃棄しなければならず、別の日に使うことはできません。

制約

入力は以下の条件を満たす。

• 1 \leq N \leq 2 \times 10^5
• 1 \leq A_i,B_i \leq 10^9
• 入力される値は全て整数

入力例 1

3
10 5
100 1
1 100

出力例 1

6

• 1 日目はぴったり 5 個のカツサンドを作ることができます。
• 2 日目はパンを 2 枚、カツを 1 枚使うことで 1 個のカツサンドを作ることができます。たくさんのパンが余ってしまいました。
• 3 日目はパンが 1 枚しかないため一つもカツサンドを作ることができません。今度はたくさんのカツが余ってしまいました。

合計 5+1+0 = 6 個のカツサンドを作ることができます。

入力例 2

7
1000000000 1000000000
1000000000 1000000000
1000000000 1000000000
1000000000 1000000000
1000000000 1000000000
1000000000 1000000000
1000000000 1000000000

出力例 2

3500000000

問題文

N 枚のコインがあります。i 枚目のコインの片方の面には整数 A_i、もう片方の面には整数 B_i が書かれています。

書かれている整数の組が同じであるコインを区別しないとき、コインは全部で何種類あるでしょうか？

制約

入力は以下の条件を満たす。

• 1 \leq N \leq 2 \times 10^5
• 1 \leq A_i,B_i \leq 10^9
• 入力される値は全て整数

入力例 1

5
1 2
2 1
3 4
5 5
3 4

出力例 1

3

書かれた整数の組が (1,2),\ (3,4),\ (5,5) である 3 種類のコインがあります。

1 枚目のコインと 2 枚目のコインはひっくり返すと同じ種類のコインであることに注意してください。

問題文

N 個の以下の問題を解いてください。

• 整数 A_i と整数 B_i の最大公約数を求めよ。

制約

入力は以下の条件を満たす。

• 1 \leq N \leq 2 \times 10^5
• 1 \leq A_i,B_i \leq 10^9
• 入力される値は全て整数

入力例 1

4
6 15
20 19
240 240
555555555 999999999

出力例 1

3
1
240
111111111

問題文

N 個の以下の問題に答えてください。

• 整数 A_i を割った余りと整数 B_i を割った余りが等しくなるような正整数のうち最大のものを求めよ。

制約

入力は以下の条件を満たす。

• 1 \leq N \leq 2 \times 10^5
• 1 \leq A_i,B_i \leq 10^9
• 入力される値は全て整数

入力例 1

2
3 5
1 1

出力例 1

2
-1

• 3 と 5 はいずれも奇数であり、2 で割った余りはいずれも 1 となります。なお、1 で割った余りも等しくなりますが、2 の方が大きいため 2 を出力します。また、2 より大きい数で割った場合は余りが等しくなることはありません。
• 1 と 1 はどんな整数で割っても余りが等しくなるため、答えが限りなく大きくなります。したがって、-1 を出力します。

問題文

カツサンドくんはオムライスが好きです。

他にも明太子や寿司、クリームブリュレやテンダーロインステーキなどが好きです。

今、カツサンドくんの目の前には N 種類の好きな食べ物が並んでいます。 カツサンドくんはこの中から最強の食べ物を決めることにしました。

カツサンドくんの独自の調査により、食べ物 i の体力が A_i、攻撃力が B_i であることが分かりました。 食べ物 i と食べ物 j が戦った場合、以下の手順で勝敗が決まります。（入出力例も参考にしてください。）

1. 各食べ物が互いを攻撃し合う。食べ物 i の体力が B_j だけ減少し、食べ物 j の体力が B_i だけ減少する。
2. 体力が 0 以下になった食べ物は戦闘不能になる。
3. いずれの食べ物も戦闘不能になっていない場合は手順 1. に戻る。
4. 両方が戦闘不能になった場合は引き分け、片方のみが戦闘不能になった場合はもう片方の勝利とする。

カツサンドくんは、他のどの食べ物と戦ったとしても勝利できるような食べ物を最強の食べ物とすることにしました。最強の食べ物がどの食べ物であるかを求めてください。

制約

入力は以下の条件を満たす。

• 1 \leq N \leq 2 \times 10^5
• 1 \leq A_i,B_i \leq 10^9
• 入力される値は全て整数

入力例 1

3
7 3
9 2
2 5

出力例 1

1

食べ物 1 は他のどちらの食べ物と戦っても勝利できるため、最強の食べ物です。

• 食べ物 1 と食べ物 2 が戦った場合、以下のようになります。
  1. 始め、2 つの食べ物の体力はそれぞれ 7, 9 である。
  2. 互いに攻撃を行い、それぞれの体力は 5, 6 となる。
  3. 互いに攻撃を行い、それぞれの体力は 3, 3 となる。
  4. 互いに攻撃を行い、それぞれの体力は 1, 0 となる。
  5. 食べ物 2 のみが戦闘不能となったため、食べ物 1 の勝利となる。
• 食べ物 1 と食べ物 3 が戦った場合、以下のようになります。
  1. 始め、2 つの食べ物の体力はそれぞれ 7, 2 である。
  2. 互いに攻撃を行い、それぞれの体力は 2, -1 となる。
  3. 食べ物 3 のみが戦闘不能となったため、食べ物 1 の勝利となる。

入力例 2

2
999999999 1000000000
1 999999999

出力例 2

-1

食べ物 1 と食べ物 2 が戦った場合、最初の攻撃の後両方の食べ物が戦闘不能になり、引き分けとなります。 このため、最強の食べ物は存在しません。

入力例 3

2
999999999 1
1000000000 1

出力例 3

2

入力例 4

3
100 17
171 10
91 19

出力例 4

-1

問題文

整数のペアが N 組あります。i 番目の整数のペアは (A_i, B_i) です。

すぬけ君は各ペアからちょうど 1 つずつ整数を選ぼうとしています。選ばれた N 個の整数の最大公約数として考えられる最大値はいくらでしょうか？

制約

入力は以下の条件を満たす。

• 1 \leq N \leq\ 5 \times 10^4
• 1 \leq A_i,B_i \leq 10^9
• 入力される値は全て整数

入力例 1

2
15 12
18 18

出力例 1

6

各ペアからそれぞれ 12, 18 を選ぶと最大公約数が 6 となり、これが最大です。

入力例 2

3
999999929 999999883
999999757 999999929
999999883 999999757

出力例 2

1

問題文

整数のペアが N 組あります。i 番目の整数のペアは (A_i, B_i) です。

すぬけ君は各ペアからちょうど 1 つずつ整数を選ぼうとしています。選ばれた N 個の整数の種類数として考えられる最大値はいくらでしょうか？

制約

入力は以下の条件を満たす。

• 1 \leq N \leq 2 \times 10^5
• 1 \leq A_i,B_i \leq 10^9
• 入力される値は全て整数

入力例 1

5
58 48
58 58
20 19
58 425
48 425

出力例 1

4

各ペアからそれぞれ 58,58,20,425,48 を選ぶと 4 種類の整数を選ぶことができます。5 種類以上の整数を選ぶことはできません。

入力例 2

3
1000000000 1000000000
1000000000 1000000000
1000000000 1000000000

出力例 2

1

問題文

N 個の長方形があり、長方形 i の幅と高さはそれぞれ A_i, B_i です。

すぬけ君はこれらの長方形の中からいくつかを選んで順番に重ねることで 1 つの模様を作ろうとしています。 このとき、j\ (2 \leq j) 番目に配置する長方形は以下の条件を満たすようにしなければなりません。

• j-1 番目に配置した長方形の内部に完全に含まれる。
• j-1 番目に配置した長方形と辺どうしが接してはならない。
• 各辺は j-1 番目に配置した長方形のいずれかの辺と平行になっていなければならない。

なお、長方形を配置する際は幅と高さを入れ替えても構いません。また、長方形を配置する順番は長方形の番号に関係なく自由に決めることができます。

すぬけ君は最大でいくつの長方形が重なった模様を作ることができるでしょうか？

制約

入力は以下の条件を満たす。

• 1 \leq N \leq 2 \times 10^5
• 1 \leq A_i,B_i \leq 10^9
• 入力される値は全て整数

入力例 1

4
3 4
1 5
5 5
3 1

出力例 1

3

長方形 3、長方形 1、長方形 4 をこの順で図のように配置すると 3 つの長方形を重ねることができます。 長方形の幅と高さを入れ替えても構わない点に注意してください。

入力例 2

3
1000000000 1000000000
1000000000 1000000000
1000000000 1

出力例 2

1

辺どうしが接してはいけない点に注意してください。