問題文

正整数 N,K が与えられます。N 頂点のラベルなし木 T であって、T の 1 頂点を根とすることによって作られるラベルなし根付き木がちょうど K 通りあるようなものが存在するかどうか判定し、存在するならひとつ出力してください。

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

制約

• 入力はすべて整数
• 1 \le Q \le 1000
• 1 \le K \le N \le 1000
• 1 つの入力の中のテストケースすべてにわたる N の総和は 2000 以下

部分点

追加の制約 N \le 5 を満たすデータセットに正解した場合は 10 点が与えられる。

入力例 1

2
4 2
5 1

出力例 1

Yes
1 2
1 3
1 4
No

1 つ目のテストケースでは、4 頂点のスターグラフが出力されています。
黒色の頂点を根として見た時に、上段の 3 つのラベルなし根付き木はすべて同一のものとして扱われます。
また、下段のラベルなし根付き木は他 3 つのラベルなし根付き木と異なるものとして扱われるため、このラベルなし木によって 2 通りのラベルなし根付き木が作られます。よって、このラベルなし木は条件を満たしています。

また、どのような番号の付け方をしても良いため、辺集合が \lbrace (3,4),(3,2),(3,1) \rbrace となるように番号を付けても正解となります。

2 つ目のテストケースでは、条件を満たすラベルなし木は存在しません。

この入力例は、部分点の制約を満たします。

入力例 2

1
7 3

出力例 2

Yes
1 2
1 3
2 4
2 5
3 6
3 7

1 つ目のテストケースでは、下図のラベルなし木が出力されています。
このラベルなし木では同じ色の頂点からどの頂点を根に選んでも、同一のラベルなし根付き木が作られます。
したがって、3 通りのラベルなし根付き木が得られ、このラベルなし木は条件を満たしています。

問題文

1,2,\ldots ,N の番号がついた N 個の荷物が左右一列に並んで置かれています。はじめ、荷物 i は左から i 番目の位置に置かれています。また、各荷物には重さが設定されており、荷物 i の重さは A_i です。

あなたは、この荷物の列に対して、次の一連の操作を 0 回以上好きな回数行うことができます。

1. 1 \le L \lt R \le N を満たす整数組 (L,R) であって、左から L,L+1, \ldots ,R 番目の荷物の重さの総和が K 以上であるようなものを 1 つ選ぶ。
2. 左から L,L+1, \ldots ,R 番目の荷物を、左に巡回シフトする。すなわち、左から L 番目の位置に置いてあった荷物は左から R 番目の位置にくるように、左から L+1,\ldots ,R 番目の位置に置いてあった荷物は、それぞれ左から L,\ldots ,R-1 番目の位置にくるように、荷物を移動させる。

すべての操作が終わった時点での荷物の並び方としてありうるものの個数を 998244353 で割ったあまりを求めてください。

制約

• 入力はすべて整数
• 2 \le N \le 2 \times 10^5
• 1 \le K \le 10^{14}
• 1 \le A_i \le 10^8

入力例 1

4 7
1 2 2 3

出力例 1

12

最初の状態において、左から 2,3,4 番目の荷物の重さの総和は 2+2+3=7 \ge K=7 なので、最初の操作として (L,R)=(2,4) を選ぶことができます。この操作の後、荷物の番号は左から順に 1,3,4,2 となります。

すべての操作が終わった時点での荷物の並び方としてありうるものは 12 通りとなります。

なお、荷物の重さが同じでも、荷物どうしは番号によって区別されることに注意してください。このケースの場合、荷物の番号が左から順に 1,2,3,4 となる並び方と、1,3,2,4 となる並び方は、別の並び方として扱われます。

入力例 2

2 100
1 1

出力例 2

1

操作が 1 回も行えない場合もあります。

入力例 3

20 1
10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10

出力例 3

401576539

998244353 で割ったあまりを答えてください。

問題文

整数 N, X, Y, K, M が与えられます。長さ N の整数列からなる 3 つ組 (A, B, C) であって、以下の条件をすべて満たす組の個数を M で割ったあまりを求めてください。ただし、数列 a の k 番目の要素を a_k と表すこととします。

