問題文

N 行 M 列の 0,1 からなる行列 A=(A_{i,j}) (1\leq i\leq N,1\leq j\leq M) は 2^{NM} 通りありますが、そのうち以下の条件を満たすものの個数を 998244353 で割った余りを求めてください。

• k=1,2,\dots,K のすべてについて、以下の両方が成り立つ。
  • \displaystyle\sum_{i=1}^{x_{k}} \displaystyle\sum_{j=1}^{y_{k}} A_{i,j} が奇数
  • \displaystyle\sum_{i=x_{k}+1}^{N} \displaystyle\sum_{j=y_{k}+1}^{M} A_{i,j} が奇数

制約

• 2\leq N,M\leq 10^9
• 1\leq K\leq 3\times 10^5
• 1\leq x_i< N (1\leq i\leq K)
• 1\leq y_i< M (1\leq i\leq K)
• (x_i,y_i)\ne(x_j,y_j) (i\ne j)
• 入力はすべて整数

入力例 1

3 4
2
2 2
1 3

出力例 1

256

下図上の行列は条件を満たします。しかし、下の行列は条件を満たしません。\displaystyle\sum_{i=1}^{x_1} \sum_{j=1}^{y_1} A_{i,j} が偶数であるためです。

入力例 2

76 38
4
7 6
3 8
20 26
3 28

出力例 2

361562686

答えを 998244353 で割った余りを求めることを忘れないでください。

問題

非負整数の組 W,S が与えられます。

パフィンのパ太郎は、ひとりでカードゲームをしています。カードには、カードw、カードsの2種類あります。

パ太郎は、はじめ、カードwを W 枚、カードsを S 枚持っていて、スコアは 0 です。パ太郎は、すべてのカードを消費するまで、持っているカードのうち 1 枚を消費することを繰り返します。i 番目に消費したカードがカードsのとき、以下の効果が発生します。

• i-1,i-2,i-3 番目に消費したカードのうち、カードwの枚数を x とする。27\times \left(\dfrac{4}{3}\right)^x のスコアを得る。

ただし、便宜上 0 番目以前に消費したカードはカードwでないものとします。

適切な順番でカードを消費したときの、得ることのできるスコアの最大値を求めてください。ただし、求める答えは必ず整数になることが証明できます。

以上の問題を T 個のテストケースについて解いてください。

制約

• 1\leq T\leq 10^4
• 0\leq W,S\leq 10^{16}
• 入力はすべて整数

入力例 1

3
5 3
12 9
2026 328

出力例 1

160
484
20992

最初のテストケースでは、パ太郎はカードw,w,s,s,w,w,w,sの順に消費するのが最適です。このとき、

• 3 番目に消費したカードはカードsなので、2,1,0 番目に消費したカードのうちカードwは 2 枚であることから 27\times\left(\dfrac{4}{3}\right)^2=48 のスコアを得る。
• 4 番目に消費したカードはカードsなので、3,2,1 番目に消費したカードのうちカードwは 2 枚であることから 27\times\left(\dfrac{4}{3}\right)^2=48 のスコアを得る。
• 8 番目に消費したカードはカードsなので、7,6,5 番目に消費したカードのうちカードwは 3 枚であることから 27\times\left(\dfrac{4}{3}\right)^3=64 のスコアを得る。

よって、パ太郎が得ることのできるスコアは 160 です。どのようにカードを消費したとしても、160 より大きいスコアを得ることはできないため、160 が答えです。

問題文

二次元平面上に N 個の点 p_1,p_2,\dots,p_N があります。

p_i は (X_i,Y_i) に位置します。複数の点が同一座標にあることはありません。

以下の条件を満たす点列 p=(p_1,p_2,\dots,p_N) の並び替え q=(q_1,q_2,\dots,q_N) をひとつ構築するか、それが不可能であることを宣言してください。

• 1\leq i\leq N-2 について、点列 q_i,q_{i+1},q_{i+2} が一直線上にあるか、この順に反時計回りとなる。
  • より正確には、q_i の座標を (x_i,y_i) として、(x_{i+1} - x_i)(y_{i+2} - y_{i+1}) - (y_{i+1} - y_i)(x_{i+2} - x_{i+1}) \ge 0 が成り立つ。

