問題文

長さ N の非負整数列 A=(A_1,A_2,\ldots,A_N) が与えられます． ここで，2 \leq N および A_1 < A_2 < \cdots < A_N が保証されます．

あなたは今から以下の操作を 1 回以上行います．

• 正整数 x を選ぶ．そして，すべての i (1 \leq i \leq N) について，A_i の値を，A_i を x で割ったあまりで置き換える．

ここで，操作列のスコアを，操作で使用した x の最小値と定義します．

あなたの目標は，A のすべての要素が等しい状態にすることです． 目標を達成する操作列のスコアとしてあり得る最大値を求めてください．

1 つの入力につき，T ケースを解いてください．

制約

• 1 \leq T \leq 125000
• 2 \leq N \leq 250000
• 0 \leq A_1 < A_2 < \cdots < A_N \leq 10^9
• T ケースにわたる N の総和は 250000 以下
• 入力はすべて整数

入力例 1

4
3
2 3 5
4
4 10 15 25
5
0 10 20 30 40
15
52633263 109965057 177443516 242738411 319866698 372592710 429724665 485840965 570195620 653861052 725414602 781977517 835165877 912632268 988630679

出力例 1

2
6
10
57331794

例えば，1 つめのテストケースでは，以下のように操作を行えばよいです．

• x=5 として操作を行う．A は (2,3,0) になる．
• x=3 として操作を行う．A は (2,0,0) になる．
• x=2 として操作を行う．A は (0,0,0) になる．

問題文

1 から N までの番号のついた N 頂点からなる重み付き完全無向グラフ G があります． 頂点 i と頂点 j (1 \leq i < j \leq N) を結ぶ辺の重みは C_{i,j} です．

Alice と Bob はこれからゲームをします． まずゲームの準備として，Bob が以下の操作を行います．

• G から 0 本以上の辺を削除する．ここで削除した辺の重みの総和をコストと呼ぶことにする．
• 頂点のうち好きな A 個を選び，そこに A と書き込む．残りの N-A 個に B と書き込む．
• 好きな頂点を 1 個選び，そこに駒を 1 つ置く．

準備が終了したらゲームを開始します． Alice から始めて二人のプレイヤーは交互に手番をプレイします． 各手番では，次のいずれかの行動ができます．

• ゲームを終了する．
• 駒を隣接頂点へと動かす．ただし，今までに駒が置かれたことのある頂点へは動かせない（ゲーム開始時に駒が置かれていた頂点にも動かせない）．

ゲームが終了した瞬間に駒が置かれていた頂点に書かれた文字が A なら Alice の勝ち，B なら Bob の勝ちです． Bob は自分に必勝法が存在するようにゲームを準備したいです． そのために必要なコストの最小値を求めてください．

1 つの入力につき，T ケースを解いてください．

制約

• 1 \leq T \leq 100
• 2 \leq N \leq 20
• 1 \leq A \leq N-1
• 0 \leq C_{i,j} \leq 10^9
• T ケースにわたる N^2 の総和は 20^2 以下
• 入力はすべて整数

入力例 1

4
2 1
1
4 2
0 1 0
1 1
1
4 3
0 1 0
1 1
1
10 6
920863892 404674703 404674703 972355497 19199103 13614516 2354795 994561596 404674703
333091354 956864449 832425833 949490369 267560921 607314403 595085993 147983762
979679626 425301247 13605197 11023257 25122957 333091354 925837072
629748489 333702011 455328188 529811895 662742653 679478024
532156763 300916094 645258473 298300578 337246479
523721752 333702011 1356103 9719790
657515163 3035530 3007974
15464189 19594391
298300578

出力例 1

1
0
1
137097802

1 番目のテストケースでは，以下のようにゲームを準備すればよいです．

• 辺 (1,2) を削除する．コストが 1 かかる．
• 頂点 1,2 にそれぞれ A,B を書き込む．
• 駒を頂点 2 に置く．

2 番目のテストケースでは，以下のようにゲームを準備すればよいです．

