問題文

頂点に 1 から N の番号がついた N 頂点 0 辺のグラフがあります。あなたは k = 1,2,\dots , N-1 に対して以下の操作を行います。

• 2 つの頂点 u, v を選び、その間に辺を張る。この操作のコストは (u + v) \times k を N で割ったあまりとする。

ただし、N-1 回の操作が終了したときグラフが連結になっている必要があります。

N-1 回の操作のコストの総和としてありうる最小値を求めてください。

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

制約

• 1 \le T \le 100
• 2 \le N \le 10^9
• 入力はすべて整数

入力例 1

3
4
56
789

出力例 1

1
0
130

1 番目のテストケースについて、以下のように操作するとコストの総和が 1 となります。

• k = 1 のとき u = 1, v = 4 を選ぶ。コストは (1 + 4) \times 1 \bmod 4 = 1
  
• k = 2 のとき u = 2, v = 4 を選ぶ。コストは (2 + 4) \times 2 \bmod 4 = 0
  
• k = 3 のとき u = 1, v = 3 を選ぶ。コストは (1 + 3) \times 3 \bmod 4 = 0

終了時にグラフが連結になるように操作する方法であって、コストの総和は 0 以下のものはないため、答えは 1 です。

問題文

長さ N の非負整数列 A = (A_1, A_2, ..., A_N) が与えられます。 あなたは以下の操作を 0 回以上 K 回以下行うことができます。

• 1 \leq i \leq N を満たす整数 i を一つ選び、A_i を 0 に変更する。

長さ N の整数列 B = (B_1, B_2, ..., B_N) を、 \displaystyle B_i = \sum_{j=1}^{i} A_j で定義します。 最終的な \displaystyle\sum_{i=1}^{N} B_i として考えられる最小値を求めてください。

制約

• 1 \leq K \leq N \leq 3 \times 10^5
• 0 \leq A_i \leq 10^7
• 入力はすべて整数

入力例 1

5 2
1 1 3 2 9

出力例 1

13

i = 3, 5 として操作を行ったとき A = (1, 1, 0, 2, 0) , B = (1, 2, 2, 4, 4) となり、B の総和は 13 になります。
どのように操作を行っても B の総和を 12 以下とすることはできないため、答えは 13 となります。

入力例 2

4 1
6 0 2 6

出力例 2

10

入力例 3

3 3
2 3 8

出力例 3

0

問題文

長さ N の正整数列 A=(A_1,A_2,\dots,A_N) が与えられます。ここで、整数列 X=(X_1,X_2,\dots,X_l) に対して以下のように f(X) を定義します。

• 0 \le i \le N について、正整数列 C^{(i)} を (A_1,A_2,\dots,A_i,X_1,X_2,\dots,X_l,A_{i+1},A_{i+2},\dots,A_N,\textcolor{red}{\boldsymbol{i}}) と定義する。これら N+1 個の数列のうち、辞書順で最も小さいもの(一意に定まることが証明できます)を C^{(k)} としたとき、f(X) = k とする。

i = 0,1,\dots,N に対して、以下の問題を解いてください。

• 長さが 1 以上 M 以下かつすべての要素が 1 以上 K 以下であるような整数列 B のうち、f(B) = i を満たすものの個数を 998244353 で割ったあまりを求めよ。

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

制約

• 1 \le T \le 5 \times 10^5
• 1 \le N \le 5 \times 10^5
• 1 \le M \le 10^9
• 1 \le K \le 10^9
• 1 \le A_i \le K
• すべてのテストケースに対する N の総和は 5 \times 10^5 以下
• 入力はすべて整数

入力例 1

4
2 1 3
2 3
3 2 4
3 1 2
5 7 100
23 38 19 78 97
12 66621153 962738384
596076187 241253251 294255618 160313007 362465084 613302073 172378047 202387723 783794852 575378463 266956797 649540193

出力例 1

2 1 0 
10 0 0 10 
166591803 201113277 0 215366213 869870626 294965523 
742219241 0 0 0 0 357811811 0 0 797772154 0 0 0 896363579 

1 番目のテストケースについて、長さが 1 かつ要素が 1 以上 3 以下な正整数列 B すべてについて C^{(i)} を列挙すると以下のようになります。