以上の問題を T 個のテストケースについて解いてください。

制約

• 1\leq T\leq 100
• 3\leq N\leq 3000
• 0\leq X_i,Y_i\leq 10^9
• (X_i,Y_i)\ne (X_j,Y_j) (i\ne j)
• N の総和は 3000 以下
• 入力はすべて整数

入力例 1

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

出力例 1

6 9 2 3 5 1 8 7 4

問題文

整数 N,X と、長さ N の整数列 A=(A_1,A_2,\dots,A_N) が与えられます。 これから、以下の条件をすべて満たす長さ N の整数列 s=(s_1,s_2,\dots,s_N) を作ります。

• 1\leq s_i\leq X
• s_i\ne A_i (1\leq i\leq N)

s_i=s_{i+1} なる i (1\leq i\lt N) の個数の最大値を求めてください。

制約

• 1\leq N\leq 5\times 10^5
• 2\leq X\leq 10^9
• 1\leq A_i\leq X (1\leq i\leq N)
• 入力はすべて整数

入力例 1

8 3
1 2 2 3 2 1 2 1

出力例 1

5

例えば s=(3,3,1,1,3,3,3,3) とすると s_i=s_{i+1} なる i は 1,3,5,6,7 の 5 個となります。これより多くの i で s_i=s_{i+1} にすることはできないことが示せるので、5 が答えです。

入力例 2

4 8
7 6 3 8

出力例 2

3

例えば s=(5,5,5,5) とするとよいです。

問題文

ルルルタタ型数列を、空でない数列 r,t を用いて、r+r+r+t+t と表せる数列と定義します。

長さ N の正整数列 A=(A_1,A_2,\dots,A_N) が与えられます。Q 個のクエリが与えられるので、順に処理してください。

各クエリでは整数 L,R が与えられるので、(A_L,A_{L+1},\dots,A_{R}) の連続部分列にルルルタタ型数列が存在するか判定してください。

制約

• 1\leq N\leq 5\times 10^5
• 1\leq A_i\leq N (1\leq i\leq N)
• 1\leq Q\leq 5\times 10^5
• 1\leq L\leq R\leq N
• 入力はすべて整数

入力例 1

17
3 3 3 2 2 2 4 3 4 3 4 3 2 2 2 2 2
5
1 5
4 12
2 6
8 15
13 17

出力例 1

Yes
Yes
No
No
Yes

1 個目のクエリについて、(S_1,S_2,S_3,S_4,S_5)=(3,3,3,2,2) はルルルタタ型数列です。r=(3),t=(2) とすると条件を満たします。

2 番目のクエリについて、(S_4,S_5,\dots,S_{12}) の連続部分列 (S_4,S_5,\dots,S_{10})=(2,2,2,4,3,4,3) はルルルタタ型数列です。r=(2),t=(4,3) とすると条件を満たします。

3 番目のクエリについて、(3,3,2,2,2) はルルルタタ型数列ではありませんし、明らかにそれより短いルルルタタ型数列も含まれていません。

4 番目のクエリについて、(3,3,3,2,2) は連続部分列でないことに注意してください。

5 番目のクエリについて、r=t でも構わないことに注意してください。

問題文

整数 N と、長さ N の整数列 A,B が与えられます。

(1,2,\dots,N) を並び替えた数列 C であって、すべての i (1\leq i\leq N) について以下の条件を満たすものが存在するか判定してください。

• C の先頭 i 項を取り出した数列のLIS（最長増加部分列）の長さが A_i である。
• C の先頭 i 項を取り出した数列のLDS（最長減少部分列）の長さが B_i である。

存在するなら、ひとつ構築してください。

制約

• 1 \leq N \leq 5 \times 10^5
• 1 \leq A_i \leq N (1 \leq i \leq N)
• 1 \leq B_i \leq N (1 \leq i \leq N)
• 入力はすべて整数

入力例 1

3
1 1 2
1 2 2

出力例 1

2 1 3 

入力例 2

4
1 1 2 2
1 2 2 3

出力例 2

3 2 4 1 

入力例 3

4
1 2 2 3
1 2 2 2

