問題文

パ研王国は N 個の街とそれを繋ぐ M 本の道路からなります。街には標高が高い順に 1, 2, \ldots, N の番号がついており、全ての道路は標高が高い街から低い街へ一方向に移動することができます。具体的には、 i 番目の道路は街 A_i から街 B_i への一方向に移動することができます (A_i < B_i) 。

さて、今年もパ研合宿が開催されます。今年のパ研合宿ではいくつかの街に会場を設け、パ研王国のどの街からでも 0 本以上の道路を通ることで会場のある街に移動できるようにします。

しかし、予算に制約があるため、会場を設ける街をできるだけ少なくしたいです。このとき、会場を設ける街の集合を一つ定めて下さい。

制約

• 入力は全て整数
• 1 \leq N \leq 10^5
• 0 \leq M \leq 2 \times 10^5
• 1 \leq A_i < B_i \leq N (1 \leq i \leq M)

入力例 1

4 4
1 2
1 3
1 4
2 4

出力例 1

2
3 4

この出力例の場合、それぞれの街からは、次のように会場のある街に移動できます。

• 街 1 からは街 3, 4 に移動できる
• 街 2 からは街 4 に移動できる
• 街 3 からは街 3 に移動できる
• 街 4 からは街 4 に移動できる

また、会場を 1 つ以下の街に設けて、全ての街から会場のある街に移動することはできないため、この出力は条件を満たします。

入力例 2

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

出力例 2

2
9 10

問題文

パ研学園では各年度に N 個の学期があり、 1, 2, \ldots, N の番号が付いています。各学期ごとに成績が付き、成績は 1 から N までの整数値で表されます。

さて、パ研学園の生徒であるあなたは、一年の最後に自分の各学期の成績表を眺めていました。すると、次のことに気が付きました。ここで i 番目の学期の成績を G_i とします。

• G は長さ N の順列である。
• 2 学期以降について、前の学期より成績が下がっている学期が存在し、それらは連続する 1 つの区間になっている。

このとき、これらの条件を満たす成績 G_1, G_2, \ldots, G_N の個数を求めて下さい。ただし、答えはとても大きくなることがあるので、答えを 998244353 で割った余りを出力してください。

制約

• 入力は全て整数
• 2 \leq N \leq 10^{18}

小課題

1. (50 点) N \leq 8
2. (50 点) N \leq 15
3. (200 点) N \leq 3000
4. (100 点) N \leq 10^6
5. (100 点) 追加の制約はない

入力例 1

4

出力例 1

18

順列である G のうち、 G_1 < G_2 < G_3 < G_4 の時と G_1 > G_2 < G_3 > G_4 の時のみが条件を満たしません。

そのような G は (1, 2, 3, 4), (2, 1, 4, 3), (3, 1, 4, 2), (3, 2, 4, 1), (4, 1, 3, 2), (4, 2, 3, 1) の 6 つあります。長さ 4 の順列は 24 個あるため、答えは 18 になります。

この入力は全ての小課題の制約を満たします。

入力例 2

13

出力例 2

398574

この入力は小課題 2, 3, 4, 5 の制約を満たします。

入力例 3

2947

出力例 3

663703367

この入力は小課題 3, 4, 5 の制約を満たします。

入力例 4

999999

出力例 4

946508973

この入力は小課題 4, 5 の制約を満たします。

入力例 5

1000000000000000000

出力例 5

856673235

この入力は小課題 5 の制約を満たします。

問題文

パ研町にはパ研美術館とこまば美術館があります。それぞれの美術館には N 個の美術品が一列に展示されており、パ研美術館の左から i 番目の美術品の価値は A_i で、こまば美術館の左から i 番目の美術品の価値は B_i です。来場者をより楽しませるために、美術品は左から右に向かって価値の低い物から高い物の順に並んでいます。

パ研美術館とこまば美術館はコラボ展示をすることになりました。コラボには Q 個のプランがあり、 i 番目のプランでは、パ研美術館の左から L_i 番目から R_i 番目の美術品と、こまば美術館の左から X_i 番目から Y_i 番目の美術品を展示します。コラボ展示でも同様に、美術品は左から右に向かって価値の低い物から高い物の順に並べます。

