問題文

英小文字のみからなる文字列 S が与えられます。

あなたは以下の操作を好きな回数行うことができます。

• S から文字を 1 個選んで取り除き、その文字を S の（両端を含め）好きな位置に挿入する。

同じ文字が隣り合わないようにできるかを判定し、可能な場合は必要な操作回数の最小値を求めてください。

T 個のテストケースが与えられるので、それぞれについて答えを求めてください。

制約

• 1 \le T \le 10^5
• 2 \le |S| \le 10^6
• S は英小文字からなる
• 全てのテストケースにおける |S| の総和は 10^6 以下
• T は整数

入力例 1

3
kiiiww
aa
oooxovvvxiiiq

出力例 1

2
-1
3

1 つ目のテストケースでは、以下のように操作をすると 2 回の操作で同じ文字が隣り合わないようにできます。

• 3 文字目の i を取り除き、2 個の w の間に挿入する。S は kiiwiw となる。
• 2 文字目の i を取り除き、末尾に挿入する。S は kiwiwi となる。

2 つ目のテストケースでは、どのように操作しても 2 個の a が隣り合います。

問題文

N 頂点 M 辺の連結な単純無向二部グラフ G があります。 頂点には 1 から N までの番号が付いています。 i 本目の辺は頂点 U_i と頂点 V_i を結んでいます。

はじめ、各頂点は黒または白で塗られており、頂点 1 は黒で塗られています。 また、各辺の両端の色は異なります。この条件から全ての頂点の色は一意に定まります。

以下の操作を何回でも行うことができます。

• 頂点 A_1,A_2,\ldots,A_K のうち 1 つを選び v とする。G において v と同じ色の頂点からなる誘導部分グラフで、v と同じ連結成分に属する全ての頂点について、白黒を反転する。

全ての頂点を同じ色にするために必要な操作回数の最小値を求めてください。

T 個のテストケースが与えられるので、それぞれについて答えを求めてください。

制約

• 1 \le T \le 10^4
• 2 \le N \le 2 \times 10^5
• N-1 \le M \le 2 \times 10^5
• 1 \le K \le \min(N, 10)
• 1 \le A_1 < A_2 < \ldots < A_K \le N
• 1 \le U_i < V_i \le N
• G は連結な単純無向二部グラフ
• 全てのテストケースにおける N の総和は 2 \times 10^5 以下
• 全てのテストケースにおける M の総和は 2 \times 10^5 以下
• 入力される値は全て整数

入力例 1

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

出力例 1

2
1
3

1 つ目のテストケースでは、はじめ、頂点 1,4 が黒、頂点 2,3,5 が白で塗られています。 以下の手順で操作を行うと、2 回の操作で全ての頂点を同じ色にすることができます。

• 頂点 3 を選ぶ。頂点 3 の色が黒に変わる。
• 頂点 1 を選ぶ。頂点 1,3,4 の色が白に変わる。

問題文

高橋王国には金貨鳥という、コインを産む鳥がいます。

現在は 0 日目の夜であり、高橋君は金貨鳥を 1 羽飼っており、コインを持っていません。

毎日、朝になると、飼っている金貨鳥がそれぞれコインを 1 枚ずつ産みます。 また、夜には、コインを C 枚支払って金貨鳥を 1 羽購入することを、コインが足りる限り好きな回数行うことができます。

高橋君が金貨鳥の購入を適切に行うことで、所持コインを X 枚以上にできる最も早い日は何日目か求めてください。

制約

• 1 \le C \le 10^6
• 1 \le X \le 10^{18}
• 入力される値は全て整数

入力例 1

1 5

出力例 1

4

以下のように金貨鳥を購入すると、4 日目にコインが 5 枚以上になります。

• 1 日目：朝、金貨鳥が合計 1 枚のコインを産み、コインの所持枚数は 1 枚となる。夜、コインを 1 枚支払って金貨鳥を 1 羽購入する。
• 2 日目：朝、金貨鳥が合計 2 枚のコインを産み、コインの所持枚数は 2 枚となる。夜、金貨鳥を購入しない。
• 3 日目：朝、金貨鳥が合計 2 枚のコインを産み、コインの所持枚数は 4 枚となる。夜、コインを 3 枚支払って金貨鳥を 3 羽購入する。
• 4 日目：朝、金貨鳥が合計 5 枚のコインを産み、コインの所持枚数は 6 枚となる。

入力例 2

8 23

出力例 2

20

入力例 3

90 99462082157

出力例 3

2026

問題文

長さ N の整数列 a=(a_1,a_2,\ldots,a_N) があります。 はじめ、a=(0,0,\ldots,0) です。

Q 回の更新を順に行います。 i 回目の更新では、全ての j=1,2,\ldots,N について a_j に X_{i,j} を加えます。

各更新について、N 個の加算を全て行った直後に、以下の帳消し操作を 1 回行うかどうかを選べます。

• 全ての j=1,2,\ldots,N について、a_j を \max(a_j,0) に置き換える。

整数 M が与えられます。 各 k=1,2,\ldots,M について、帳消し操作をちょうど k 回行うとき、最終的な \sum_{i=1}^N a_i としてあり得る最大値を求めてください。

制約

• 1 \le N \le 10
• 1 \le Q \le 10^4
• 1 \le M \le \min(Q,1000)
• -10^9 \le X_{i,j} \le 10^9
• 入力される値は全て整数

入力例 1

3 4 2
-2 5 -1
-3 -3 -6
5 2 -1
-7 4 5

出力例 1

10 13

k=1 のとき、2 回目の更新の直後に帳消し操作を行います。このとき、a は以下のように変化します。