出力例 3

-1

お知らせ

この問題の想定解が誤っており、実際にはおそらく妥当な時間で解けないことが発覚しました。申し訳ありません。Universal Cupからもこの問題は削除されます。

なお、「宇宙人は最低2人の他の宇宙人と手を繋がなければならない」と条件をつければ妥当な出題であったと感じております。

問題文

x 座標と y 座標がそれぞれ 0 以上 N 未満の整数であるような格子点 (x, y) に宇宙人が立っています（それ以外の場所には存在しません）。

合計 N^2 人の宇宙人はそれぞれ 4 本の手を持っています。距離がちょうど 1 であるような 2 人の宇宙人は、互いに手をつなぐ（双方向の接続を作る）ことができます。

初め、いくつかの宇宙人のペアはすでに手をつないでおり、その状態は以下のように与えられます。

• A_{i,j} = 1 のとき、(i, j) にいる宇宙人と (i, j+1) にいる宇宙人はすでに手をつないでいます（0 \le i < N,\ 0 \le j < N-1）。

• B_{i,j} = 1 のとき、(i, j) にいる宇宙人と (i+1, j) にいる宇宙人はすでに手をつないでいます（0 \le i < N-1,\ 0 \le j < N）。

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

• 距離がちょうど 1 である 2 人の宇宙人を選び、その 2 人に手をつながせる。

これらの操作を適切に行うことで、ちょうど他の 3 人の宇宙人と手をつないでいる宇宙人の数を最大化してください。

制約

• 2 \le N \le 500
• A_{i,j} \in \lbrace 0,1\rbrace （0 \le i < N,\ 0 \le j < N-1）
• B_{i,j} \in \lbrace 0,1\rbrace （0 \le i < N-1,\ 0 \le j < N）
• 入力はすべて整数

入力例 1

4
000
010
010
000
0000
0110
0000

出力例 1

8

図 1 の左側にサンプルの初期状態が示されています。図に示されている通り、追加で 12 回手をつながせることで、合計 8 人の宇宙人がそれぞれちょうど 3 人と手をつないでいる状態にすることができます。これは達成可能な最大値であり、最適です。

入力例 2

7
001110
111011
100110
101111
100001
001001
010110
0101011
1001110
1101000
0001111
0111000
0110111

出力例 2

42

問題文

メモリ制限が特殊であることに注意してください。

T 個のテストケースについて以下の問題を解いてください。

長さ N の整数列 A = (A_0, A_1, \dots, A_{N-1}) が与えられます。
あなたは、配列の長さが 1 になるまで、次のいずれかの操作を繰り返し行います。

• \mathrm{AND} 操作：隣り合う 2 要素 (a, b) を選び、これらをマージして 1 つの要素に置き換える。このとき、新しい要素は a \,\&\, b とする。
• \mathrm{OR} 操作：隣り合う 2 要素 (a, b) を選び、これらをマージして 1 つの要素に置き換える。このとき、新しい要素は a \,|\, b とする。

最終的に配列の要素が 1 つになったとき、その値が 0 でなければなりません。

この条件を満たすような操作列のうち、「\mathrm{OR} 操作」を行う回数の最大値を求めてください。

ただし、そのような操作列が存在しない場合は -1 を出力してください。

制約

• 1 \leq T \leq 2^{12}
• 2 \leq N \leq 2^{13}
• 0 \leq A_{i} < 2^{13}
• 各テストケースにおける N の総和は 2^{13} を超えない
• 入力は全て整数

部分点

この問題では、次の規則で提出に対する得点が定められる。

• 全ての入力ケースで AC を得た場合、満点が得られる。

• そうでなかった場合、m = 1,2 \ldots 12 について次の規則で部分点を得ることができる。

  • 「各テストケースにおける N の総和が 2^m を超えないかつ、A_i < 2^m」という条件を満たす全ての入力ケースで AC を得た場合、追加で m 点を得ることができる。

• 例えば、「各テストケースにおける N の総和が 2^4 (=16) を超えないかつ、A_i < 2^4」という条件を満たす全ての入力ケースで AC を得た場合、1+2+3+4 点、すなわち 10 点を得ることができる。