• i = 1, 2, \dots, N について、(A_i, B_i, C_i) は (1, 2, 3) の順列である。
• A に含まれる 1, 2 の個数はそれぞれ X, Y である。
• A の転倒数と B の転倒数と C の転倒数の合計は K である。

制約

• 入力はすべて整数
• 2 \le N \le 50
• 0 \le X, Y \le N
• X + Y \le N
• 0 \le K \le \frac{3}{2}N(N - 1)
• {10}^8 \le M \le {10}^9

入力例 1

3 1 1 4 998244353

出力例 1

24

条件を満たす (A, B, C) は 24 通り存在します。例えば、A = (1, 2, 3), B = (3, 3, 2), C = (2, 1, 1) とすると、(A, B, C) は条件を満たします。

入力例 2

4 0 0 18 123456789

出力例 2

0

条件を満たす (A, B, C) は存在しません。

入力例 3

50 10 20 1000 1000000000

出力例 3

805988728

問題文

正整数 A,B,C,D が与えられます。

2 次元平面上の相異なる 4 点 p,q,r,s であって、次の条件をすべて満たすものが存在するかどうか判定してください。

• p と q のユークリッド距離は A である。
• q と r のユークリッド距離は B である。
• r と s のユークリッド距離は C である。
• s と p のユークリッド距離は D である。
• 四角形 pqrs は自己交叉しない。すなわち、線分 pq,qr,rs,sp は端点以外に他の線分と交点を持たない。
• 四角形 pqrs の内角のうち 1 つは、180 度より大きい。

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

制約

• 入力はすべて整数
• 1\le T\le 10^5
• 1\le A,B,C,D\le 10^9

入力例 1

4
5 3 2 4
1000 1 1000000 1000000000
100 100 100 100
2024 2022 2019 2015

出力例 1

Yes
No
No
Yes

1 番目のテストケースでは、点 p を (0,0) 、点 q を (3,4) 、点 r を(\frac{62}{17} - \frac{16\sqrt{2}}{17}, \frac{24}{17} - \frac{4\sqrt{2}}{17}) 、点 s を (4, 0) とすると、内角 qrs は 180 度より大きくなり、すべての条件を満たします。

問題文

長さ N の正整数列 A=(A_1,A_2,\dots, A_N) が与えられます。

Q 個のクエリに答えてください。i 個目のクエリでは整数 L_i,R_i が与えられるので、次の問題に B = (A_{L_i},A_{L_i+1},\dots ,A_{R_i}) を与えたときの答えを求めてください。

正整数列 B=(B_1,B_2,\dots, B_{|B|}) が与えられます。正整数列 C=(C_1,C_2,\dots, C_k) が B の非空な部分列として 2 回以上現れるとき、形式的には、正整数 k と 2 つの添字の列 (i_1,i_2,\dots ,i_k),(j_1,j_2,\dots ,j_k) が存在して以下の条件をすべて満たすとき、 C を良い列とします。

• 1\le i_1\lt i_2\lt \dots \lt i_k\le |B|
• 1\le j_1\lt j_2\lt \dots \lt j_k\le |B|
• p=1,2,\dots ,k に対して B_{i_p}=B_{j_p}=C_p が成り立つ。
• ある p\ (1\le p\le k) が存在して i_p\neq j_p が成り立つ。

良い列が存在するかどうか判定し、存在する場合は良い列のうち辞書順で最大のものの ローリングハッシュ を答えてください。ただし、正整数列 a=(a_1,\dots, a_n) の ローリングハッシュ は \displaystyle \left(\sum_{i=1}^{n}a_i 3^{i-1}\right)\bmod 998244353 と定義します。存在しない場合は -1 を答えてください。

ただし、すべてのクエリに渡る R_i-L_i+1 の総和は 10^7 以下であることが保証されます。

制約