• B=(1) のとき、C^{(0)}=(1,2,3,0),C^{(1)}=(2,1,3,1),C^{(2)}=(2,3,1,2) となり、f(B) = 0 である。
• B=(2) のとき、C^{(0)}=(2,2,3,0),C^{(1)}=(2,2,3,1),C^{(2)}=(2,3,2,2) となり、f(B) = 0 である。
• B=(3) のとき、C^{(0)}=(3,2,3,0),C^{(1)}=(2,3,3,1),C^{(2)}=(2,3,3,2) となり、f(B) = 1 である。

よって、i=0,1,2 に対する答えはそれぞれ 2,1,0 となります。

問題文

M 次元空間上の点が N 個与えられます。i 個目の点は (x_{i,1},x_{i,2},\dots,x_{i,M}) にあります。また、非負整数 D も与えられます。

\lbrace 1,2,\dots,N \rbrace の部分集合の組 (S_1,S_2) のうち、以下の条件を全て満たすものの個数を 998244353 で割った余りを求めてください。

• 1 \le i \le N を満たす整数 i は S_1,S_2 のうち片方にのみ含まれる。
• a,b \in S_c を満たす任意の a,b,c に対して、\sum_{i=1}^{M} |x_{a,i} - x_{b,i}| \le D を満たす。

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

制約

• 1 \le T \le 2 \times 10^5
• 1 \le N \le 2 \times 10^5
• 1 \le M \le 4
• 0 \le D \le 10^9
• 0 \le x_{i,j} \le 10^9
• すべてのテストケースにおける N の総和は 2 \times 10^5 以下
• 入力はすべて整数

入力例 1

4
4 2 5
1 4
3 3
5 8
9 7
3 1 0
1
2
3
6 2 1
1 1
2 1
1 2
2 2
1 1
2 1
8 3 102
13 14 25
20 19 32
32 8 27
19 31 19
8 12 5
27 39 4
30 28 21
40 17 18

出力例 1

2
0
4
256

1 番目のテストケースについては、(S_1,S_2) = (\lbrace 1,2 \rbrace,\lbrace 3,4 \rbrace),(\lbrace 3,4 \rbrace,\lbrace 1,2 \rbrace) の 2 個が条件を満たします。

2 番目のテストケースについては、条件を満たす (S_1,S_2) は存在しません。

問題文

正整数 x に対して、f(x) を「x を十進表記した文字列を逆順にして得られる文字列を十進表記の整数と解釈した値」と定義します。例えば、f(123) = 321,f(1200) = 21 です。

正整数 N,M が与えられます。\displaystyle \sum_{x=1}^{10^N-1} f(x)^M を 998244353 で割ったあまりを求めてください。

制約

• 1 \le N \le 10^9
• 1 \le M \le 10^6
• 入力はすべて整数

部分点

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

• M=1 を満たすデータセットに正解した場合 1 点が与えられる。

入力例 1

1 1

出力例 1

45

1 \le x \le 9 を満たす整数 x について、f(x) = x です。よって、\sum_{x=1}^{9} f(x) = 45 が答えです。

入力例 2

2 3

出力例 2

22479525

入力例 3

12345 54321

出力例 3

144731006

問題文

(1,2,\dots,N) の順列のうち、長さ 3 の単調減少な連続部分列を含まないものの個数を 10^9 + 9 で割ったあまりを求めてください。

制約

• 1 \le N \le 1.7 \times 10^7
• N は整数

部分点

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

• N \le 3000 を満たすデータセットに正解した場合 1 点が与えられる。

入力例 1

3

出力例 1

5

(1,2,3) の順列のうち、(3,2,1) 以外の 5 個が条件を満たします。

入力例 2

6

出力例 2

349

入力例 3

123

出力例 3

756051385

入力例 4

17000000

出力例 4

430982110

問題文

頂点に 1 から N の番号がついた N 頂点 N 辺の有向グラフが与えられます。i 番目の辺は頂点 i から頂点 X_i への辺です。ただし、このグラフは辺の向きを無視した無向グラフにしたときに連結であることが保証されます。

各頂点にはいくつかの駒が置かれており、頂点 i には A_i 個の駒が置かれています。あなたはこれから以下の操作を N 回行います。