入力例 1

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

出力例 1

3
0
5
6

この入力には、4 つのテストケースが含まれます。

1 つ目のテストケースについて、次のような手順で 2 番目の操作を 3 回行うことができます。

• 最初、A = (3,0,1,4,1,5) である。
• (A_{3}, A_{4}) に対して \mathrm{OR} 操作を行う。操作後、A = (3,0,5,1,5) となる。
• (A_{1}, A_{2}) に対して \mathrm{AND} 操作を行う。操作後、A = (0,5,1,5) となる。
• (A_{3}, A_{4}) に対して \mathrm{OR} 操作を行う。操作後、A = (0,5,5) となる。
• (A_{2}, A_{3}) に対して \mathrm{OR} 操作を行う。操作後、A = (0,5) となる。
• (A_{1}, A_{2}) に対して \mathrm{AND} 操作を行う。操作後、A = (0) となる。

この操作方法は、最終的に A_{1} = 0 が成立しているため条件を満たします。 \mathrm{OR} 操作を 4 回以上行う方法であって、条件を満たすように操作を行うことはできないため答えは 3 となります。

問題文

横に長いスケートリンクがあります。スケートリンクは L+2 個の区画に分かれていて、左から区画 0,1,2,\dots,L,L+1 と番号が付けられています。区画 0 と区画 L+1 には海に落ちる穴が空いていて、それ以外の区画には穴はありません。

スケートリンクの穴のない区画のうち、N 個の区画にはペンギンがいます。i 番目のペンギンは区画 P_i にいて、ペンギンのいる区画はすべて相異なります。

パフィンのパ太郎は、これから、全てのペンギンが海に落ちるまでペンギンを動かします。具体的には、以下の操作をすべてのペンギンが海に落ちるまで行います。

• 海に落ちていないペンギンを一様ランダムに 1 匹選ぶ。
• 左か右のどちらかを一様ランダムに選び、その選んだ方向に動かす。ペンギンは、以下の条件のどちらかを満たすまで、指定された方に動き続ける。
  • 別のペンギンがいる区画の直前の区画に到達する。
  • 穴のある区画に到達し、海に落ちる。

ただし、海に落ちたペンギンはどの区画にもいないとみなします。また、すべての選択は独立に行われます。

ペンギンが 1 回の操作で区画 i から区画 j まで移動したとき、その操作でのペンギンの移動距離を |i-j| とします。すべてのペンギンが海に落ちるまでの、ペンギンの移動距離の総和の期待値を \bmod 998244353 で求めてください。

以上の問題を T 個のテストケースについて解いてください。

制約

• 1\leq T\leq 100
• 1\leq N\leq 5000
• N\leq L\leq 10^9
• 1\leq P_1\lt P_2\lt \dots \lt P_N\leq L
• 入力はすべて整数

入力例 1

3
1 8
2
4 7638
7 66 333 888
5 21
2 4 9 15 17

出力例 1

499122181
308996191
485077673

1 番目のテストケースでは、パ太郎が 1 番目のペンギンを左に動かすと移動距離は 2 、右に動かすと移動距離は 7 で、どちらにせよペンギンは海に落ちます。よって、移動距離の期待値は \frac{9}{2} です。499122181 \times 2\equiv9\pmod{998244353} ですから、答えは 499122181 です。

2 番目のテストケースでは、例えばパ太郎がはじめに 4 番目のペンギンを左に動かすと、4 番目のペンギンは区画 334 に移動し、このときの移動距離は 554 です。もちろん、それ以外にもペンギンを動かす方法は複数存在し、パ太郎はそのうち一様ランダムに 1 つ選びます。

問題文

正整数 N 、素数 P 、長さ N の P 未満の要素からなる正整数列 A=(A_1,A_2,\dots,A_N) が与えられます。

S=\lbrace 1,2,\dots,N\rbrace とします。

以下の条件をすべて満たす長さ 1 以上の集合の列 T の個数を P で割った余りを求めてください。

• T の要素はすべて S の空でない部分集合
• i=1,2,\dots,N について、以下が成り立つ
  • T の要素のうち、i を含むものはちょうど A_i 個

制約

