問題文

あなたはアイドルグループ Bit♡Beat のプロデューサーです。

Bit♡Beat の事務所に N 個のファンレターが届きました。 i 個目のファンレターは A_i 月 B_i 日に届いたものです。

これら N 個のファンレターの日付を早い順（1 月 1 日から始めて、先に訪れる順）に出力してください。

制約

• 1\le N\le 365
• A_i 月 B_i 日は平年（うるう年ではない年）において正しい日付である。
• (A_i , B_i) \neq (A_j , B_j) (i \neq j)
• 入力される値は全て整数

入力例 1

3
3 15
1 15
3 8

出力例 1

1 15
3 8
3 15

事務所には 3 月 15 日、 1 月 15 日、 3 月 8 日にファンレターが届きました。

これらの日付を早い順に並べると 1 月 15 日、 3 月 8 日、 3 月 15 日となります。したがって、上記のように出力してください。

入力例 2

5
1 1
1 2
1 3
1 4
1 5

出力例 2

1 1
1 2
1 3
1 4
1 5

入力例 3

10
9 21
8 22
10 28
6 22
6 26
7 10
5 3
8 31
9 4
11 21

出力例 3

5 3
6 22
6 26
7 10
8 22
8 31
9 4
9 21
10 28
11 21

問題文

アイドルグループ Bit♡Beat では、新曲のカップリングとしてメンバーの中から 2 人のユニット（選抜）を組むことになりました。

グループには N 人のメンバーがおり、それぞれのメンバーにスキル値が定まっています。 i 人目のメンバー (1\le i\le N) のスキル値は A_i です。

プロデューサーであるあなたは、スキル値の合計が ちょうど S になるような 2 人のメンバーの選び方を探しています。

スキル値の合計がちょうど S になるような 2 人のメンバーの選び方が何通りあるか求めてください。

制約

• 2\le N\le 5\times 10^5
• 1\le S \le 10^9
• 1\le A_i\le 10^9
• 入力される値は全て整数

入力例 1

5 11
5 6 9 2 2

出力例 1

3

1 人目と 2 人目がユニットを組むと、スキル値の合計は 5+6=11 となります。

このほかにも、 3 人目と 4 人目、3 人目と 5 人目がユニットを組んでも条件を満たします。

条件を満たす 2 人のメンバーの選び方は 3 通りであるため、 3 を出力してください。

入力例 2

10 1000000000
1 1 1 1 1 1 1 1 1 1

出力例 2

0

条件を満たす 2 人のメンバーの選び方が存在しない場合もあります。

入力例 3

6 14
7 7 7 7 7 7

出力例 3

15

入力例 4

15 8
3 4 10 9 1 1 1 7 8 9 9 3 8 9 7

出力例 4

6

問題文

アイドルグループ Bit♡Beat のファンイベントに N 人のファンが来る予定です。 N 人のファンはそれぞれ整理券を持っており、i 番目のファン (1\le i\le N) は番号 i の書かれた整理券を持っています。

Bit♡Beat のファンイベントでは整理券の番号順にファンを会場に案内する必要があります。しかし、ファンの到着順はバラバラなので、以下のルールに従ってファンを案内していきます。

• ファンは待機場に 1 人ずつ順番にやってくる。
• 待機場には椅子が K 脚ある。
• プロデューサーであるあなたは、ファンを以下の操作で案内することができる。
  • ちょうど今来たファンを そのまま会場に案内 する。
  • ファンを椅子に一時的に座らせる。ただし、すでにファンが座っている椅子に別の人を座らせることはできない。
  • 椅子に乗ったファンを会場に案内する。その椅子にはそれ以降別の人を座らせることができる。

N 人のファンの到着順は N! 通り考えられますが、そのうち整理券に書かれた番号が小さい順に N 人の人を会場に案内できるような到着順が何通りあるかを 998244353 で割ったあまりを求めてください。

制約

• 1\le K\le N\le 10^6
• 入力される値は全て整数

入力例 1

3 1

出力例 1

4

番号 i の書かれた整理券を持っているファンをファン i と呼びます。

たとえばファン 2 、ファン 1 、ファン 3 という順番でファンが来た場合、以下のようにファンを整理券に書かれた番号が小さい順に会場に案内することができます：

• ファン 2 を椅子に座らせる。
• ファン 1 をそのまま会場に案内する。
• 椅子に座っていたファン 2 を会場に案内する。
• ファン 3 をそのまま会場に案内する。

ファンを整理券に書かれた番号が小さい順に会場に案内できる到着順は 4 通りであるため、 4 を出力してください。