• 入力はすべて整数
• 1\le N,Q\le 3\times 10^5
• 1\le A_i\le N\ (1\le i\le N)
• 1\le L_i\le R_i\le N\ (1\le i\le Q)
• \sum_{i=1}^{Q}(R_i-L_i+1)\le 10^7

入力例 1

5 4
3 2 1 2 3
1 5
1 3
2 4
2 5

出力例 1

36
-1
2
11

1 個目のクエリについて説明します。 B=(3,2,1,2,3) の非空な部分列として 2 回以上現れるもののうち辞書順で最大のものは (3,2,3) です。これを与える 2 つの添字の列としては (1,2,5),(1,4,5) を取ることができます。

2 個目のクエリでは B=(3,2,1) で、非空な部分列として 2 回以上現れるものは存在しません。

3 個目のクエリでは B=(2,1,2) で、非空な部分列として 2 回以上現れるもののうち辞書順で最大のものは (2) です。

4 個目のクエリでは B=(2,1,2,3) で、非空な部分列として 2 回以上現れるもののうち辞書順で最大のものは (2,3) です。

入力例 2

5 1
3 2 1 4 1
1 5

出力例 2

18

入力例 3

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

出力例 3

56
20
56
35
20
56
17
35
20
17

問題文

1, 2, …, 9 の数字からなる長さ N の文字列 S が与えられます。

全部で \frac{N(N+1)}{2} 個のブロックからなる三角形のピラミッドがあります。

ピラミッドは N 個の層に分かれており、上から順に層 1, 2, \dots, N と番号付けられています。さらに、層 i (1 \le i \le N) には i 個のブロックが左右一列に並んでいます。各ブロックには文字列が書かれており、層 i の左から j 番目のブロック (1 \le j \le i) に書かれている文字列を C_{i,j} と表します。

C_{i,j} について、以下のことが成り立ちます。

• i = N ならば、C_{i, j} は S の j 番目の文字のみからなる長さ 1 の文字列である。
• 1 \le i < N ならば、C_{i, j} は C_{i+1,j} と C_{i+1,j+1} をこの順に結合したものである。

C_{1,1} を十進表記の整数として見たときの値を 998244353 で割ったあまりを求めてください。

制約

• N は整数
• 1 \le N \le 2 \times 10^5
• S は 1, 2, …, 9 からなる長さ N の文字列

入力例 1

4
8192

出力例 1

81191992

S = 8192 です。ピラミッドは下図の通りになり、C_{1,1} = 81191992 です。

入力例 2

1
5

出力例 2

5

S = 5 です。ピラミッドは下図の通りになり、C_{1,1} = 5 です。

入力例 3

14
11123455678999

出力例 3

913063116

問題文

正整数 A, B, L, R が与えられます。

x = L, L+1, \dots, R について、以下の問題の答えを f(x) とします。

プログラミングコンテストが開催されます。競技者は x 人います。

x 人の競技者を A 人または B 人からなるいくつかのチームに分けます。各競技者はちょうど 1 個のチームに所属しなければなりません。

このとき、チーム数の最小値を求めてください。ただし、チーム分けができない時は、答えを 10^{100} とします。

\displaystyle\max_{L \le x \le R} f(x) を求めてください。ただし、答えが 10^{100} となるときは、-1 と出力してください。

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

制約

• 入力はすべて整数
• 1 \leq T \leq 10^5
• 1 \leq A, B \leq 10^9
• 1 \leq L \leq R \leq 10^{18}

入力例 1

3
3 2 1 7
3 5 10 20
37 518946 448700728 617638174

出力例 1

-1
5
520098

最初のケースについて、参加人数が 1 人の場合、2 人チームにも、3 人チームにも分けることはできません。

2 つ目のケースについて、参加人数が 19 人の場合、3 人チーム 3 つと 5 人チーム 2 つに分けるのが最適で、この時、合計チーム数は 5 となります。 参加人数が 10 人以上 20 人以下のどの場合でも、5 個以下のチームに分けることができるので、答えは 5 となります。

問題文

整数 H, W, A, B, C, D が与えられます。