• 1\leq N\leq 2\times 10^5
• 113\leq P\leq 500009
• P は素数
• 1\leq A_i\lt P (1\leq i\leq N)
• 入力はすべて整数

入力例 1

2 113
1 2

出力例 1

5

T としてありうるのは (\lbrace 1,2\rbrace,\lbrace 2\rbrace),(\lbrace 2\rbrace,\lbrace 1,2\rbrace),(\lbrace 1\rbrace,\lbrace 2\rbrace,\lbrace 2\rbrace),(\lbrace 2\rbrace,\lbrace 1\rbrace,\lbrace 2\rbrace),(\lbrace 2\rbrace,\lbrace 2\rbrace,\lbrace 1\rbrace) の 5 通りです。

入力例 2

4 8191
7 6 3 8

出力例 2

4477

T の個数を P で割った余りで求めることを忘れないでください。

問題文

N 人が、声優のトークイベントに申し込みました。このイベントはチケットを 1 枚以上 4 枚以下買うことで申し込むことができ、チケットを i 枚 (1\leq i\leq 4) 買った人は T_i 人います。ここで、人はチケットの枚数のみで区別し、同じ枚数の人は区別しません。

このトークイベントでは、抽選に当選すれば買ったチケットの枚数と同じ単位時間だけ声優と話すことができます。

イベントの時間は X 単位時間です。乱数を司る神であるパフィンのパ太郎は、当選者をイベントの時間に収まるように選びます（言い換えると、当選者の買ったチケットの枚数の合計が X 以下になるように選びます）。ただし、当選しなかった人から不満が出てはいけないので、以下の条件を満たすようにします。

• どの当選していない人についても、その人を追加で当選させるとイベントの時間に収まらなくなる。

当選者をちょうど K 人選ぶ通り数を 998244353 で割った余りを求めてください。

以上の問題を \text{TESTCASES} 個のテストケースについて解いてください。

制約

• 1\leq \text{TESTCASES}\leq 10^4
• 1\leq K\leq N\leq 2.5\times 10^8
• 1\leq X\leq 10^9
• 0\leq T_i (1\leq i\leq 4)
• T_1+T_2+T_3+T_4=N
• 入力はすべて整数

入力例 1

2
24 8 11
7 6 3 8
24 3 28
7 6 3 8

出力例 1

4
0

チケットを i 枚買った人のうち抽選に当たった人数を t_i とします。最初のテストケースでは、以下の 4 通りの選び方があります。

• (t_1,t_2,t_3,t_4)=(5,3,0,0)
• (t_1,t_2,t_3,t_4)=(6,1,1,0)
• (t_1,t_2,t_3,t_4)=(7,0,0,1)
• (t_1,t_2,t_3,t_4)=(7,0,1,0)

2 番目のテストケースでは、条件を満たす選び方は存在しません。

問題文

N \times N のグリッドがあります。それぞれのマスには 1 つずつ整数が書かれており、マス (i, j) には A_{i,j}（1 \le A_{i,j} \le (N - K)^2）が書かれています。

パンダのパ太郎はこのグリッドに対して次のような操作を行いました。

• N 行の中から K 個の行を選び、これらを削除する。
• N 列の中から K 個の列を選び、これらを削除する。

操作を行った結果、残った (N - K)^2 個の数字がすべて異なるものだったと言います。

パ太郎が行った操作として考えられるものの通り数を 998244353 で割った余りを求めてください。

ただし、2 つの操作が異なるとは、上記の 2 つの操作のうち少なくとも片方で選んだ行または列の集合が異なる場合、またその場合に限ります。

制約

• 1 \le K < N \le 1000
• K \le 5
• 1 \leq A_{i,j} \leq (N-K)^2
• 入力は全て整数

入力例 1

3 1
1 2 4
3 4 2
2 1 3

出力例 1

6

次の 6 通りの操作方法が条件を満たします。これらの操作をそれぞれ行うことで、残った (N-K)^2 個の数字は小さい順に 1,2,3,4 となります。

