問題文

あなたは予選・本選の二部からなるプログラミングコンテストの開催を計画しています。 そのために、何人を本選に参加させるかを決めなければなりません。

本選参加者数は次の 2 つの条件を満たす必要があります。

• 会場の大きさの都合上、参加者数は A 以下でなければならない。
• 懇親会で B 人がけのテーブルに座ってもらうため、参加者数は B の倍数でなければならない。

あなたはできるだけ多くの人に本選に参加してもらいたいと考えています。 上の 2 条件を満たす本選参加者数であって最大のものを求めてください。

制約

• 1 \leq B \leq A \leq 100

入力例 1

79
6

出力例 1

78

78 は A = 79 以下であるため 1 つ目の条件を満たします。 また、B = 6 の倍数であるため 2 つ目の条件も満たします。 この値が 2 つの条件を満たす最大の値であることもわかります。

入力例 2

100
100

出力例 2

100

入力例 3

43
5

出力例 3

40

入力例 4

56
1

出力例 4

56

問題文

あなたは洋菓子店を経営しています。 本日はショートケーキを A 個、チーズケーキを B 個用意しました。

本日はこの洋菓子店を N 人の客が訪れることがわかっています。 また、それぞれの客のふるまいは、文字 S、C、E からなる長さ N の文字列 X を用いて以下のように表されます。

• X の i 文字目が S の場合、i 番目に来る客はショートケーキを 1 個買う。ただし、到着した時点でショートケーキがすでに売り切れている場合は何も買わない。
• X の i 文字目が C の場合、i 番目に来る客はチーズケーキを 1 個買う。ただし、到着した時点でチーズケーキがすでに売り切れている場合は何も買わない。
• X の i 文字目が E の場合、i 番目に来る客はショートケーキとチーズケーキのうち到着した時点で多く残っている方を 1 個買う。 ただし、両方がすでに売り切れている場合は何も買わない。また、両方が 1 以上の同じ数ずつ残っている場合はショートケーキを 1 個買う。

すべての客が帰ったあと、ショートケーキおよびチーズケーキはそれぞれいくつ残っているでしょうか。

制約

• 0 \leq A, B \leq 10^5
• 1 \leq N \leq 10^5
• |X| = N
• X の各文字は S、C、E のいずれかである。

入力例 1

3 2 3
SEC

出力例 1

1
1

はじめの 2 人の客はショートケーキを、最後の客はチーズケーキを買います。

入力例 2

2 4 6
SSSEEE

出力例 2

0
1

3 人目の客はケーキを買うことができません。

入力例 3

0 3 6
SEECEE

出力例 3

0
0

入力例 4

100 99 9
SSSEEECCC

出力例 4

96
94

問題文

N 個の都市があり、1, 2, ..., N の番号がついています。 これらの都市はこの順に一直線上に並んでいます。 各 i (1 \leq i \leq N) について、都市 i の座標は X_i です。

高橋くんは都市 i と都市 j の間の移動手段を以下のように選びます。

• 都市 i と都市 j の距離 |X_i - X_j| が D 以下であれば、徒歩で移動する。
• そうでない場合、電車で移動する。

3 つの都市 (の番号) の組 (i, j, k) であって、以下の条件を満たすものの個数を求めてください。

• i < j < k
• 高橋くんは都市 i と都市 j の間、および都市 j と都市 k の間を徒歩で移動する。
• 高橋くんは都市 i と都市 k の間を電車で移動する。

制約

• 3 \leq N \leq 10^5
• 0 \leq X_i \leq 10^9 (1 \leq i \leq N)
• X_i < X_{i + 1} (1 \leq i < N)
• 0 \leq D \leq 10^9

入力例 1

5 7
11 13 17 19 23

出力例 1

5

条件を満たす (i, j, k) の組は (1, 2, 4), (1, 3, 4), (1, 3, 5), (2, 3, 5), (2, 4, 5) の 5 個あります。

入力例 2

4 10
0 3 6 10

出力例 2

0

入力例 3

6 36
0 5 32 48 69 71

出力例 3

4

入力例 4

6 405885562
133510576 158828561 245133494 461153833 840383806 867039395

出力例 4

6

問題文

H 行 W 列のマス目が書かれた紙があります。 このマス目の上から i 行目、左から j 列目のマス (1 \leq i \leq H, 1 \leq j \leq W) をマス (i, j) と書きます。