• すべての駒を、今置かれている頂点から出ている唯一の辺に沿って移動させる。

k = 0,1,\dots,N について、k 回目の操作が終わった時点での \sum_{i=1}^{N} (頂点 i に置かれている駒の個数) \times B_i を求めてください。

制約

• 1 \le N \le 2 \times 10^5
• 1 \le X_i \le N
• 1 \le A_i,B_i \le 10^6
• 与えられるグラフは辺の向きを無視した無向グラフにしたときに連結
• 入力はすべて整数

部分点

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

• X_i = i を満たす整数 i が存在するデータセットに正解した場合 1 点が与えられる。

入力例 1

3
2 1 1
4 1 2
3 5 1

出力例 1

19 29 27 29 

(頂点 1 に置かれている駒の個数 , 頂点 2 に置かれている駒の個数 , 頂点 3 に置かれている駒の個数) は、以下のように変化します。

• (4,1,2) \rightarrow (3,4,0) \rightarrow (4,3,0) \rightarrow (3,4,0)

それぞれの時点における \sum_{i=1}^{N} (頂点 i に置かれている駒の個数) \times B_i は、19,29,27,29 です。

入力例 2

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

出力例 2

59 66 60 68 76 76 76 

入力例 3

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

出力例 3

81 91 82 96 100 94 96 100 94 

入力例 4

10
2 6 9 5 9 5 6 2 6 6
23957 98539 98777 93417 64636 90740 72538 91432 11805 87997
6580 77845 27752 98108 4695 96373 76155 26842 12878 83118

出力例 4

44227480465 38056928301 30512335897 22545117713 30560451138 30512335897 22545117713 30560451138 30512335897 22545117713 30560451138 

問題文

頂点に 1 から N の、辺に 1 から M の番号がついた N 頂点 M 辺の単純連結無向グラフが与えられます。辺 i は頂点 u_i と頂点 v_i を結んでおり、整数 A_i が書かれています。

いま、頂点 1 にたこさんウインナーがいます。たこさんウインナーは足を 1 本持っています。たこさんウインナーは以下の行動を繰り返すことで頂点 N へ向かおうと考えています。

1. 現在の頂点に接続する辺を 1 つ選ぶ。選んだ辺を辺 i とする。
2. たこさんウインナーの現在の足の本数を x 本として、x \le y かつ y\ \mathrm{OR}\ A_i = A_i を満たすような整数 y を選ぶ。そして、足の本数を y 本に増やし辺 i を渡る。

ここで a\ \mathrm{OR}\ b は a と b のビットごとの論理和を表します。

たこさんウインナーが頂点 N に到達することが可能か判定し、可能な場合、初めて頂点 N にたどり着いたときのたこさんウインナーの足の本数として考えられる最小値と最大値を求めてください。

制約

• 2 \le N \le 2 \times 10^5
• 1 \le M \le 2 \times 10^5
• 1 \le u_i, v_i \le N
• 0 \le A_i \lt 2^{30}
• 入力で与えられるグラフは単純連結
• 入力はすべて整数

入力例 1

4 4
1 2 6
2 3 1
3 4 4
1 4 7

出力例 1

1 7

はじめ、たこさんウィンナーは足が 1 本の状態で、頂点 1 にいます。例えば、以下のように移動することができます。

• 辺 4 を選び、y = 1 とすると足の本数が 1 本の状態で、頂点 4 に移動します。

このように移動すると足の本数が 1 本の状態で頂点 4 に移動できます。また、以下のように移動することもできます。

• 辺 4 を選び、y = 7 とすると足の本数が 7 本の状態で、頂点 4 に移動します。

このように移動すると足の本数が 7 本の状態で頂点 4 に移動できます。これが、頂点 4 に着いたときの足の本数の最小値と最大値を達成する方法です。

入力例 2

4 4
1 2 100
1 3 200
2 4 1
3 4 5

出力例 2

-1 -1

入力例 3

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

出力例 3

1 7

問題文

頂点に 1 から N の番号がついた N 頂点 M 辺の単純無向グラフが与えられます。i 番目の辺は頂点 u_i と 頂点 v_i を結んでいます。

