問題文

数直線上で生活している高橋君は、いま座標 S にいます。座標が L 以上 R 以下の区間は日当たりが良いです。

日に当たりたい高橋君は座標が L 以上 R 以下になるまで次のような移動を繰り返します。

• 現在の座標を X として、L \leq X \leq R のとき移動をやめる。X が L 未満のとき、X + 1 に移動する。X が R より大きいとき、X - 1 に移動する。

高橋君が最終的に移動をやめる座標を求めてください。

制約

• -100 \leq S \leq 100
• -100 \leq L \leq R \leq 100
• 入力は全て整数である

入力例 1

5 1 5

出力例 1

5

高橋君はいま座標 5 にいて、既に日に当たっているので 5 を出力してください。

入力例 2

2 7 10

出力例 2

7

高橋君はいま座標 2 にいて、日当たりが良い区間は 7 以上 10 以下なので、7 に到達するまで移動を繰り返します。

入力例 3

20 3 5

出力例 3

5

高橋君はいま座標 20 にいて、日当たりが良い区間は 3 以上 5 以下なので、5 に到達するまで移動を繰り返します。

問題文

赤か青で塗られた N 個のボールが入った袋があります。また、それぞれのボールには整数が書かれています。

i 個目のボールには整数 X_i が書かれており、色は C_i が R のとき赤、B のとき青です。

高橋君は、袋の中にボールが残っている間、次の手順を繰り返して袋からボールを取り出します。

• 袋の中に赤のボールがあるとき、残っている赤のボールのうち最小の整数が書かれたボールを袋から取り出す。そうでないとき、残っている青のボールのうち最小の整数が書かれたボールを袋から取り出す。

高橋君が各手順で取り出したボールに書かれていた整数を求めてください。

制約

• 1 \leq N \leq 100
• 1 \leq X_i \leq 10000
• C_i は R または B
• X_i \neq X_j (i \neq j)
• N, X_i は全て整数

入力例 1

4
10 B
6 R
2 R
4 B

出力例 1

2
6
4
10

袋の中に赤いボールがある間は赤のボールを取り出すので、取り出すボールの順番は (2, R)、(6, R)、(4, B)、(10, B) となります。

入力例 2

2
5 B
7 B

出力例 2

5
7

どちらかの色のボールしか存在しないこともあります。

問題文

積み木の山が 3 つ並んでおり、それぞれの山には a_1 \geq a_2 \geq a_3 個の積み木が積まれています。

全部で N = a_1 + a_2 + a_3 個の積み木がありますが、これらに 1 から N までの整数をちょうど 1 つずつ書き込みます。

ただし、次の条件を全て満たす必要があります。

• 左から i 個目の山の下から j 個目の積み木に書かれた整数を X_{i, j} で表す (1 \leq i \leq 3, 1 \leq j \leq a_i) とき、
  • X_{i, j} > X_{i, j-1} (1 \leq i \leq 3, 1 < j \leq a_i)
  • X_{i, j} > X_{i-1, j} (1 < i \leq 3, 1 \leq j \leq a_i)

この条件を満たす整数の書き込み方の個数を求めてください。

制約

• 3 \geq a_1 \geq a_2 \geq a_3 \geq 1
• 入力は全て整数である

入力例 1

1 1 1

出力例 1

1

左から 1, 2, 3 と書き込むしかありません。

入力例 2

2 1 1

出力例 2

3

以下の 3 通りの書き込み方が存在します。

入力例 3

2 2 1

出力例 3

5

問題文

長さ N の整数列 A_1, A_2, \cdots, A_N があります。

Q 個の 1 より大きい整数 S_1, S_2, \cdots, S_Q が与えられるので、i = 1, 2, \cdots, Q について次の問題で X = S_i とした場合の答えを求めてください。

• 初め整数 X がある。j = 1, 2, \cdots, N の順に、X を \gcd(X, A_j) で置き換えるという操作を行う。j 回目の操作の直後に X = 1 であるような j が存在する場合はそのような j の最小値を、存在しない場合は最終的な X の値を求めよ。

制約

• 1 \leq N, Q \leq 10^5
• 1 \leq A_i \leq 10^9
• 1 < S_i \leq 10^9
• 入力は全て整数である

注記

2 つの 0 より大きい整数 X, Y の最大公約数を \gcd(X, Y) で表します。

C++ では std::gcd が利用できます。

Python では fractions.gcd から math.gcd に変更されています。

入力例 1

4 3
6 12 6 9
4 6 3

出力例 1

4
3
3

• i = 1 のとき、X は初め 4 です。4 回の操作の後、それぞれ X = 2, 2, 2, 1 となり、4 回の操作の後初めて X = 1 となるので 4 を出力してください。

• i = 2 のとき、X は初め 6 です。4 回の操作の後、それぞれ X = 6, 6, 6, 3 となり、4 回の操作の後も X \neq 1 であるので、最終的な X の値である 3 を出力してください。

• i = 3 のとき、X は初め 3 です。4 回の操作の後、それぞれ X = 3, 3, 3, 3 となり、4 回の操作の後も X \neq 1 であるので、最終的な X の値である 3 を出力してください。

入力例 2

4 3
4 6 2 1
3 2 1000000000

出力例 2

1
4
4