H 行 W 列のマス目があります。上から i 行目、左から j 列目のマスをマス (i, j) と呼びます。

各マスは白または黒で塗られており、マス (i, j) の色は、A \le i \le B かつ C \le j \le D を満たすとき黒、そうでないとき白です。

このマス目のいくつかの白マスに照明を配置します。白マス (i, j) に置かれた照明は、以下の 2 つの条件を満たす白マスすべてを照らします。

• マス (i, j) と同じ行または同じ列にある
• マス (i, j) とそのマスの間に黒マスが存在しない

照明の配置は、以下の 2 つの条件を満たすとき valid であると言います。

• すべての白マスが、少なくとも 1 つの照明に照らされている
• 照明のあるマスはいずれも、他の照明によって照らされていない

valid な照明の配置の個数を 998244353 で割ったあまりを求めてください。

制約

• 入力はすべて整数
• 1 \leq A \leq B \leq H \leq 5 \times 10^{5}
• 1 \leq C \leq D \leq W \leq 5 \times 10^{5}
• (A, B) \neq (1, H)
• (C, D) \neq (1, W)

入力例 1

3 3 2 2 2 2

出力例 1

7

valid な照明の配置は以下の 7 通りです。

ただし、下図では照明及び照明に照らされている白マスは緑色で表しています。

また、以下のような照明の配置は条件を満たしません。

左図の場合、照明に照らされていない白マスがあるため、条件を満たしません。

右図の場合、照明のある白マスであって、他の照明によって照らされているものがあるため、条件を満たしません。

入力例 2

2 3 1 1 1 2

出力例 2

3

入力例 3

500000 500000 100000 200000 100000 250000

出力例 3

360665510

998244353 で割ったあまりを出力してください。

注意

この問題のメモリ制限は 384 MiB です。

問題文

2N+1 行 2N+1 列のグリッドが与えられます。ここで、 N は正整数です。グリッドの上から i 行目、左から j 列目のマス (1 \le i, j \le 2N + 1) をマス (i, j) と表記します。マス (i, j) には文字 S_{i,j} が書かれており、次の性質を満たします。

• i が奇数、 j が奇数であるとき、 S_{i, j} = o
• i が奇数、 j が偶数であるとき、 S_{i, j} = - または .
• i が偶数、 j が奇数であるとき、 S_{i, j} = | または .
• i が偶数、 j が偶数であるとき、 S_{i, j} = .

独立したクエリが Q 個与えられます。 i 個目 (1 \le i \le N) のクエリでは、奇数 U_i, D_i, L_i, R_i (1 \le U_i \le D_i \le 2N+1,\ 1 \le L_i \le R_i \le 2N+1) が与えられるので、次の問いに答えてください。

部分グリッド [U_i, D_i] \times [L_i, R_i] において、文字 o を頂点、文字 - と | を辺としたときにできる無向グラフの連結成分の個数を求めてください。

厳密には、次に問いに答えてください。

((D_i - U_i + 2) / 2) \times ((R_i - L_i + 2) / 2) 頂点の無向グラフ G があり、頂点は U_i 以上 D_i 以下の奇数 x と L_i 以上 R_i 以下の奇数 y のペア (x, y) で表されるとします。また、無向グラフ G には次の無向辺があるとし、これら以外の無向辺はないとします。

• 奇数 x, y が U_i \le x \le D_i,\ L_i \le y \le R_i - 2 かつ S_{x,y+1} = - を満たすならば、頂点 (x, y) と頂点 (x, y+2) との間に無向辺がある。
• 奇数 x, y が U_i \le x \le D_i - 2,\ L_i \le y \le R_i かつ S_{x+1,y} = | を満たすならば、頂点 (x, y) と頂点 (x+2, y) との間に無向辺がある。

無向グラフ G の連結成分の個数を求めてください。

制約