また、X, Y, ? からなる長さ N の文字列 S も与えられます。

頂点集合の部分集合の組 ( X, Y) のうち、以下の条件を満たすものが存在するか判定し、存在する場合一つ求めてください。

• 頂点 i ~ ( 1 \le i \le N ) は X, Y のうち片方にのみ含まれる。
• X による誘導部分グラフにおいて、すべての頂点の次数は奇数である。
• Y による誘導部分グラフにおいて、すべての頂点の次数は偶数である。
• S_i = X ならば頂点 i は X に、S_i = Y ならば頂点 i は Y に属している。

制約

• 1 \le N \le 500
• 0 \le M \le N (N - 1) / 2
• 1 \le u_i, v_i \le N
• 与えられるグラフは単純
• N, M, u_i, v_i はすべて整数
• S は X, Y, ? からなる長さ N の文字列

部分点

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

• S に含まれる ? の個数が 17 個以下であるデータセットに正解した場合 1 点が与えられる。

入力例 1

3 2
1 2
2 3
???

出力例 1

XXY

X = \{ 1, 2 \} , Y = \{ 3 \} とします。
集合 X の部分誘導グラフには、辺 (1, 2) のみが含まれます。よって、頂点 1, 2 の次数はともに 1 です。
集合 Y の部分誘導グラフには、辺が含まれません。よって、頂点 3 の次数は 0 です。
よって、これは条件を満たします。また YXX を出力しても正解となります。

入力例 2

4 6
1 2
1 3
1 4
2 3
2 4
3 4
XXX?

出力例 2

XXXX

入力例 3

4 6
1 2
1 3
1 4
2 3
2 4
3 4
YYYY

出力例 3

-1

入力例 4

10 11
1 5
2 3
2 10
3 6
3 7
4 5
4 9
5 8
6 7
6 10
8 9
?XY??YY???

出力例 4

XXYXXYYXYX

問題文

頂点に 1 から N の番号がついた N 頂点 N 辺の単純連結無向グラフが与えられます。i 番目の辺は頂点 u_i と頂点 v_i を結んでいます。 各頂点にはいくつかの駒が置かれており、頂点 i には A_i 個の駒が置かれています。

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

• 駒が 1 つ以上置かれている頂点 x と、x に隣接する頂点 y を任意に選ぶ。x に置かれている駒を 1 つ y に移動させる。

あなたの目標は、頂点 i (i = 1, 2, \ldots, N) に駒が B_i 個置かれている状態にすることです。目標の達成に必要な操作回数の最小値を求めてください。

制約

• 3\leq N\leq 3\times 10^5
• 1\leq u_i, v_i \leq N (i = 1, 2, \ldots, N)
• 与えられるグラフは単純かつ連結
• 0\leq A_i, B_i \leq 10^6
• \sum_{i = 1}^N A_i = \sum_{i = 1}^N B_i
• 入力はすべて整数

入力例 1

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

出力例 1

3

以下のような順で操作を行うと 3 回の操作で目標を達成できます。

• 頂点 4 の駒を 1 つ頂点 3 に移動させる。
• 頂点 3 の駒を 1 つ頂点 1 に移動させる。
• 頂点 3 の駒を 1 つ頂点 2 に移動させる。

2 回以下の操作では目標を達成できないため、答えは 3 です。

入力例 2

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

出力例 2

29

問題文

けむにく君は N 個のゆがんだサイコロで偏りのない K 面サイコロを再現したいです。

有理数からなる N 行 K 列行列 P = (P_{i,j})_{0 \le i < N,\ 0 \le j < K} のうち、以下を満たすものの個数を 998244353 で割ったあまりを求めてください。

• すべての (i,j) に対して、0 \le P_{i,j} \le 1
• すべての i に対して、\sum_{j=0}^{K-1} P_{i,j} = 1
• 0 \le S < K を満たすすべての整数 S に対して、\displaystyle \sum_{\substack{0 \le j_0, j_1, \dots, j_{N-1} < K \\[0.5mm] j_0 + j_1 + \dots + j_{N-1} = S}} \prod_{0 \le i \lt N} P_{i,j_i} = \frac{1}{K}

制約

• 1 \le N \le 2 \times 10^5
• 1 \le K \le 2 \times 10^5
• 入力はすべて整数