• 1 つ目の操作で 1 行目を選び、2 つ目の操作で 1 列目を選ぶ。
• 1 つ目の操作で 1 行目を選び、2 つ目の操作で 3 列目を選ぶ。
• 1 つ目の操作で 2 行目を選び、2 つ目の操作で 1 列目を選ぶ。
• 1 つ目の操作で 2 行目を選び、2 つ目の操作で 2 列目を選ぶ。
• 1 つ目の操作で 3 行目を選び、2 つ目の操作で 2 列目を選ぶ。
• 1 つ目の操作で 3 行目を選び、2 つ目の操作で 3 列目を選ぶ。

入力例 2

6 5
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1

出力例 2

36

入力例 3

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

出力例 3

36

問題文

(1,2,\dots,N) の順列 P であって、以下の条件を満たすものが存在するかどうか判定してください。存在する場合、一つ構築してください。

• 整数 1 \le i < j < k \le N であって P_i < P_j < P_k を満たすものの個数と、整数 1 \le i < j < k \le N であって P_i > P_j > P_k を満たすものの個数が等しい。

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

制約

• 1 \le T \le 5 \times 10^5
• 3 \le N \le 5 \times 10^5
• テストケース中の N の合計は 5 \times 10^5 以下である。
• 入力はすべて整数である。

入力例 1

2
3
4

出力例 1

1 3 2 
2 4 1 3 

一つ目のテストケースについて、順列 (1,3,2) は、単調増加でも単調減少でもありません。よって、条件を満たしています。

二つ目のテストケースについて、例えば順列 (2,4,1,3) を考えると、(P_i,P_j,P_k) の値の組として考えられるものは、(2,4,1),(2,4,3),(4,1,3),(2,1,3) がありますが、これらの三つ組はすべて単調増加でも単調減少でもありません。よって、条件を満たしています。

Universal Cup参加者へ

この問題は Universal Cup に収録される際に削除されます。そのため、Universal Cup に AtCoder での結果を使用する場合はこの問題以外を先に解くことをおすすめします。

問題文

この問題はインタラクティブな問題です。

X 種類のアクリルスタンドを売る物販があります。はじめ、i 種類目のアクリルスタンドは A_i 個の在庫があります。

これから、N 人の客が来ます。客は以下の 2 種類いるので、順に処理してください。

• 単品で購入する人。在庫のうちどれか 1 つ選んで売ってください。
• コンプリートセットを購入する人。すべての種類のアクリルスタンドを 1 個ずつ売ってください。

ただし、在庫がなく売れない場合はその事を報告してください（在庫があるのに売れないと報告することは許されません）。また、過去の売り方を変えていればその客に売れるような場合があってはいけません。

制約

• 2\leq X\leq 20
• 1\leq N\leq 2000
• 1\leq A_i\leq 100
• 入力はすべて整数

入出力

最初に、X,N,A が標準入力から与えられます。

X N
A_1 A_2 \dots A_X

次に、ちょうど N 回、以下に示す客とのやりとりを繰り返してください。

まず、正整数 T が与えられます。

T

ここで、T は -1 または 1 または 2 で、

• T=1 のとき、単品を買う客が来たことを表します。
• T=2 のとき、コンプリートセットを買う客が来たことを表します。
• T=-1 のとき、これまでのやりとりが形式に沿っていないことを表します。
  • このとき、プログラムはすでに不正解と判定されています。ただちにプログラムを終了してください。

単品を買う客が来た場合、-1 または 1 以上 X 以下の整数 s を出力してください。

s

-1 を出力した場合、売れないと報告したことを表します。このとき、実際には売れる場合、または過去の売り方を変えていれば売れた場合、形式に沿っていないと判定されます。

それ以外の場合、s 種類目のアクリルスタンドを売ったことを表します。s 種類目のアクリルスタンドの在庫がない場合、形式に沿っていないと判定されます。

コンプリートセットを買う客が来た場合、-1 または 1 である整数 c を出力してください。

c

-1 を出力した場合、売れないと報告したことを表します。このとき、実際には売れる場合、または過去の売り方を変えていれば売れた場合、形式に沿っていないと判定されます。

1 を出力した場合、全種類のアクリルスタンドを売ったことを表します。在庫のないアクリルスタンドの種類がある場合、形式に沿っていないと判定されます。