ある展示の満足度を、隣り合う美術品の価値の差の最小値としましょう。各 i \ (1 \leq i \leq Q) について、 i 番目のプランで展示を行った際の満足度を求めてください。

制約

• 入力は全て整数
• 1 \leq N \leq 200000
• 1 \leq A_1 \leq A_2 \leq \cdots \leq A_N \leq 10^{18}
• 1 \leq B_1 \leq B_2 \leq \cdots \leq B_N \leq 10^{18}
• 1 \leq Q \leq 200000
• 1 \leq L_i \leq R_i \leq N \ (1 \leq i \leq Q)
• 1 \leq X_i \leq Y_i \leq N \ (1 \leq i \leq Q)

小課題

1. (50 点) N, Q \leq 1000
2. (150 点) \max(A_{L_i}, B_{X_i}) > \min(A_{R_i}, B_{Y_i}) \ (1 \leq i \leq Q)
3. (400 点) 追加の制約はない

入力例 1

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

出力例 1

1
1
1
0

1 番目のプランでは、並ぶ美術品の価値は順に 1, 2, 3, 4, 6, 7, 8, 9, 10, 11 です。この場合隣り合う展示品の価値の差の最小値は 1 となります。

この入力例は小課題 1, 3 の制約を満たします。

入力例 2

10
4 14 18 31 47 51 59 72 78 96
2 23 25 36 58 60 63 85 88 97
7
1 3 5 5
6 10 3 4
8 10 1 4
7 10 2 4
6 7 1 3
2 4 6 9
2 3 2 9

出力例 2

4
6
2
2
2
3
2

この入力例は全ての小課題の制約を満たします。

入力例 3

15
1141 1334 2083 2504 4031 4238 4328 5260 5315 6427 6991 8127 8199 8356 9136
189 403 1035 1126 1165 1477 2021 2100 2528 3892 4108 4459 5792 7050 8709
8
4 7 7 15
8 11 8 11
7 11 2 15
2 13 6 11
11 12 3 10
8 10 3 12
3 11 3 10
3 11 8 10

出力例 3

24
55
39
17
39
39
17
17

この入力例は小課題 1, 3 の制約を満たします。

問題文

0 と 1 からなる長さ N の文字列であって 1 以上 M 以下の全ての整数 i について次の条件を満たすものの個数を 998244353 で割った余りを求めてください。

• L_i 文字目から R_i 文字目の間に文字 C_i が存在する

制約

• 1\leq N\leq 2\times 10^5
• 1\leq M\leq 2\times 10^5
• 1\leq L_i\leq R_i\leq N\,(1\leq i\leq M)
• C_i\in\lbrace 0,1\rbrace\,(1\leq i\leq M)
• 入力は全て整数

小課題

1. (50 点) N\leq 16, M\leq 16
2. (100 点) N\leq 2000, M\leq 2000, C_i=0\,(1\leq i\leq M)
3. (150 点) C_i=0\,(1\leq i\leq M)
4. (300 点) 追加の制約はない

入力例 1

3 2
1 3 0
1 2 1

出力例 1

5

010、011、100、101、110 の 5 つが条件を満たす文字列です。

入力例 2

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

出力例 2

13

10101 や 00000 など合計 13 個の文字列が条件を満たします。

入力例 3

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

出力例 3

13

問題文

パ研楽団には、 N 人の演奏者がいます。また、パ研楽団は M 種類の楽器を所有しています。i 人目の演奏者の熟練度は A_i で担当楽器は B_i 、楽器の移行コストは C_i です。i 人目の演奏者は C_i の移行コストで担当の楽器を好きなものに変更することができます。

楽団の調和度を以下のように定義します。

• M 種類の楽器それぞれについて、その楽器を担当する人の熟練度の最大値を考える。この M 個の値の最小値が調和度である。ただし、担当する人がいない楽器が存在する場合、調和度は 0 である。

x = X_1, X_2, \ldots ,X_Q について、移行コストの総和が x を超えずに実現できる最大の調和度を求めてください。

制約