入力例 1

2 2

出力例 1

2

P = \begin{pmatrix} 1 & 0 \\ \frac{1}{2} & \frac{1}{2} \\ \end{pmatrix},\begin{pmatrix} \frac{1}{2} & \frac{1}{2} \\ 1 & 0 \\ \end{pmatrix} が条件を満たします。

入力例 2

10 6

出力例 2

190

入力例 3

123456 54321

出力例 3

997126171

問題文

連勝数に興味のあるけむにく君は以下の問題を作りました。

Max Streak Problem

正整数 N, M と長さ N の数列 W, L が与えられます。

W_i = x であるような i \ (1 \le i \le N) であって「 i \lt j \le N かつ L_j = x であるような j が存在しない」 i の個数を f(x) とします。
このとき \displaystyle \max_{1 \le x \le M} f(x) を求めてください。

ただし、与えられる数列 W, L について 1 \le W_i, L_i \le M および W_i \ne L_i が成立することが保証されます。

しかし、はるるん君はこの問題を簡単すぎると感じたため、次の問題を考えました。

Many Max Streak Problems

長さが N の数列 W, L の組であって Max Streak Problem の入力として考えられるものは、すべてで \big ( M \times (M - 1) \big ) ^ N 通りあります。
それらすべてについての Max Streak Problem の答えの総和を P で割ったあまりを求めてください。

Many Max Streak Problems を解いてください。

制約

• 1 \le N \le 300
  
• 2 \le M \le 300
  
• 10^8 \le P \le 10^9
  
• P は素数
• 入力はすべて整数

部分点

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

• N, M \le 30 を満たすデータセットに正解した場合 1 点が与えられる。

入力例 1

2 2 998244353

出力例 1

6

Max Streak Problem の入力としてありうる (W, L) は以下の 4 通りです。

• ((1, 1),(2, 2)) のとき、答えは 2
• ((1, 2),(2, 1)) のとき、答えは 1
• ((2, 1),(1, 2)) のとき、答えは 1
• ((2, 2),(1, 1)) のとき、答えは 2

となるため、答えは 6 となります。

入力例 2

7 7 202602157

出力例 2

123958978

入力例 3

46 35 924844033

出力例 3

88210081

問題文

長さ N の整数列 A = (A_0, \dots , A_{N-1}) に対し、 f(A) を以下のように定義します。ここで a \ \mathrm{AND} \ b は a と b のビットごとの論理積を表します。

• 頂点に 0 から 2^N-1 の番号がついた 2^N 頂点の重み付き完全グラフ G を考える。ただし、頂点 i と頂点 j を結ぶ辺の重みは \displaystyle A_{\mathrm{popcount}(i \ \mathrm{AND} \ j)} である。このときのグラフ G の最小全域木にふくまれる辺の重みの総和を f(A) と定める。

長さ N の整数列 B = (B_0, \dots , B_{N-1}) が与えられます。B の各要素は -1 または 1 以上 M 以下です。

B の要素のうち、 -1 をすべて 1 以上 M 以下の整数に置き換えて得られる数列 B' は、B に含まれる -1 の個数を q とすると M^q 通りあります。

考えられる B' すべてに対する f(B') の総和を 998244353 で割ったあまりを求めてください。

制約

• 1 \le N, M \le 125000
• B_i は -1 または 1 以上 M 以下の整数

部分点

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

• 1 \le B_i \le M を満たすデータセットに正解した場合 1 点が与えられる。

入力例 1

2 2
-1 2

出力例 1

9

考えられる B' は以下の 2 通りです。

• B' = (1, 2) のとき、辺 (0, 1), (0, 2), (0, 3) からなる全域木が最小全域木の一例で、辺の重みの総和は 3 となります。
• B' = (2, 2) のとき、辺 (0, 1), (1, 2), (2, 3) からなる全域木が最小全域木の一例で、辺の重みの総和は 6 となります。

よって、すべての B' に対する f(B') の総和は 9 となります。

入力例 2

7 7
-1 7 -1 7 -1 7 -1

出力例 2

801052

入力例 3

8 8
5 7 2 4 7 1 8 6

出力例 3

445

問題文