入力例 2

4 1

出力例 2

8

入力例 3

2025 314

出力例 3

31233731

998244353 で割ったあまりを求めてください。

問題文

アイドルグループ Bit♡Beat のプロデューサーであるあなたは、次のライブに向けて特訓期間を設けることにしました。

特訓期間の候補日は 1 日目から N 日目までの N 日あり、そのうちの何日かの 連続する 期間を特訓期間とする予定です。

各候補日によってその日に特訓した場合の体力消費量は異なり、 i 日目 (1\le i\le N) に特訓した場合の体力消費量は A_i です。

あなたは、次の条件を満たす特訓期間のうち最も期間が長いものを調べようとしています。

• 特訓期間の平均体力消費量が K 以下である。

条件を満たす特訓期間のうち、最も期間が長いものの長さを求めてください。

ただし、条件を満たす特訓期間が必ず 1 つ以上存在することが保証されます。

制約

• 1\le N\le 2\times 10^5
• 1\le K\le 10^9
• 1\le A_i\le 10^9
• 条件を満たす特訓期間が必ず 1 つ以上存在する
• 入力される値は全て整数

入力例 1

5 5
3 8 3 6 6

出力例 1

4

1 日目から 4 日目までの 4 日間を特訓期間とすると、この間の平均体力消費量は \displaystyle \frac{3+8+3+6}4=5 となり条件を満たします。

4 日より長い特訓期間で条件を満たすものは存在しないので、 4 を出力してください。

入力例 2

6 1000000000
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

出力例 2

6

入力例 3

12 11
19 11 13 16 3 16 9 8 11 16 14 11

出力例 3

8

問題文

アイドルグループである Bit♡Beat のライブでは、 N 人のメンバーそれぞれのブレスレットが周期的に光りますが、メンバーごとに少しずつスタートがずれた状態から始まります。具体的には、 i 人目のメンバーのブレスレットはライブ開始から A_i 秒後に光り、そこから B_i 秒ごとに光ります。

N 人全員のブレスレットが同時に光ることがあるか判定してください。

より厳密には、ライブ開始から x 秒後に全員のブレスレットが光るような非負整数 x が存在するか判定してください。

制約

• 2\le N\le 2\times 10^5
• 0\le A_i < B_i \le 10^6
• 入力される値は全て整数

入力例 1

3
1 3
1 12
3 5

出力例 1

Yes

ライブ開始から 13 秒後に全員のブレスレットが同時に光ります。したがって、 Yes を出力してください。

入力例 2

2
0 6
5 6

出力例 2

No

全員のブレスレットが同時に光ることはありません。したがって、No を出力してください。

入力例 3

10
23192 199879
152914 434323
486127 642530
867889 926999
362331 897721
75620 913403
100107 117031
22740 516557
260622 642909
419828 739597

出力例 3

Yes

ライブ開始から 382791477 秒後に全員のブレスレットが同時に光ります。

問題文

アイドルグループ Bit♡Beat のファンである高橋君はメンバー N 人全員のアクリルスタンドを 1 つずつ持っています。

高橋君は N 個のアクリルスタンドを一列に並べようとしていますが、特定の 2 人を隣に並べてはいけないと考えています。具体的には、 i=1,2,\ldots,M に対し A_i 人目のメンバーと B_i 人目のメンバーのアクリルスタンドが隣り合わないように並べたいと考えています。

高橋君の M 個の要望を全て満たすような N 個のアクリルスタンドの並べ方が何通りあるかを 998244353 で割ったあまりを求めてください。

制約

• 2\le N\le 10^6
• 0\le M\le 16
• 1\le A_i < B_i \le N
• (A_i , B_i) \neq (A_j , B_j) (i \neq j)
• 入力される値は全て整数である

入力例 1

3 1
1 2

出力例 1

2

以下の 2 つの並べ方が条件を満たします。

• 2 人目のメンバー、 3 人目のメンバー、 1 人目のメンバーのアクリルスタンドと順に並べる。
• 1 人目のメンバー、 3 人目のメンバー、 2 人目のメンバーのアクリルスタンドと順に並べる。

したがって、 2 を出力してください。

入力例 2

5 4
1 4
1 2
1 5
1 3

出力例 2

0

条件を満たす並べ方は存在しません。したがって、 0 を出力してください。

入力例 3

15 5
3 8
8 9
8 12
4 9
4 7

出力例 3

720555423

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

問題文