• 辺 (1,2),(1,4) を削除する．コストが 0 かかる．
• 頂点 1,2,3,4 にそれぞれ B,A,B,A を書き込む．
• 駒を頂点 1 に置く．

問題文

1 から N までの番号のついた N 頂点からなる無向木があります． 辺には 1 から N-1 までの番号がついており，辺 i は頂点 A_i と頂点 B_i を結んでいます．

各辺 i には 2 つのカウンター x_i,y_i があります． 最初，x_i=y_i=0 です．

あなたは今から以下の操作を 0 回以上行います．

• 木上のウォークを自由に選ぶ． より正確には，頂点列 (v_0,v_1,\ldots,v_k) (頂点 v_i,v_{i+1} は直接辺で結ばれており，ウォークの長さ k は任意) を選ぶ． 頂点 v_i,v_{i+1} を結ぶ辺を辺 e_i とする． そして，各 i=0,2,4,\ldots に対して，x_{e_i} の値を 1 増やす． 同様に，各 i=1,3,5,\ldots に対して，y_{e_i} の値を 1 増やす． なお，同じ辺が複数回登場する場合は，登場するたびにカウンターの値が増加する．

各辺には，目標とすべきカウンターの値 X_i,Y_i が定まっています． あなたの目標は，すべての辺でカウンターの値が (x_i,y_i)=(X_i,Y_i) となっている状態にすることです． 目標が達成可能かどうか判定してください． また可能な場合は，そのために必要な最小の操作回数を求めてください．

1 つの入力につき，T ケースを解いてください．

制約

• 1 \leq T \leq 125000
• 2 \leq N \leq 250000
• 1 \leq A_i,B_i \leq N
• 0 \leq X_i,Y_i \leq 10^9
• 入力されるグラフは木である
• T ケースにわたる N の総和は 250000 以下
• 入力はすべて整数

入力例 1

4
3
1 2 2 0
2 3 0 1
3
1 2 1 0
2 3 0 2
5
2 3 3 3
3 5 5 2
1 4 2 4
4 5 1 1
10
3 10 0 16306834
6 8 123600023 90587973
10 1 35502434 4326053
1 9 0 6983702
10 2 0 11702429
6 5 0 53901118
10 4 82799399 29529115
10 8 72275777 16348135
6 7 0 21602025

出力例 1

2
-1
-1
215877450

例えば，1 番目のテストケースについては，以下のように 2 回の操作を行うことで目標を達成できます．

• ウォーク (1,2,3) を選び，x_1,y_2 の値を 1 増やす．
• ウォーク (2,1) を選び，x_1 の値を 1 増やす．

2 番目と 3 番目のテストケースでは，どうやっても目標を達成することができません．

問題文

1 から N までの番号のついた N 人の子供たちがおり，各人が 1 つのプレゼントを持って集まりました． 彼らは今からプレゼント交換を行おうとしています． 具体的には，以下の操作を行います．

• まず N 脚の椅子を用意し，円環状に並べる．椅子には時計回りに 1,2,\ldots,N と番号をつけておく．
• 次に，0 回以上のフェーズを行う． あなたは，最初のフェーズの開始前にフェーズ数 k と各フェーズでの座り方 p_{i,j} (意味は後述) を決めて，それを子どもたちに伝える． その後子どもたちが k 回のフェーズを行う．i 回目のフェーズでは以下の動作を行う．
  • まず，各 j (1 \leq j \leq N) について，子供 p_{i,j} が椅子 j に座る．
  • その後，子どもたちは以下の行動を 0 回以上 N-1 回以下行う．
    • 自分が現在持っているプレゼントを，時計回りで次の椅子に座っている子供に渡す，という操作を N 人が同時に行う．

あなたは，フェーズ数と各フェーズでの座り方を適切に決めることで，以下の M 個の条件を満たすようにしたいです．

• i 番目 (1 \leq i \leq M) の条件: 各フェーズでプレゼントが回される回数を適切に指定すれば，子供 1,2 が持ってきたプレゼントがそれぞれ子供 A_i,B_i の手にある状態でプレゼント交換を終えることができる．