N×N マスのグリッドがあります。上から i 行目、左から j 列目のマスを (i,j)(1≤i,j≤N) と表します。

各マスには整数が 1 つ書かれており、(i,j) には i×j が書かれています。

(1,1) から開始して、右または下のマスへの移動を繰り返すことで (N,N) まで移動する経路を良い経路と呼びます。このとき、良い経路のスコアを「通ったマスに書かれている数字の総和」と定義します。

良い経路のスコアとしてありうる最大の値を M とします。M 以下の整数であって、良い経路のスコアとして現れない最大の値を求めてください。

制約

• 2 \le N \le 1000
• 入力はすべて整数

部分点

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

• N \le 30 を満たすデータセットに正解した場合 1 点が与えられる。

入力例 1

3

出力例 1

20

例として、上の図に示した経路について考えます。

• 赤色の経路のスコアは 1 + 2 + 3 + 6 + 9 = 21 です。
• 青色の経路のスコアは 1 + 2 + 4 + 6 + 9 = 22 です。

その他にも経路は考えられますが、N = 3 の場合 M = 22 です。そして、M 以下の整数であって、経路のスコアとして現れない最大の値は 20 です。

入力例 2

6

出力例 2

152

入力例 3

9

出力例 3

476

問題文

非負整数 x, y, z に対し、 以下の条件をすべて満たす非負整数の組 (a,b,c) の個数を f(x, y, z) と定めます。

• a \ \mathrm{AND} \ b \ \mathrm{AND} \ c = x
• a \ \mathrm{OR} \ b \ \mathrm{OR} \ c = y
• a + b + c = z

ここで a \ \mathrm{AND} \ b は a と b のビットごとの論理積を表し、a \ \mathrm{OR} \ b は a と b のビットごとの論理和を表します。

正整数 N, M と、 0, 1, ? からなる長さ N の文字列 X,Y,Z が与えられます。

X の ? を 0 または 1 に置き換えて得られる文字列を 2 進数の整数と解釈したものとしてあり得る整数全体の集合を S_X とおきます。Y に対する S_Y 、 Z に対する S_Z も同様に定義します。

k = 0, 1, \ldots, M-1 について、以下の問題を解いてください。

• x \in S_X, y \in S_Y, z \in S_Z を満たす整数の 3 つ組 (x, y, z) であって、f(x, y, z) \equiv k \pmod{M} を満たすものが存在するか判定せよ。

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

制約

• 1 \leq T \leq 3000
• 1 \leq N \leq 3000
• 1 \leq M \leq 10^6
• X, Y, Z は 0, 1 , ? からなる長さ N の文字列
• すべてのテストケースにおける N の総和は {3000} 以下
• すべてのテストケースにおける M の総和は 10^6 以下
• N,M は整数

入力例 1

3
3 5
0?1
?01
?11
5 7
?0???
?0?1?
01?10
10 10
0000000000
0000000000
0000000000

出力例 1

11010
1011001
0100000000

1 番目のテストケースについて、S_x = \lbrace 1,3 \rbrace , S_y = \lbrace 1,5 \rbrace , S_z = \lbrace 3,7 \rbrace になります。 k = 0,1,3 について、

• f(3, 1, 3) \equiv 0 \pmod{M} ： 条件を満たす (a,b,c) の組は存在しません。

• f(1, 1, 3) \equiv 1 \pmod{M} ： 条件を満たす (a,b,c) は (1,1,1) の 1 つです。

• f(1, 5, 7) \equiv 3 \pmod{M} ： 条件を満たす (a,b,c) は (1,1,5) , (1,5,1) , (5,1,1) の 3 つです。

のように条件を満たす (x,y,z) が存在することがわかります。

一方、 k = 2,4 について条件を満たすような (x,y,z) は存在しません。

問題文

長さ N の整数列 A = (A_1, A_2, ..., A_N) が与えられます。あなたは以下の操作を 0 回以上行うことができます。

• 1 \leq i \leq N を満たす整数 i を一つ選び、 A_i を -1 倍する。

全ての操作が終了した後に、 A を昇順に並び替えます。このときに A が等差数列となっているような操作方法が存在するか判定し、存在する場合は操作回数の最小値を求めてください。

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

制約

