問題文

"OSAKA" という文字列に対し、'O' を 'A' に、'A' を 'O' に変換する操作を行うと "ASOKO" になります。

英大文字のみから成る 5 文字の文字列 S が与えられます。S に対し、'O' を 'A' に、'A' を 'O' に変換してできる文字列を出力するプログラムを作成してください。

制約

• S は 5 文字の文字列です。
• S は英大文字のみから成ります。

入力例 1

OSAKA

出力例 1

ASOKO

"OSAKA" は "ASOKO" になります。

入力例 2

TOKYO

出力例 2

TAKYA

入力例 3

KKKKK

出力例 3

KKKKK

文字列がまったく変化しないこともあります。

入力例 4

GRAPH

出力例 4

GROPH

入力例 5

CPSCO

出力例 5

CPSCA

問題文

競プロ練習会イベントでは、コンテスト中に、問題を解いた参加者たちに風船が配布されます。今回の運営チームの中には未来透視のできる超能力者がいて、合計で M 個の風船が必要であることがわかりました。

現在、N 色の風船が手元にあり、色 i (=1, 2, \ldots, N) の風船が a_i 個あります。この中から合計で M 個の風船を選びます。選んだ風船に登場する色の種類がなるべく少なくなるようにしたいです。色の種類数の最小値を求めるプログラムを作成してください。

制約

• 1 \le N \le 10^5
• 1 \le M \le 10^9
• 1 \le a_i \le 10^9
• a_1 + a_2 + \dots + a_N \ge M
• 与えられる入力はすべて整数です。

入力例 1

5 17
4 5 7 9 2

出力例 1

3

例えば色 1 の風船を 4 個、色 3 の風船を 6 個、色 4 の風船を 7 個使えば 3 種類で 17 個の風船を用意することができます。

入力例 2

2 9
3 6

出力例 2

2

ちょうどすべての風船を使うことができます。

入力例 3

10 9
1 2 3 4 5 6 7 8 9 10

出力例 3

1

入力例 4

10 129
12 42 13 25 32 19 14 9 21 12

出力例 4

5

問題文

高橋君は競プロ合宿を開催することにしました。高橋君が会場に到達した時点の時刻を 0 とします。高橋君は時刻 0 の時点では控室にいて、その後参加者たちの受付を開始します。参加者は N 人いて、i (=1, 2, \ldots, N) 人目の参加者は、時刻 s_i に受付を開始して時刻 t_i に受付を終えます。

高橋君は、いずれかの参加者が受付中の時間帯は常に受付にいて、どの参加者も受付中ではない時間帯は常に控室にいるようにします。また複数人の参加者の受付を並列に処理できるものとします。より正確にいえば、i (=1, 2, \ldots, N) 人目の参加者は、他の参加者の受付状態によらず時刻 s_i に到着して時刻 t_i に受付を終えます。

高橋君が会場に到着した時から最後の参加者が到着するまでの間に、高橋君が控室から受付へと移動する回数が何回あったかを求めるプログラムを作成してください。ただし、高橋君が受付から控室へ移動したり、控室から受付へ移動したりするのにかかる時間は無視できるものとしますが、ある参加者の受付を時刻 t に終了して他の参加者の受付が時刻 t に開始する場合には、時刻 t の時点で控室に戻ることはないものとします。

制約

• 1 \le N \le 2 \times 10^5
• 1 \le s_i < t_i \le 10^6
• 与えられる入力はすべて整数です。

入力例 1

3
2 6
4 7
8 12

出力例 1

2

時刻 2 から時刻 7 までは 1 番目と 2 番目の参加者の受付を行います。時刻 7 から時刻 8 までの間は受付中の参加者がいないので控室に戻ります。その後、時刻 8 から 3 番目の参加者の受付を開始するので再び受付に行きます。

入力例 2

2
3 5
5 7

出力例 2

1

1 人目の参加者の受付を終えた時刻 5 時点で次の 2 人目の参加者が受付開始となるため、控室に戻る時間はないことに注意してください。

入力例 3

5
8 11
6 12
2 7
17 21
12 15

出力例 3

2

問題文

長さ N のマス目があり、最初はすべてのマスが白く塗られています。各マスは左から順に 1, 2, \ldots, N の番号が付けられています。

このマス目内の連続する 3 マスに対し、左から順に赤色・緑色・青色に上塗りするスタンプを次々と押して行きます。より正確に言えば、整数 i ( = 1, 2, \ldots, N-2) を一つ選んで、マス i を赤色に、マス i+1 を緑色に、マス i+2 を青色に塗る操作を行います。このときすでにスタンプが押されているマスの上にもスタンプを押すことができて、スタンプを押された各マスの色は新たなスタンプの色に上塗りされます。青木さんは白色マスがなくなるまでこの操作を行いました。白色マスがなくなっても操作を続けることができて、好きなタイミングで操作を終了することができます。

操作終了時に好みの色合いを実現することができるかどうかを判定するプログラムを書いてください。好みの色合いは長さ N の文字列 S で表され、i = 1, 2, \ldots, N に対して、S_i = 'R' のとき i マス目を赤色にしたいことを表し、S_i = 'G' のとき i マス目を緑色にしたいことを表し、S_i = 'B' のとき i マス目を青色にしたいことを表します。