このマス目の N 行 M 列ぶんと同じ大きさのハンコがあります。 このハンコの印影は N 個の長さ M の文字列 A_1, A_2, ..., A_N によって表されます。 ハンコの左上をマス (s, t) (1 \leq s \leq H - N + 1, 1 \leq t \leq W - M + 1) の左上に 合わせてハンコを押すと、ハンコに覆われた各マス (u, v) (s \leq u \leq s + N - 1, t \leq v \leq t + M - 1) の色は以下のように変化します。

• 文字列 A_i の j 文字目が # であるとき、マス (s + i - 1, t + j - 1) の色は黒に変化する。
• 文字列 A_i の j 文字目が . であるとき、マス (s + i - 1, t + j - 1) の色は変化しない。

はじめ、すべてのマスの色は白色です。 1 \leq s \leq H - N + 1, 1 \leq t \leq W - M + 1 を満たす各 s, t について、 ハンコの左上をマス (s, t) の左上に合わせてハンコを押しました。

色が黒に変化したマスの個数を求めてください。

制約

• 1 \leq H, W \leq 10^9
• 1 \leq N, M \leq 1000
• N \leq H
• M \leq W
• |A_i| = M (1 \leq i \leq N)
• 各 i について、A_i の各文字は # と . のいずれかである

入力例 1

3 4
2 3
..#
##.

出力例 1

9

ハンコの左上をマス (1, 1), (1, 2), (2, 1), (2, 2) の 4 箇所に合わせて押すことになります。 ハンコをこの順に押していった場合、各マスの色は下の図のように変化します。

すべての位置にハンコを押し終わったとき、色が黒に変化しているマスは 9 個あります。

入力例 2

5 5
4 4
####
#..#
#..#
####

出力例 2

24

真ん中以外のマスが黒くなります。

入力例 3

10 12
1 1
.

出力例 3

0

入力例 4

20 20
5 5
##.##
.##.#
..##.
...##
....#

出力例 4

390

入力例 5

1000000000 1000000000
5 4
.#..
....
..#.
.#..
....

出力例 5

999999996999999999

問題文

AtCoder 国の 1 年は Y 週間からなり、1 週間は W 日間からなります。 すなわち、1 年は Y \times W 日間からなります。 また、曜日には順に 1, 2, ..., W の番号がついています。 すなわち、各 i (1 \leq i < W) に対して曜日 i の日の翌日は曜日 i + 1 で、 曜日 W の日の翌日は曜日 1 です。

AtCoder 国の祝日は以下のように定められています。

• 各 i (1 \leq i \leq N) に対して、一年のうち A_i 日目は祝日である。
• 各 j (1 \leq j \leq M) に対して、一年のうち B_j 回目の曜日 C_j の日は祝日である。
• 一年のうち x 日目および y 日目が祝日であり、1 \leq y - x - 1 \leq D が成り立つとき、 一年のうち x + 1, x + 2, ..., y - 1 日目はすべて祝日である。
• 上記で祝日とならなかった日はすべて祝日ではない。

AtCoder 国の一年の最初の日が曜日 d であった場合の一年間の祝日の日数を各 d = 1, 2, ..., W に対して求めてください。

制約

• 1 \leq Y \leq 10^9
• 1 \leq W \leq 10^5
• 0 \leq N \leq 50
• 0 \leq M \leq 10^5
• 0 \leq D \leq Y \times W
• 1 \leq A_i \leq Y \times W (1 \leq i \leq N)
• i \neq j のとき、A_i \neq A_j
• 1 \leq B_i \leq Y (1 \leq i \leq M)
• 1 \leq C_i \leq W (1 \leq i \leq M)
• i \neq j のとき、B_i \neq B_j または C_i \neq C_j

部分点

• N = 0 を満たすデータセットに正答すると、600 点が与えられる。

入力例 1

3 4
0 3 1
1 2
2 4
3 3

出力例 1

3
3
4
4

たとえば、一年の最初の日の曜日が 3 であった場合、一年の 4, 5, 6, 9 日目が祝日となります。

入力例 2

100 5
0 2 496
100 5
1 1

出力例 2

2
495
495
495
495

入力例 3

52 7
12 4 1
1
42
80
119
123
124
125
126
266
307
327
357
2 2
29 2
38 2
41 2

出力例 3

16
16
15
16
17
16
16

入力例 4

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

出力例 4

7
9
11
9
9
10
8
8
7
8