• N は整数
• 1 \le N \le 2000
• i が奇数、j が奇数であるとき、 S_{i, j} = o
• i が奇数、j が偶数であるとき、 S_{i, j} = - または .
• i が偶数、j が奇数であるとき、 S_{i, j} = | または .
• i が偶数、j が偶数であるとき、 S_{i, j} = .
• Q は整数
• 1 \le Q \le 7000
• 1 \le U_i \le D_i \le 2N+1
• 1 \le L_i \le R_i \le 2N+1
• U_i, D_i, L_i, R_i は奇数

入力例 1

3
o-o-o-o
|.....|
o-o.o.o
|.|....
o-o.o-o
....|.|
o.o-o-o
12
3 5 1 7
1 1 1 1
1 3 1 3
1 3 1 7
1 1 1 1
1 1 1 7
1 7 1 1
1 7 1 7
3 5 3 5
3 5 3 7
3 7 3 7
5 7 3 5

出力例 1

4
1
1
2
1
1
2
4
3
4
4
2

与えられるグリッドは次のようになっています。

1 番目のクエリにおける答えは、次の図のように 4 となります。

問題文

無限に広い二次元グリッドがあります。

グリッド上には N 人の人がおり、i 人目の人ははじめマス (R_{i} ,C_{i}) にいます。各人は金か銀、いずれかの色の帽子をかぶっています。 i 人目の人は H_i = G のとき金色、H_i = S のとき銀色の帽子をかぶっています。

1 ターンごとに、各人は帽子の色に応じて、現在地から以下のように移動することができます。

• 金色の帽子をかぶっている人：
  その場にとどまるか、将棋の金の動きをする。厳密には、現在いるマスを (i, j) としてマス (i-1, j-1), (i-1, j), (i-1, j+1), (i, j-1), (i, j), (i, j+1), (i+1, j) のいずれかに移動する。
• 銀色の帽子をかぶっている人：
  その場にとどまるか、将棋の銀の動きをする。厳密には、現在いるマスを (i, j) としてマス (i-1, j-1), (i-1, j), (i-1, j+1), (i, j), (i+1, j-1), (i+1, j+1) のいずれかに移動する。

N 人全員が同じマスに集まるために必要な最小のターン数を求めてください。

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

制約

• T, N, R_i, C_i は整数
• 1 \le T \le 10^5
• 1 \le N \le 2 \times 10^5
• 1 \le R_i \le 10^9
• 1 \le C_i \le 10^9
• H_i は G か S のいずれか
• 1 つの入力の中のテストケースすべてにわたる N の総和は 2 \times 10^5 以下

部分点

追加の制約 H_i = G を満たすデータセットに正解した場合は 30 点が与えられる。

入力例 1

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

出力例 1

2
2
0
0
5

1 個目のテストケースについて、例えば以下のような移動を行うことで、2 ターンで全員同じマスに集まることができます。

• 1 ターン目
  • 人 1 は (2, 2) に移動する
  • 人 2 は (3, 3) に移動する
• 2 ターン目
  • 人 1 はその場にとどまる
  • 人 2 は (2, 2) に移動する

2 個目のテストケースについて、例えば以下のような移動を行うことで、2 ターンで全員同じマスに集まることができます。

• 1 ターン目
  • 人 1 は (1, 2) に移動する
  • 人 2 は (1, 3) に移動する
  • 人 3 は (1, 2) に移動する
• 2 ターン目
  • 人 1 はその場にとどまる
  • 人 2 は (1, 2) に移動する
  • 人 3 はその場にとどまる

3 個目のテストケースについて、はじめから全員同じマスに集まっています。

入力例 2

2
2
1 1 G
3 3 G
5
1 4 G
5 2 G
3 1 G
3 6 G
1 2 G

出力例 2

2
3

1 個目のテストケースについて、例えば以下のような移動を行うことで、2 ターンで全員同じマスに集まることができます。

• 1 ターン目
  • 人 1 は (2, 1) に移動する
  • 人 2 は (2, 2) に移動する
• 2 ターン目
  • 人 1 はその場にとどまる
  • 人 2 は (2, 1) に移動する

この入力例は、部分点の制約を満たします。

問題文

2 つのプログラム Alice, Bob が協力して以下のゲームを行います。