• 1 \leq M \leq N \leq 2 \times 10^5
• 1 \leq Q \leq 2 \times 10^5
• 1 \leq A_i \leq 10^9 \ (1 \leq i \leq N)
• 1 \leq B_i \leq M \ (1 \leq i \leq N)
• 0 \leq C_i \leq 10^9 \ (1 \leq i \leq N)
• 0 \leq X_1 < X_2 < \cdots < X_Q \leq 2 \times 10^{14}
• 入力は全て整数

小課題

1. (150 点) N, Q \leq 2000
2. (150 点) M \leq 10
3. (300 点) 追加の制約はない

入力例 1

5 3
7 1 4
10 3 3
8 3 3
9 3 5
7 1 4
6
2 9 12 15 25 46

出力例 1

0
8
8
8
8
8

例えば人 2 の担当楽器を 2 に、人 3 の担当楽器を 1 にすると調和度は 8 になります。このときかかるコストは C_2+C_3=6 です。

誰一人担当楽器を変えないと、調和度は 0 になります。このときかかるコストは 0 です。

入力例 2

10 6
10 3 4
12 2 5
2 1 3
7 3 15
12 1 10
8 3 3
11 3 14
13 6 9
3 3 12
4 5 1
10
1 3 7 37 53 85 88 91 94 148

出力例 2

0
4
8
8
8
8
8
8
8
8

問題文

パ研君は、次の問題を解いています。

N 頂点の木が与えられる。頂点には 1, 2, \ldots, N の番号が付けられている。

各頂点について、その頂点から最も離れた頂点を一つ求めよ。複数ある場合はどれを求めてもいい。

パ研君はこの問題を解き、 1 \leq i \leq N について頂点 i から最も離れた頂点のうち一つが頂点 A_i であると分かりました。

しかしなんという事でしょう、せっかく問題を解けたのに、元の木や A の一部の値が分からなくなってしまいました。あなたはパ研君のために、数列 A を復元してあげたいと考えました。

今あなたには長さ N の数列 B が与えられます。この数列は残っている A の情報を表しています。このとき、次の全ての条件を満たす長さ N の数列 A を考えます。

• B_i \neq -1 ならば A_i = B_i である
• ある木が存在し、 1 \leq i \leq N について、頂点 i から最も離れた頂点の一つが頂点 A_i である

このような条件を満たす A がいくつあるか、パ研君に教えてあげてください。ただし、パ研君が問題を解き間違えていた可能性があるため、条件を満たす A が存在しない場合もあります。

なお、答えは大きくなる場合があるので、代わりに答えを 998244353 で割ったあまりを求めて下さい。

制約

• 入力は全て整数
• 1 \leq N \leq 2 \times 10^5
• 1 \leq B_i \leq N または B_i = -1 (1 \leq i \leq N)

小課題

1. (100 点) B_i \neq -1 (1 \leq i \leq N)
2. (100 点) 1 \leq N \leq 20
3. (100 点) 1 \leq N \leq 2000
4. (300 点) 追加の制約はない

入力例 1

3
2 -1 -1

出力例 1

3

A=(2, 1, 1), (2, 1, 2), (2, 3, 2) の 3 通りが考えられます。

この入出力例は小課題 2, 3, 4 の制約を満たします。

入力例 2

8
-1 8 7 5 -1 1 2 3

出力例 2

47

この入力例は小課題 2, 3, 4 の制約を満たします。

入力例 3

4
1 2 3 4

出力例 3

0

どうやらパ研君は問題を解き間違えていたようですが、この入力例は全ての小課題の制約を満たします。

問題文

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

パ研町には N 戸の家があり、 1, 2, \ldots, N の番号が付いています。また家と家を双方向に結ぶ 0 本以上の道路があり、道路は 300 本以下であることが分かっていますが、何本あるかや、それぞれの道路がどの家とどの家を結んでいるかは分かりません。ただし、両端が同じ家を結んでいる道路はなく、複数の道路が同じ家の組を結んでいることもありません。

パ研町の町長となったあなたは、これから毎日 1 回ずつ集会を開きます。 N 戸の家それぞれについて、その家の住人を招待するかしないか決めることができます。

しかし、パ研町は非常に険悪な町です。特に隣人、つまり 1 つの道路で結ばれた 2 つの家に住む住人は、集会で顔を合わせるだけで集会の全員を巻き込んだ乱闘が起きてしまいます。