条件を満たすことが可能かどうか判定し，可能な場合は必要な最小のフェーズ数 k と，実際に条件を達成する座り方 p_{i,j} を 1 つ求めてください．

1 つの入力につき，T ケースを解いてください．

制約

• 1 \leq T \leq 64
• 2 \leq N \leq 16
• 1 \leq M \leq N(N-1)
• 1 \leq A_i,B_i \leq N
• A_i \neq B_i
• (A_i,B_i) \neq (A_j,B_j) (i \neq j)
• T ケースにわたる N^2 の総和は 16^2 以下
• 入力はすべて整数

入力例 1

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

出力例 1

1
3 2 1
-1
1
4 1 2 3
0

例えば，1 つめのテストケースではフェーズ数を 1 とし，子供 3,2,1 を椅子 1,2,3 に座らせればよいです．このとき，以下のようにプレゼント交換が進む可能性があります．

• 子どもたちがプレゼントを 0 回時計回りに回す．子供 1,2 の持ってきたプレゼントは，それぞれ子供 1,2 の手にある状態で終わる．
• 子どもたちがプレゼントを 1 回時計回りに回す．子供 1,2 の持ってきたプレゼントは，それぞれ子供 3,1 の手にある状態で終わる．
• 子どもたちがプレゼントを 2 回時計回りに回す．子供 1,2 の持ってきたプレゼントは，それぞれ子供 2,3 の手にある状態で終わる．

よって，2 つの条件は両方とも満たされています．

問題文

長さ 2^N の非負整数列が M 個黒板に書いてあります． i 番目 (1 \leq i \leq M) の数列は A_i=(A_{i,1},A_{i,2},\ldots,A_{i,2^N}) です．

あなたは以下の 2 種類の操作を好きな順番で好きな回数行うことができます．

• 黒板に書かれた数列を 1 つ自由に選び，それを 1 回左シフトしたものを新たに黒板に書き込む． より正確に言えば，数列 x=(x_1,x_2,\ldots,x_{2^N}) を選んだ場合，新たに (x_2,\ldots,x_{2^N},x_1) を書き込む．

• 黒板に書かれた数列を 2 つ（これらが同一でも構わない）を自由に選び，それらの要素ごとのビット単位 \mathrm{XOR} をとった数列を新たに黒板に書き込む． より正確に言えば，数列 x=(x_1,x_2,\ldots,x_{2^N}),y=(y_1,y_2,\ldots,y_{2^N}), を選んだ場合，新たに (x_1 \oplus y_1,x_2 \oplus y_2,\ldots,x_{2^N} \oplus y_{2^N}) を書き込む．

どちらの操作でも，選んだ数列は消えないことに注意してください．

黒板に書き込むことができる数列の種類数を 998244353 で割ったあまりを求めてください．

制約

• 1 \leq N \leq 16
• 1 \leq M \leq 8
• 0 \leq A_{i,j} < 256
• 入力はすべて整数

入力例 1

1 1
1 2

出力例 1

4

以下の手順で 4 種類の数列を書き込むことができます．

• 最初，黒板には (1,2) のみが書かれている
• (1,2) と (1,2) を選び \mathrm{XOR} をとることで，(0,0) を書き込むことができる．
• (1,2) を選んで左シフトすることで，(2,1) を書き込むことができる．
• (1,2) と (2,1) を選び \mathrm{XOR} をとることで，(3,3) を書き込むことができる．

入力例 2

1 2
1 1
1 2

出力例 2

8

入力例 3

2 4
12 4 11 15
0 6 4 0
8 5 4 8
2 8 8 13

出力例 3

32768

入力例 4

4 5
55 153 189 168 81 18 15 140 3 101 113 216 215 67 113 81
42 47 89 86 51 230 108 163 251 112 246 238 160 176 37 169
63 215 220 47 148 158 76 112 140 210 14 125 222 217 120 127
159 238 73 195 112 141 239 109 175 82 191 20 95 46 6 165
156 37 120 73 189 235 107 167 184 42 29 136 219 237 232 212

出力例 4

8247623

問題文

正整数 N,M,K が与えられます．