N 人の客に対処すると、正整数 J が与えられます。

J

ここで、J は 1 または -1 で、

• J=1 のとき、すべての客を正しく処理できたことを表します。この後ただちにプログラムを終了することで、正解と判定されます。
• J=-1 のとき、これまでのやりとりが形式に沿っていないことを表します。
  • このとき、プログラムはすでに不正解と判定されています。ただちにプログラムを終了してください。

以上の形式に沿っていない出力をした場合、-1 が入力から与えられます。

-1

このときも、プログラムは不正解と判定されています。ただちにプログラムを終了してください。

注意点

• 出力を行うたびに、末尾に改行を入れて標準出力をflushしてください。そうしなかった場合、ジャッジ結果が TLE となる可能性があります。
• すべての客を処理したとき、または -1 を標準入力から受け取ったとき、ただちにプログラムを終了してください。そうしなかった場合の判定結果は不定です。
• 余計な改行は不正なフォーマットの出力とみなされることに注意してください。
• この問題のジャッジシステムは適応的（adaptive）です。 つまり、ジャッジは過去のやり取りによって来る客の種類を変える可能性があります。

入出力例

X=3,N=5,A=(2,3,3) のときの対話の一例を示します。

これは対話の一例であることに注意してください。

Universal Cup参加者へ

この問題は Universal Cup に収録される際に削除されます。そのため、Universal Cup に AtCoder での結果を使用する場合はこの問題以外を先に解くことをおすすめします。

問題文

整数 G と、0 と 1 からなる文字列 S が与えられます。

ある0 と 1 からなる空でない文字列が、

• キリン文字列であるとは、長さが G 以上であることを指します。
• シマウマ文字列であるとは、同じ文字が隣り合っている部分が存在しないことを指します（長さ 1 の文字列はシマウマ文字列です）。
• オカピ文字列であるとは、キリン文字列でもシマウマ文字列でもないことを指します。

Q 個のクエリを処理してください。i 番目のクエリでは、整数 L_i,R_i,T_i が与えられるので、以下のクエリに答えてください。

• S の L_i 文字目から R_i 文字目を取り出した文字列の中に含まれる部分文字列のうち、
  • T_i=1 のとき、キリン文字列の数を答えよ。
  • T_i=2 のとき、シマウマ文字列の数を答えよ。
  • T_i=3 のとき、オカピ文字列の数を答えよ。

ただし、同じ文字列でも取り出す場所が違えば異なる部分文字列として扱います。

制約

• 1\leq G\leq |S|
• 1\leq |S| \leq 2\times 10^5
• S は 0 と 1 からなる
• 1\leq Q\leq 2\times 10^5
• 1\leq L_i\leq R_i\leq N
• 1\leq T_i\leq 3
• G,Q,L_i,R_i,T_i は整数

小課題

1. (10 点) T_i=1
2. (50 点) T_i=2
3. (40 点) 追加の制約はない。

入力例 1

3
010010
3
1 6 1
1 6 2
1 6 3

出力例 1

10
12
1

Universal Cup参加者へ

この問題は Universal Cup に収録される際に削除されます。そのため、Universal Cup に AtCoder での結果を使用する場合はこの問題以外を先に解くことをおすすめします。

問題文

頂点に 1 から N の番号が付けられた N 頂点の木が与えられます。i 番目の辺は頂点 u_i と頂点 v_i を結んでいます。この木の上で、AliceとBobがゲームをします。 はじめ、Aliceは頂点 a に、Bobは頂点 b にいます。頂点 a は赤色で、頂点 b は青色で塗られており、それ以外の頂点は色が塗られていません。

Aliceを先手として、AliceとBobは以下の操作を交互に行います。この操作は、各プレイヤーがそれぞれちょうど 10^{100} 回ずつ行うまで繰り返されます。

• 今自分がいる頂点と隣接する頂点を 1 つ選び、その頂点に移動する。その後、移動した先の頂点の色を、自分がAliceの場合は赤色に、Bobの場合は青色に塗り替える（すでに色が塗られている場合も上書きする）。