制約

• 3 \le N \le 10^5
• |S| = N
• S は 'R', 'G', 'B' からなる文字列です。

入力例 1

4
RGBB

出力例 1

Yes

まず後ろ 3 マスにスタンプを押し、次に前 3 マスにスタンプを押すことで、"RGBB" となります。

入力例 2

6
RRGGBB

出力例 2

No

入力例 3

10
RGBBBGRRGB

出力例 3

Yes

問題文

長さ N の 0 以上の整数からなる数列 A_1, A_2, \ldots, A_N が与えられます。各 k = 1, 2, \ldots, N に対して

• X = A_1 {\rm xor} A_2 {\rm xor} \ldots {\rm xor} A_k として、
• (A_1 {\rm xor} X) + (A_2 {\rm xor} X) + \ldots + (A_k {\rm xor} X) の値を出力する

ようなプログラムを作ってください。X の定義が k によって変化することに注意してください。

なお、整数 c_1, c_2, \ldots, c_m の {\rm xor} は以下のように定義されます:

• 求める {\rm xor} の値を X とおいて、
• X を二進数表記したときの 2^k (k は 0 以上の整数) の位の値は、c_1, c_2, \ldots, c_m のうち、二進数表記したときの 2^k の位の値が 1 となるものが奇数個ならば 1、偶数個ならば 0 となる。

制約

• 1 \le N \le 3 \times 10^5
• 0 \le A_i < 2^{30}
• 与えられる入力はすべて整数です。

入力例 1

3
7 5 3

出力例 1

0
12
12

• k = 1 のとき、X = 7 なので、A_1 {\rm xor} X = 0 となります。
• k = 2 のとき、X = 7 {\rm xor} 5 = 2 なので、A_1 {\rm xor} X = 5、A_{2} {\rm xor} X = 7 より、合計値は 12 になります。
• k = 3 のとき、X = 7 {\rm xor} 5 {\rm xor} 3 = 1 なので、A_1 {\rm xor} X = 6、A_{2} {\rm xor} X = 4、A_{3} {\rm xor} X = 2 より、合計値は 12 になります。

入力例 2

7
12 42 61 31 34 53 17

出力例 2

0
54
110
138
142
233
252

問題文

正の整数 N が与えられます。

1, 2, \ldots, N を並び替えてできる数列 P_1, P_2, \ldots, P_N は N! 通りありますが、そのうち以下の条件を満たすものが何通りあるかを、10^{9} + 7 で割ったあまりを求めるプログラムを作成してください。

• P_i > i を満たすような i (= 1, 2, \dots, N) がちょうど A 個であり、
• P_i < i を満たすような i (= 1, 2, \dots, N) がちょうど B 個であり、
• P_i = i を満たすような i (= 1, 2, \dots, N) がちょうど N - A - B 個です。

制約

• 1 \le N \le 300
• 0 \le A, B \le N
• A + B \le N
• 与えられる入力はすべて整数です。

部分点

この問題には部分点が設定されています。

• N \leq 15 を満たす入力に正解すると、300 点が与えられます。

入力例 1

3 1 1

出力例 1

3

(1, 3, 2), (3, 2, 1), (2, 1, 3) の 3 個が条件を満たします。

入力例 2

6 2 3

出力例 2

126

入力例 3

10 5 0

出力例 3

0

条件を満たす順列が存在しないこともあります。

入力例 4

256 155 51

出力例 4

125746759

問題文

アイドルグループ ATC48 にて、N 人のアイドルたちに人気投票が行われ、各アイドルに a_1, a_2, \ldots, a_N の投票が集まりました。

各アイドルには得票数に応じた賞金を渡します。事前に X 円 (X は正の整数) の賞金が用意されていて、なるべくアイドル i には a_i に比例する賞金を渡したいです。しかし、A = a_1 + a_2 + \dots + a_N として X \times \frac{a_i}{A} が整数値になるとは限りません。そこで各アイドルに渡す賞金額 x_1, x_2, \ldots, x_N を以下の条件を満たす 0 以上の整数値となるように決めることにしました:

• x_1 + x_2 + \ldots + x_N = X
• |\frac{x_1}{a_1} - \frac{X}{A}| + |\frac{x_2}{a_2} - \frac{X}{A}| + \ldots + |\frac{x_N}{a_N} - \frac{X}{A}| が最小値をとる。

各アイドルの賞金額 x_1, x_2, \ldots, x_N を出力するプログラムを作ってください。複数通り考えられる場合には、(x_1, x_2, \ldots, x_N) の辞書順が最小のものを出力してください。

制約

• 1 \le N \le 10^5
• 1 \le X \le 10^9
• 1 \le a_i \le 100
• 与えられる入力はすべて整数です。

入力例 1

4 100
3 4 5 8

出力例 1

15
20
25
40

この場合はちょうど比例配分することができます。

入力例 2

2 100
3 4

出力例 2

43
57

このとき |\frac{43}{3} - \frac{100}{7}| + |\frac{57}{4} - \frac{100}{7}| = 0.083333… となります。

入力例 3

6 1000
7 6 1 3 4 1

出力例 3

318
273
45
136
182
46

複数通り考えられる場合は、辞書順最小のものを出力します。