次の条件を満たす長さ N の非負整数列 a=(a_1,a_2,\ldots,a_N) を，よい数列と呼ぶことにします．

• 0 \leq a_1 \leq a_2 \leq \cdots \leq a_N \leq M

よい数列 a に対し，多項式 f_a(x) を次のように定めます．

• f_a(x)=(\prod_{1 \leq i \leq K} (a_i+x)) \times (\prod_{K+1 \leq i \leq N} a_i)

すべてのよい数列 a について f_a(x) を足し合わせて得られる多項式を g(x) とします． 明らかに g(x) は K 次の多項式となります． 各 i (0 \leq i \leq K) について，g(x) の i 次の係数 g_i を 998244353 で割ったあまりを求めてください．

制約

• 1 \leq K \leq N \leq 250000
• 1 \leq M \leq 250000
• 入力はすべて整数

入力例 1

2 2 2

出力例 1

7 12 6

すべてのよい数列 a とそれに対する f_a(x) は以下のようになります．

• a=(0,0): f_a(x)=x^2
• a=(0,1): f_a(x)=x^2+x
• a=(0,2): f_a(x)=x^2+2x
• a=(1,1): f_a(x)=x^2+2x+1
• a=(1,2): f_a(x)=x^2+3x+2
• a=(2,2): f_a(x)=x^2+4x+4

これらの f_a(x) をすべて足し合わせると，g(x)=6x^2+12x+7 となります．

入力例 2

3 4 2

出力例 2

350 357 105

入力例 3

15 10 1

出力例 3

403118239 34849843

入力例 4

250000 250000 5

出力例 4

528068001 689977268 512161527 103797525 493357217 965257117

問題文

長さ N の整数列 A=(A_1,A_2,\ldots,A_N) 及び整数 K が与えられます． 関数 f(L,R) (1 \leq L \leq R \leq N) を次のように定義します．

• R-L +1 < K のとき，f(L,R)=0 とする．
• そうでないとき，(A_L,A_{L+1},\ldots,A_{R}) から K 個の非空な連続部分列を重なりがないように取り出すことを考える． 「一番左の部分列に含まれる要素の総和の絶対値」+「それ以外の部分列に含まれる要素の総和」としてあり得る最大値を f(L,R) とする． より形式的に言えば，f(L,R)=\max_{L\leq l_1 \leq r_1 < l_2 \leq r_2 < \ldots < l_K \leq r_K \leq R}(|\sum_{l_1 \leq i \leq r_1} A_i| + \sum_{2 \leq j \leq K} \sum_{l_j \leq i \leq r_j} A_i) である．

\sum_{1 \leq L \leq R \leq N} f(L,R) を 998244353 で割ったあまりを求めてください （負の数を割ったあまりも 0 以上 998244353 未満の範囲で求めてください）．

制約

• 1 \leq K \leq N \leq 250000
• K \leq 4
• -10^9 \leq A_i \leq 10^9
• 入力はすべて整数

入力例 1

3 2
2 -2 -1

出力例 1

2

K \leq R-L+1 に対する f(L,R) の値は以下のようになります．

• (L,R)=(1,2) のとき: (l_1,r_1,l_2,r_2)=(1,1,2,2) が最大値を達成し，f(L,R)=0 となる．
• (L,R)=(1,3) のとき: (l_1,r_1,l_2,r_2)=(1,1,3,3) が最大値を達成し，f(L,R)=1 となる．
• (L,R)=(2,3) のとき: (l_1,r_1,l_2,r_2)=(2,2,3,3) が最大値を達成し，f(L,R)=1 となる．

よって，これらの和である 2 が答えです．

入力例 2

5 2
-1 -2 -4 -8 -16

出力例 2

998244327

入力例 3

10 3
-21 -75 -29 -5 -99 -60 -75 -98 -48 -66

出力例 3

2320

入力例 4

15 4
-296045184 -17176032 -21940358 388585142 -410726492 244506160 -324910496 -99305133 -45869288 -25027474 -109128673 105493294 -6256129 -40956935 -33486703

出力例 4

51969020