さて、あなたはパ研町の道路の本数や、それぞれの道路がどの家とどの家を結んでいるかを調べたいと思いました。そこで、各日に集会に招待する人を工夫し、乱闘が起きるかどうかを調べることで、パ研町の構造を調べることにしました。

これは明らかに職権濫用なので、 3200 日間までしか集会を開けません。集会に招待する人を決める戦略を定めるプログラムを作成してください。

なお、あなた自身は誰とも隣人でないものとします。また、誰も呼ばずに一人で集会を行うこともできます。

制約

• N は整数
• 1 \leq N \leq 200
• 道路は 300 本以下である。
• 両方の端が同じ 1 つの家となっている道路はない
• 複数の道路が同じ家の組を結んでいることはない

小課題

1. (50 点) N \leq 80
2. (100 点) どの道路についても、その道路が結ぶ 2 つの家の番号の偶奇が異なる
3. (150 点) どの家 a, b, c についても、 a と b を結ぶ道路が存在し、 a と c を結ぶ道路が存在しない場合、 b と c を結ぶ道路が存在する
4. (400 点) 追加の制約はない

入出力

最初に、 N が以下の形式で入力で与えられる。

N

次に、あなたは質問を繰り返しすることができる。この質問の回数は 3200 回以下である必要がある。

? S

ただし、 S は 0 と 1 からなる長さ N の文字列であり、 S_i = 0 の場合家 i の住人を集会に呼ばないことを、 S_i = 1 の場合家 i の住人を集会に呼ぶことを表す。

その後、ジャッジが質問に対する回答をする。この返答は次のいずれかの文字列である。

• Yes : 集会参加者全員を巻き込んだ乱闘が起きた。
• No : 乱闘は起きなかった。
• -1 : 不正な質問や不正な出力を行った。これは質問回数が 3200 回を超えた場合を含む。

また、パ研町の構造が分かった場合、全ての道路を以下の形式で出力せよ。

! M
a_1 b_1
a_2 b_2
\vdots
a_M b_M

ここで M は道路の本数を表し、 i 本目の道路が家 a_i, b_i を結んでいることを示している。

ただし、道路を出力する順番はどれでも構わない。また、 a_i, b_i が逆になっていても構わない。

注意

• 出力の度に標準出力を flush せよ。そうしない場合、ジャッジ結果は不定である。
• 全ての道路を出力した後プログラムを終了させなかった場合、ジャッジ結果は不定である。
• 不正な質問や不正な出力を行った場合、ジャッジ結果は不定である。

入出力例

この入出力例では、 N=4 で道路が 4 本あり、それぞれの道路が家 1, 2 、家 2, 3 、家 3, 4 、家 4, 1 を結ぶ場合のジャッジとのやり取りの一例を示している。

ただしこれはあくまで入出力例であり、意味のあるやり取りをしているとは限らないことに注意せよ。

なお、この入力例は全ての小課題の制約を満たす。

問題文

パ研部員が一列に N 人並んでいます。左から i \ (1 \leq i \leq N) 番目の部員を部員 i と呼ぶことにします。現在の部員 i のパソコン力は A_i です。隣り合う部員同士には仲良し度という指標が存在し、 1 \leq i \leq N - 1 について現在の部員 i と部員 i + 1 の仲良し度は B_i です。ここで B_i は相異なります。

パ研部員は派閥争いが大好きです。普段は派閥争いが禁止されていますが、万が一派閥争いが起こってしまったときのことを考えてみましょう。

人 l, l + 1, \cdots , r \ (1 \leq l \leq r \leq N) が派閥争いを始めると、以下の事柄が起こります。

• はじめ、派閥 l, l + 1, \cdots ,r が存在し、部員 i \ (l \leq i \leq r) は派閥 i に属する。それ以外の部員は派閥に属さない。
• 派閥 a, b \ (l \leq a < b \leq r) の仲良し度は、以下のように定義される。

  どの時点においても、派閥 a に人 i が所属し、派閥 b に人 i+1 が所属しているような i は高々 1 つ存在することが証明できる。仲良し度は、このような i が存在しない場合 -10^{100} であり、存在する場合 B_i である。