日本には N 箇所の都市があり、都市同士を双方向に結ぶ M 本の道路が存在します。都市には都市 1 から都市 N までの番号がついており、 i 本目の道路は都市 U_i と都市 V_i を結ぶ、長さ C_i キロメートルの道路です。道路を通る方法以外で都市間の移動はできません。

また、 N 箇所の都市のうち K 箇所にライブ会場があります。具体的には、 k=1,2,\ldots,K に対し都市 A_k にライブ会場があります。ここで、K は 4 以上であることと都市 1 と都市 N には必ずライブ会場があることが保証されます。

人気アイドルグループである Bit♡Beat は全国ツアーを開催することにしました。

全国ツアーは異なる 4 つの都市のライブ会場で行います。また、最初のライブは都市 1 で、最後のライブは都市 N で行う必要があります。

都市 1 からスタートして 4 つの都市（都市 1,N 含む）でライブを行い都市 N に到達するまでに必要な移動距離の最小値を求めてください。

ただし、移動の途中で同じ都市を複数回通っても構いません。

制約

• 4\le N\le 10^5
• \displaystyle N-1 \le M\le \min\left(2\times 10^5, \frac{N(N-1)}2 \right)
• 1\le U_i < V_i \le N
• 1\le C_i \le 10^9
• 与えられるグラフは単純で連結
• 4\le K\le N
• 1 = A_1 < A_2 < \ldots < A_K = N
• 入力される値は全て整数

入力例 1

5 4 4
1 2 4 5
1 3 1
2 3 10
3 4 100
4 5 1000

出力例 1

1121

以下のように移動することで 4 つの都市でライブをすることができます：

• 都市 1 でライブをする。
• 都市 1 から都市 3 に 1 キロメートル移動する。
• 都市 3 から都市 2 に 10 キロメートル移動する。
• 都市 2 でライブをする。
• 都市 2 から都市 3 に 10 キロメートル移動する。
• 都市 3 から都市 4 に 100 キロメートル移動する。
• 都市 4 でライブをする。
• 都市 4 から都市 5 に 1000 キロメートル移動する。
• 都市 5 でライブをする。

この場合の移動距離は 1121 キロメートルです。

移動距離が 1121 キロメートル未満となるように移動することはできないので、 1121 を出力してください。

入力例 2

6 11 4
1 4 5 6
1 2 40
2 3 30
3 6 20
1 4 100
2 4 80
3 4 60
4 6 40
1 5 80
2 5 70
3 5 60
5 6 50

出力例 2

210

入力例 3

15 22 5
1 5 11 13 15
1 2 668
1 6 869
2 3 633
2 7 563
3 4 32
3 8 158
4 5 314
4 9 859
5 10 935
6 7 826
6 11 167
7 8 112
7 12 606
8 9 279
8 13 731
9 10 181
9 14 442
10 15 557
11 12 499
12 13 174
13 14 791
14 15 477

出力例 3

2977

問題文

大人気アイドルグループである Bit♡Beat はとても広い会場でライブをすることになりました。

ライブ会場は南北に H 行、東西に W 列のグリッドに区切られており、グリッドのしきりにあたる部分に通路があります。（詳しくは入出力例を参考にしてください。）

通路同士の交点にあたる場所にそれぞれ (H+1)(W+1) 個のステージがあり、最も北西にあるステージから南に r 本、東に c 本通路を進んだ先のステージをステージ (r,c) (0 \le r \le H , 0 \le c \le W) と表記します。

プロデューサーであるあなたは、アイドルがライブ中にステージ (0,0) から出発して全ての通路を 1 回以上通ってから再びステージ (0,0) に戻ってくるような経路を通るような経路を考えています。しかし、時間の都合上そのような経路のうちステージ間の移動回数が少ないようなものを採用したいと考えました。

(0,0) から出発して全ての通路を 1 回以上通ってから再びステージ (0,0) に戻ってくるような経路のうち、ステージ間の移動回数が最小となる経路を一つ求めてください。

制約

• 1\le H ,W\le 100
• 入力される値は全て整数

入力例 1

1 2

出力例 1

RRDLUDLU

ライブステージは以下の画像のようになります。

例えばステージ (0,0) からスタートして以下の画像の通路に書かれた番号順に移動することで 8 回の移動で全ての通路を通ることができます。

8 回未満の移動で全ての通路を通りステージ (0,0) に戻ることはできないので、 RRDLUDLU を出力すると正解となります。

また、RRDLUDLU のほかにも RDRULDLU などを出力しても正解となります。

入力例 2

1 1

出力例 2

DRUL

入力例 3

2 2

出力例 3

DDRUURDDLURLLURL