0 以上 2^{64} 未満の整数 A, B があります。はじめ Alice のみが A を、Bob のみが B を知っています。

C := \min(A, B) とします。ゲームの目的は、Alice と Bob の両方が C の値を答えられるようにすることです。

そのために、Alice と Bob は以下の関数を何度でも呼び出して情報をやりとりすることができます。

• send(x) : 相手のプログラムが receive() を呼び出すまで待機する。その後、 1 bit の値 x を相手に送信する。
• receive() : 相手のプログラムが send() を呼び出すまで待機する。その後、 1 bit の値 x を相手から受け取って返り値とする。

情報のやり取りが終了した後、各プログラムは以下の関数を 1 度呼び出して C の値を回答する必要があります。

• answer(x) : C の値が x であると回答する。この関数を呼び出した後、ただちにプログラムを終了しなければならない。

Alice と Bob の両方が正しく C の値を回答したらゲームは成功となります。このとき、関数 send() の呼び出し回数の合計が少ないほど良い評価が得られます。

できるだけ少ない回数の関数の呼び出しでゲームを成功させるような 2 つのプログラム Alice, Bob を作成してください。

入出力

この問題はインタラクティブ問題（あなたの作成したプログラムとジャッジプログラムが入出力を介して対話を行う形式の問題）です。
Alice として振る舞うあなたのプログラムと、Bob として振る舞うあなたのプログラムが、ジャッジプログラムを介してゲームを行います。

プログラムの開始

あなたのプログラムは、まず以下の形式で入力を受け取ってください。

\text{Player}
X

ここで、\text{Player} は文字列 Alice または文字列 Bob であり、X は 0 以上 2^{64} 未満の整数です。

• \text{Player} = {}Alice である場合、A = X であることを表します。また、あなたのプログラムはこれ以降 Alice として振る舞わなければなりません。
• \text{Player} = {}Bob である場合、B = X であることを表します。また、あなたのプログラムはこれ以降 Bob として振る舞わなければなりません。

その後、以下に示す方法で send(), receive(), answer() の呼び出しを行ってください。

send

send 関数を呼び出すには、以下の形式で出力してください。

send x

ここで、x は 0 または 1 でなければなりません。
この関数は相手のプログラムが receive() を呼び出すまで待機しますが、待機中に相手のプログラムが停止したり、相手も send 関数を呼び出すと WA になります。

receive

receive 関数を呼び出すには、以下の形式で出力してください。

receive

その後、相手のプログラムから送られた値 x を以下の形式で読み取ってください。

x

この関数は相手のプログラムが send() を呼び出すまで待機しますが、待機中に相手のプログラムが停止したり、相手も receive 関数を呼び出すと WA になります。
やり取りの途中で WA となった場合、与えられる入力は -1 になります。この場合、ただちにプログラムを終了してください。

answer

answer 関数を呼び出すには、以下の形式で出力してください。

answer x

ここで、x は \min(A, B) と一致していなければなりません。この関数を呼び出した後は、ただちにプログラムを終了してください。

得点

あるテストケースにおける、2 つのプログラムの send() の呼び出し回数の合計を Q' とします。この問題のすべてのテストケースにわたる Q' の最大値を Q として、

• Q ≤ 76 のとき 100 点
• 76 < Q ≤ 128 のとき \left\lfloor 100 - 27 \cdot \ln(\frac{Q-74}{2})\right\rfloor 点
• Q > 128 のとき 0 点（WA になります）

が与えられます。

注意点

• 出力を行うたびに、末尾に改行を入れて標準出力を flush してください。そうしなかった場合、ジャッジ結果が TLE となる可能性があります。
• ジャッジプログラムと、Alice として振る舞うあなたのプログラムと、Bob として振る舞うあなたのプログラムが同時に実行されます。実行時間・使用メモリはこれらの合計で計測されるため、実行時間・使用メモリには余裕を持ってください。
  • ジャッジプログラムは最大で 50 ms・5 MiB 程度を消費します。