• 1 回目の更新後：a=(-2,5,-1) となる
• 2 回目の更新後：a=(-5,2,-7) となり、ここで帳消し操作を行い a=(0,2,0) となる
• 3 回目の更新後：a=(5,4,-1) となる
• 4 回目の更新後：a=(-2,8,4) となる

最終的な \sum_{i=1}^N a_i は 10 になります。

k=2 のときは、3,4 回目の更新の直後に帳消し操作を行うのが最適です。

入力例 2

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

出力例 2

25 29 33

問題文

:、| のみからなる文字列 S が与えられます。S に含まれる | の個数を m とします。

k = 0,1,\ldots,m について、S に含まれる | のうち左から k 個を ) に、残りの m-k 個を ( に置き換えた文字列を s_k とします。

t = s_0,s_1, \ldots, s_m について、以下の問題を解いてください。

以下のいずれかの操作を行うことを、いずれの操作も行えなくなるまで繰り返します。

• t の部分文字列 ): を 1 つ選び、:) に置き換える。
• t の部分文字列 :( を 1 つ選び、(: に置き換える。

このとき、あり得る操作列の個数を 998244353 で割った余りを求めてください。

ただし、各操作後に得られる文字列の列によって操作列を区別するものとします。

制約

• 2 \le |S| \le 5000
• S は :、| のみからなる
• S は | を 1 つ以上含む

入力例 1

:|:|:|:

出力例 1

16 4 4 16

例えば s_1 は :):(:(: であり、t=s_1 のときあり得る操作列は以下の 4 個です。

• :):(:(: \to ::)(:(: \to ::)((::
• :):(:(: \to :)(::(: \to :)(:(:: \to :)((:::
• :):(:(: \to :):((:: \to ::)((::
• :):(:(: \to :):((:: \to :)(:(:: \to :)((:::

入力例 2

:|::||:::|:|::::||::||:::|:|::||::::|:::|::||::||:

出力例 2

322208215 55473788 581480459 515433014 601107939 931599079 393720955 990743753 800079371 548259390 252803059 949070759 695561170 19955262 245180926 507077502 399421430 355488765 306794074 223437030

問題文

H 行 W 列のマス目があります。 i 行目 j 列目のマスを (i,j) と表します。

H 個の長さ W の文字列 S_1,S_2,\ldots,S_H が与えられます。 S_i の j 文字目が o であるようなマス (i,j) のうち相異なる 4 マスを選び、それぞれに避難所を 1 つ設置します。

避難所の配置が良い配置であるとは、全てのマスについて、そのマスからのマンハッタン距離が最小となる避難所がちょうど 1 つ存在することをいいます。

良い配置の個数を求めてください。 ただし、避難所同士に区別はありません。

制約

• 1 \le H,W \le 500
• S_i は o, . のみからなる長さ W の文字列
• H,W は整数

入力例 1

2 6
o.o..o
..o..o

出力例 1

1

避難所を設置できるマスは 5 マスあります。 このうち、マス (1,1) 以外の 4 マスに避難所を設置するような配置が唯一の良い配置となります。

例えば、マス (1,3) 以外の 4 マスに避難所を設置した場合は、マス (1,4) から最も近い避難所がマス (2,3) とマス (1,6) の 2 箇所であるため、これは良い配置ではありません。

入力例 2

1 1
.

出力例 2

0

入力例 3

17 15
.oo.ooo.ooo....
..o.o...o......
..o.ooo.o......
o.o...o.o......
ooo.ooo.ooo....
...............
ooo.ooo.ooo.ooo
..o.o.o...o.o..
ooo.o.o.ooo.ooo
o...o.o.o...o.o
ooo.ooo.ooo.ooo
...............
ooo.o.........o
o.............o
ooo.o.oo...oo.o
o...o.o.o.o.o.o
o...o.o.o..oo.o

出力例 3

50099

問題文

N 個のグラスと、水の入った N 本のボトルがあります。 グラスとボトルには、それぞれ 1 から N までの番号が付けられています。 グラス i の容量は C_i であり、ボトル i に入っている水の量は W_i です。

(1,2,\ldots,N) の順列 P=(P_1,P_2,\ldots,P_N) を選びます。 そして、各 i=1,2,\ldots,N について、ボトル i に入っている水を全てグラス P_i に注ぎます。 このとき、溢れる水の量は \max(0,W_i-C_{P_i}) です。

溢れる水の量の総和としてありうる最大値を求めてください。 さらに、最大値を達成する順列 P の個数を 998244353 で割った余りを求めてください。

T 個のテストケースが与えられるので、それぞれについて答えを求めてください。

制約

• 1 \le T \le 10^5
• 1 \le N \le 2 \times 10^5
• 1 \le C_i \le 10^9
• 1 \le W_i \le 10^9
• 全てのテストケースにおける N の総和は 2 \times 10^5 以下
• 入力される値は全て整数

入力例 1

4
3
1 4 10
2 5 8
1
1
1
7
1 1 1 1 1000000000 1000000000 1000000000
999999999 999999999 999999999 999999999 999999999 999999999 999999999
25
29 59 17 47 73 41 88 59 17 47 29 73 59 41 47 88 17 59 29 47 73 41 88 17 47
88 17 88 59 47 59 47 29 59 73 73 88 47 17 17 17 47 41 41 41 47 59 29 73 29

出力例 1

8 2
0 1
3999999992 5040
441 225812543

1 つ目のテストケースについて、順列 (3,2,1) と (3,1,2) が最大値を達成します。 どちらの順列でも、溢れる水の量の総和は 8 です。

2 つ目のテストケースについて、水は溢れません。