すべての操作が終了したとき、赤色で塗られた頂点の個数よりも青色で塗られた頂点の個数の方が多いならば Bob の勝利となり、そうでない（赤色で塗られた頂点の個数が青色で塗られた頂点の個数以上である）ならば Alice の勝利となります。

両者が自身の勝利のために最適な行動をとったとき、どちらが勝つか判定してください。

制約

• 2 \le N \le 2 \times 10^5
• 1 \le a, b \le N
• a \neq b
• 1 \le u_i, v_i \le N
• 与えられるグラフは木である。
• 入力はすべて整数である。

入力例 1

5 1 5
4 3
4 5
3 2
2 1

出力例 1

Bob

入力例 2

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

出力例 2

Bob

Universal Cup参加者へ

この問題は Universal Cup に収録される際に削除されます。そのため、Universal Cup に AtCoder での結果を使用する場合はこの問題以外を先に解くことをおすすめします。

問題文

T 個のテストケースについて、以下の問題を解いてください。

この森は 2 行 N 列のグリッドとみなすことができます。それぞれのマスには「トゲトゲ度」と呼ばれる正整数が定められており、上から i 行目、左から j 列目のマスを (i,j) とすると、そのトゲトゲ度は T_{i,j} です。

植物を司る神であるけいすけさんは、神力「伐採」を 1 回行うことで次の操作を行うことができます。

• トゲトゲ度が正であるマス (a,b)（1 \leq a \leq 2,\ 1 \leq b \leq N）を 1 つ選び、そのマスのトゲトゲ度を 1 減らす。ただし、トゲトゲ度を負にすることはできない。

はるくさんは現在マス (1,1) におり、右または下に隣接するマスへの移動を繰り返して、マス (2,N) に到達したいと考えています。

このとき、けいすけさんが事前に適切に伐採を行うことで、はるくさんの取りうるすべての経路に対して、その経路上にある全てのマス（(1,1) および (2,N) を含む）のトゲトゲ度の総和が S 以下となるようにしたいです。

けいすけさんがこの条件を満たすために使うべき伐採の回数の最小値を求めてください。

制約

• 1 \le T \le 2 \times 10^5
• 1 \le N \le 2 \times 10^5
• 1 \le S \le 2 \times 10^{14}
• 1 \le T_{i,j} \le 10^9
• 各テストケースの N の総和は 2 \times 10^5 以下
• 入力はすべて整数

入力例 1

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

出力例 1

13
0
39

この入力には、3 つのテストケースが含まれます。

1 つ目のテストケースについて、初期状態は次のような状態です。

1 2 3
4 5 6

けいすけさんが次のように「伐採」を 13 回行うことによって、森のマスのトゲトゲ度を

0 1 3
4 0 0

のようにすることができます。

• マス (1,1) に 1 回伐採を行う。
• マス (1,2) に 1 回伐採を行う。
• マス (2,2) に 5 回伐採を行う。
• マス (2,3) に 6 回伐採を行う。

このとき、右または下に隣接するマスへの移動を繰り返し (1,1) から (2,3) へ移動する任意の方法において、通るマスのトゲトゲ度の合計値は 4 以下になるので、これは条件を満たします。

12 回以下の伐採によって条件を満たすことはできないので、答えは 13 になります。

Universal Cup参加者へ

この問題は Universal Cup に収録される際に削除されます。そのため、Universal Cup に AtCoder での結果を使用する場合はこの問題以外を先に解くことをおすすめします。

問題文

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

頂点に 1 から N の番号がついた，頂点 1 が根の根付き木であって，以下を満たすものの個数を 998244353 で割った余りを求めてください．

• 頂点 i(1 \leq i \leq N) の部分木を構成する頂点の番号はすべて i 以上である．

ただし， 2 つの根付き木が異なるとは，ある 2 つの頂点の組 u,v(1 \leq u,v \leq N) が存在して，片方の根付き木では u,v 間に辺が貼られているが，もう片方の根付き木では辺が貼られていないということを指します．

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

制約

• 1 \leq T \leq 5 \times 10^{5}
• 1 \leq N \leq 5 \times 10^{5}
• 入力はすべて整数

入力例 1

3
4
1
1000

出力例 1

6
1
815987315

この入力には， 3 つのテストケースが含まれます．