• この問題では、実行中にファイルを作成することができません。したがって、実行中にファイルを作成するような言語・プログラムでは AC を取ることができません。 例えば、C# では AC を取ることができないため、代わりに C# AOT を使用してください。
• 0 以上 2^{64} 未満の整数を扱います。オーバーフローには十分注意してください。

入出力例

問題文

長さ N の正整数列 A=(A_1,A_2,\ldots,A_N) が与えられます。はじめ、 A に M の倍数が含まれていないことが保証されます。

あなたは次の操作を N-1 回行います。

1. 1 \le i \le |A|-1 を満たす整数 i を選択する
2. A_i と A_{i+1} を足して 1 つの要素にする
   • より正確には、 (A_1 ,\ldots,A_{i-1}),(A_{i}+A_{i+1}),(A_{i+2},\ldots,A_{|A|}) をこの順に連結したもので A を置き換える
   • この操作により A の長さは 1 減少する

操作の過程で A に M の倍数が現れないように N-1 回の操作を行えるかどうか判定してください。 操作が可能な場合はそのような操作列を 1 つ構成してください。

制約

• 入力はすべて整数
• 3 \le N \le 2\times 10^5
• 2 \le M \le 10^9
• 1 \le A_i < M
• A_i は M の倍数ではない

入力例 1

4 4
1 2 3 1

出力例 1

Yes
2 1 1

この入力例において、はじめ A=(1,2,3,1) です。

• 1 回目の操作では i=2 を選択して A=(1,5,1) となります。
• 2 回目の操作では i=1 を選択して A=(6,1) となります。
• 3 回目の操作では i=1 を選択して A=(7) となります。

この操作の過程では A に 4 の倍数が現れません。

入力例 2

9 5
3 2 3 2 1 3 2 3 2

出力例 2

Yes
4 3 2 2 2 2 1 1

入力例 3

7 123456789
69024393 73329927 23109098 63845999 71517732 113556305 79443702

出力例 3

No

問題文

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

各マスは障害物が置かれたマスか、黒く塗られたマスか、白く塗られたマスのいずれかです。マスの状態は H 個の長さ W の文字列 S_1,S_2,\dots,S_H によって与えられ、S_i の j 文字目が # のときマス (i,j) には障害物が置かれていて、 B のときマス (i,j) は黒く、 W のときマス (i,j) は白く塗られています。

あなたは好きな 黒く塗られたマス を 1 つ選び、そこから移動を繰り返します。 1 回の移動で今いるマスから上下左右に隣接する、黒く塗られたマスか白く塗られたマスに移動することができます。

以下の条件を満たしながら 10^{100} 回移動することができるかどうか判定してください。

• x\ (1 \leq x \leq 10^{100}) 回目の移動の後にいるマスは、 x \equiv 0 \pmod K のとき黒く、 x \not\equiv 0 \pmod K のとき白く塗られている

制約

• H, W, K は整数
• 1 \leq H, W
• H \times W \leq 10^6
• 2 \leq K \leq 10^9
• S_i は #, B, W からなる長さ W の文字列
• S_1,S_2,\dots,S_H のうち少なくとも 1 つは B を含む

入力例 1

2 4 5
BWW#
W#BB

出力例 1

Yes

マス (1,1) を選び、移動を開始します。 (1,1) \rightarrow (1,2) \rightarrow (1,3) \rightarrow (1,2) \rightarrow (1,3) \rightarrow (2,3) \rightarrow (1,3) \rightarrow (1,2) \rightarrow (1,3) \rightarrow \cdots と移動していくと、条件を満たしながら 10^{100} 回移動することができます。

入力例 2

3 1 4
B
W
W

出力例 2

Yes

入力例 3

2 5 3
BWW##
##WWB

出力例 3

No

問題文

N 人が数直線上におり、左から i 番目の人は座標 A_i にいます。また、正整数 L, R \ (L \le R) が与えられます。

この数直線上に 1 本以上の旗を立てることを考えます。立てた旗の本数を k 本として、それらの座標を x_1, x_2, \dots, x_k とします。次の条件をともに満たすとき、この旗の立て方は良い立て方であると言います。