• 派閥が 1 つになるまで、以下のイベントが繰り返される。

  仲良し度が最大である 2 派閥 a, b \ (a < b) を考える。各派閥に所属する人のパソコン力の総和を s, t とする。このとき s \geq t なら派閥 b に所属する人が全員派閥 a に所属を変え、 s < t なら派閥 a に所属する人が全員派閥 b に所属を変える。また、所属する人がいなくなった派閥は消滅する。

パ研の活動は明日からの Q 日の間活発なので、部員のパソコン力や仲良し度は頻繁に変わります。具体的には、 j \ (1 \leq j \leq Q) 日目には以下の変化が起こります。

• T_j = 1 の場合、部員 P_j のパソコン力が V_j になる。
• T_j = 2 の場合、部員 P_j と部員 P_j + 1 の間の仲良し度が V_j になる。

ただし、いずれの時点においても部員同士の仲良し度は相異なることが保証されます。

派閥争いを想像するのが大好きな派閥太郎君は、毎日派閥争いの思考実験を行います。具体的には、 j \ (1 \leq j \leq Q) 日目の終わりには、部員 L_j, L_j + 1, \cdots ,R_j が派閥争いを始めたとき最後に残る派閥を求めます。

各思考実験の結果を求めてください。

制約

• 入力は全て整数
• いずれの時点においても、仲良し度は相異なる
• 2 \leq N \leq 10^5
• 1 \leq Q \leq 10^5
• 1 \leq A_i \leq 10^9 \ (1 \leq i \leq N)
• 1 \leq B_i \leq 10^9 \ (1 \leq i \leq N - 1)
• T_j \in \{1, 2\} \ (1 \leq j \leq Q)
• T_j = 1 のとき 1 \leq P_j \leq N \ (1 \leq j \leq Q)
• T_j = 2 のとき 1 \leq P_j \leq N - 1 \ (1 \leq j \leq Q)
• 1 \leq V_j \leq 10^9 \ (1 \leq j \leq Q)
• 1 \leq L_j \leq R_j \leq N \ (1 \leq j \leq Q)

小課題

1. (100 点) Q = 1
2. (150 点) T_j = 1, L_j = 1, R_j = N \ (1 \leq j \leq Q)
3. (350 点) T_j = 2, L_j = 1, R_j = N \ (1 \leq j \leq Q)
4. (200 点) T_j = 1, V_j = A_{P_j} \ (1 \leq j \leq Q)
5. (100 点) 追加の制約はない

入力例 1

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

出力例 1

5
2
2

例として 1 日目の思考実験について考えます。1 日目の終わりにおける部員 4, 5 のパソコン力はそれぞれ 7, 9 です。よって、 1 日目の思考実験において最後に残るのは派閥 5 となります。

この入出力例は小課題 5 の制約を満たします。

入力例 2

8
14 10 12 20 18 1 6 13
2 16 1 3 4 12 11
5
1 2 3 1 8
1 3 8 1 8
1 1 4 1 8
1 7 15 1 8
1 4 19 1 8

出力例 2

8
8
8
7
7

この入出力例は小課題 2, 5 の制約を満たします。

入力例 3

8
10 17 13 17 16 1 19 8
11 1 9 4 2 12 10
5
2 2 7 1 8
2 4 15 1 8
2 3 5 1 8
2 2 13 1 8
2 6 14 1 8

出力例 3

4
4
2
2
2

この入出力例は小課題 3, 5 の制約を満たします。

入力例 4

8
11 11 2 2 10 5 2 15
9 1 10 19 7 14 20
3
1 1 11 8 8
1 1 11 4 6
1 1 11 2 6

出力例 4

8
5
5

この入出力例は小課題 4, 5 の制約を満たします。

入力例 5

20
30 95 72 93 69 100 45 51 7 19 40 61 73 51 98 71 25 51 15 91
20 69 94 58 63 70 80 17 66 10 83 48 40 86 23 67 60 44 96
6
2 9 71 6 15
1 2 46 11 15
1 6 15 6 19
2 8 8 1 13
2 8 26 6 18
1 9 31 5 14

出力例 5

12
12
12
4
12
8

この入出力例は小課題 5 の制約を満たします。