• 1 \leq T \leq 2 \times 10^5
• 1 \leq N \leq 2 \times 10^5
• -{10}^{13} \leq A_i \leq 10^{13}
• すべてのテストケースにおける N の総和は 2 \times 10^5 以下
• 入力はすべて整数

入力例 1

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

出力例 1

2
-1
0
0

1 番目のテストケースでは、 i = 1 と i = 3 で操作を行うことで A = (6, 8, 2, 10, 4)となります。 昇順に並び替えると (2, 4, 6, 8, 10) となり、これは等差数列です。1 回以下の操作で等差数列とすることはできないため、答えは 2 になります。

2 番目のテストケースでは、どのように操作しても昇順に並び替えた列を等差数列とすることができません。

問題文

N 人のボランティアが KeioPC のお手伝いをしてくれます。そこで、色付きのリストバンドを付けてもらい N 人全員を区別することにしました。

全ての人はちょうど M 個のリストバンドを腕につける必要があります。ただし、どの相異なる 2 人のボランティアも、リストバンドの色の多重集合が一致してはいけません。

必要なリストバンドの色数の最小値を求めてください。

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

制約

• 1 \le T \le 10
• 1 \le N \le 10^{18}
• 1 \le M \le 10^{18}
• 入力はすべて整数

入力例 1

7
3 2
12 10
35 4
1000000000000000000 1
18350110 2
19010203 3
20260215 4

出力例 1

2
3
4
1000000000000000000
6058
484
147

1 番目のテストケースについて、例えば赤と青の 2 色のリストバンドを用意して、以下のように付けてもらうと条件を満たします。

• 1 人目には、赤のリストバンドを 2 個付けてもらう。
• 2 人目には、青のリストバンドを 2 個付けてもらう。
• 3 人目には、赤と青のリストバンドを 1 個ずつ付けてもらう。

1 色以下では条件を満たせないため、答えは 2 です。

問題文

長さ N の文字列 S が与えられます。また、空文字列で初期化された 2\times10^5 個の文字列 T_1, T_2, \ldots , T_{200000} があります。
以下の形式で与えられる Q 個のクエリを、与えられた順番に処理してください。
クエリは次の 2 種類のいずれかです。

• タイプ1: 1 k l r の形式で与えられる。T_k を T_k と S の l 文字目から r 文字目までからなる部分文字列をその順に連結したもので置き換える。

• タイプ2: 2 x y の形式で与えられる。 T_x の方が T_y よりも辞書順で大きい場合は > を、小さい場合は < を、等しいならば = を出力する。

制約

• 1 \leq N \leq 2 \times 10^5
• 1 \leq Q \leq 2 \times 10^5
• S は英小文字からなる長さ N の文字列
• 1 \leq k \leq 2 \times 10^5
• 1 \leq l \leq r \leq N
• 1 \leq x,y \leq 2 \times 10^5
• x \neq y
• N,Q,k,l,r,x,y は整数

入力例 1

10 7
keioprocon
1 1 1 4
1 2 5 10
2 1 2
1 3 1 10
1 1 5 10
2 1 3
2 1 4

出力例 1

<
=
>

• 1 番目のクエリ : T_1 を T_1 と keio を連結したもので置き換えます。置き換え後の T_1 は keio になります。
• 2 番目のクエリ : T_2 を T_2 と procon を連結したもので置き換えます。、置き換え後の T_2 は procon になります。
• 3 番目のクエリ : T_1 と T_2 を比較します。T_1 = keio , T_2 = procon であり、辞書順で比較すると T_1 の方が小さいため < を出力します。
• 4 番目のクエリ : T_3 を T_3 と keioprocon を連結したもので置き換えます。置き換え後の T_3 は keioprocon になります。
• 5 番目のクエリ : T_1 を T_1 と procon を連結したもので置き換えます。置き換え後の T_1 は keioprocon になります。
• 6 番目のクエリ : T_1 と T_3 を比較します。T_1 = keioprocon , T_3 = keioprocon であり、辞書順で等しいため = を出力します。
• 7 番目のクエリ : T_1 と T_4 を比較します。T_1 = keioprocon , T_4 は空文字列 であり、辞書順で比較すると T_4 の方が小さいため > を出力します。