• すべての旗は整数座標にある。すなわち、すべての j = 1, 2, \dots, k に対し x_j は整数である。
• すべての人について、その人からその人と最も近い旗との距離は L 以上 R 以下である。すなわち、すべての i = 1, 2, \dots, N に対し L \le \bigl( \min_{1\le j\le k} |A_i - x_j| \bigr) \le R である。

良い旗の立て方がある場合は立てる旗の本数を最小化して構築し、ない場合はそれを報告してください。なお、良い旗の立て方がある場合は立てるべき旗の最小本数 k が 8N 以下であることが証明できます。

T 個のテストケースについて答えてください。

制約

• 入力はすべて整数
• 1 \le T \le 2 \times 10^4
• 1 \le N \le 2\times 10^5
• 1 \le L \le R \le 5 \times 10^8
• -5\times 10^8 \le A_1 \lt A_2 \lt \dots \lt A_N \le 5\times 10^8
• テストケース全体で N の総和は 4 \times 10^5 以下

部分点

次の条件をすべて満たした場合、部分点 25 点が与えられる。

• 良い旗の立て方がないテストケースについて、構築不可能と報告している。
• 良い旗の立て方があるテストケースについて、構築可能と報告しており、構築した旗の立て方が良い立て方であり、立てた旗の本数が 8N 本以下である。
• いずれかのテストケースにおいて、良い旗の立て方があるが、旗の本数が最小化されていない。

入力例 1

4
1 3 6
0
2 5 5
-15 -5
2 3 4
0 2
3 100 100
-100 0 100

出力例 1

1
6 
1
-10 
2
-3 6 
-1

1 番目のテストケースでは座標 0 に人がおり、座標 0 から最も近い旗までの距離が 3 以上 6 以下でないといけません。

出力例では、1 本の旗を座標 6 に立ててあり、座標 0 から最も近い旗（座標 6）までの距離は 6 であるので、良い旗の立て方であり、立てる旗の本数の最小化も達成されています。一方で、

1
-2

という出力の場合、座標 0 から最も近い旗（座標 -2）までの距離は 2 であり、3 以上 6 以下ではないので良い旗の立て方ではありません。

問題文

STPC(Science Tokyo Programming Contest) は東京科学大学の学生が開催するコンテストです。初回は 2025 年 11 月 8 日に行われました。早速、次回の STPC の日程を決めることにしましょう！

正整数 N,L,W と N 個の正整数 D_1,D_2,\dots, D_N が与えられます。

あなたは STPC というイベントの開催日程を決めようとしています。具体的には、正整数 X を決めて、STPC を今日から X 日後に開催しようとしています。

さて、現在予定されている重大なイベントが N 個あります。 i 個目のイベントは今日から D_i 日後に開催されることが分かっています。

あなたはこれらのイベントと日程が被るのを避けて STPC の開催日程を決めることにしました。すなわち、任意の i に対して D_i\neq X である必要があります。また、準備には時間がかかるため、X\ge L である必要があります。さらに、開催会場の都合上、X は W の倍数である必要があります。

これらの条件をすべて満たすように STPC の開催日程を決めるとき、最も早い開催日程は今日から何日後であるかを求めてください。すなわち、すべての条件を満たす最小の正整数 X を求めてください。

ただし、このような X が存在することは証明できます。

制約

• 入力はすべて整数
• 1\le N\le 2\times 10^5
• 1\le L,W\le 10^9
• 1 \le D_1 \lt D_2 \lt \dots \lt D_N \le 10^9

入力例 1

5 3 2
1 3 4 7 9

出力例 1

6

この入力例では L = 3, W = 2 です。

• X = 1 は X \ge L を満たしません。
• X = 2 は X \ge L を満たしません。
• X = 3 は W の倍数ではありません。
• X = 4 は 3 個目のイベントと被ってしまいます。
• X = 5 は W の倍数ではありません。
• X = 6 はすべての条件を満たします。

よって、最も早い開催日程は 6 日後です。

入力例 2

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

出力例 2

11