問題文

京都大学で NF (November Festival) のテーマを決める投票が行われています。

N 個のテーマ案があり、 i 番目のテーマ案には現在 a_i 票が投じられています。

これから X 票が投じられていようとしています。

テーマは、これら X 票の投票後に得票数が最大であるようなテーマ案の内からランダムに選ばれます。

テーマとして選ばれる可能性のあるテーマ案の個数を求めてください。

制約

• 1 \leq N \leq 1000
• 1 \leq a_i \leq 1000
• 1 \leq X \leq 1000
• 入力は全て整数である。

入力例 1

5 5
1 3 5 7 9

出力例 1

3

この例では 3 番目、4 番目、5 番目のテーマ案がテーマとして選ばれる可能性があります。

入力例 2

5 2
1 3 5 7 9

出力例 2

2

この例では 4 番目、5 番目のテーマ案がテーマとして選ばれる可能性があります。

得票数が最大であるようなテーマ案が複数ある場合、いずれのテーマ案もテーマとして選ばれる可能性があることに注意してください。

問題文

n 個の品物があり、1 から n までの番号が付けられています。

各品物には価値と重さが定められていて、i 番目の品物の価値は v_i、重さは w_i です。

あなたはこれらの品物から重さの総和が W を超えないようにいくつか選び、選んだ品物の価値の総和を最大化したいです。

ただし、m 個の条件があります。

j 番目の条件は (a_j, b_j) で表され、それぞれ「 a_j 番目の品物を選ぶならば b_j 番目の品物を選ばなければならず、b_j 番目の品物を選ぶならば a_j 番目の品物を選ばなければならない」 という意味です。

これらの条件を全て満たした上で、n 個の品物から重さの総和が W を超えないようにいくつか品物を選んだときの価値の総和の最大値を求めてください。

制約

• 入力中の値は全て整数である。
• 1 \leq n \leq 100
• 0 \leq m \leq \frac {n(n-1)}{2}
• 1 \leq W \leq 10^4
• 1 \leq w_i \leq W
• 1 \leq v_i \leq 10^7
• 1 \leq a_i, b_i \leq n
• a_i \neq b_i
• i \neq j ならば、(a_i, b_i) \neq (a_j, b_j) かつ (a_i, b_i) \neq (b_j, a_j)

入力例 1

3 1 10
3 2
5 4
3 3
1 2

出力例 1

6

1 番目の品物と 2 番目の品物を選ぶことで価値の総和を 6 にすることができ、これが最適です。

条件から、2 番目の品物と 3 番目の品物だけを選ぶことはできないことに注意してください。

入力例 2

4 0 10
1 1
2 2
3 3
4 4

出力例 2

10

全ての品物を選ぶことができます。

入力例 3

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

出力例 3

0

一つも品物を選ぶことができません。

入力例 4

1 0 10000
10000 10000000

出力例 4

10000000

問題文

あなたは天秤を用いて物体の重さを 1 g単位で量りたいと考えています。

あなたは N 種類の分銅をそれぞれ K 個ずつ用意することができます。 ここで、i (1 \leq i \leq N) 種類目の分銅は全部同じ重さです。

これらの N \times K 個の分銅をあなたは

• 天秤の右の皿へ置く
• 天秤の左の皿へ置く
• どちらにも置かない

のいずれかを行うことができます。 重さを量りたい物体を右の皿に乗せることとして、

(左の皿に乗った分銅の重さの合計) = (右の皿の乗った分銅の重さの合計) + (物体の重さ)

が成り立つとき天秤は釣り合い、このとき物体の重さは (左の皿に乗った分銅の重さの合計) - (右の皿の乗った分銅の重さの合計) gであると量ることができます。

あなたは分銅をできるだけ少ない種類数用意することで 1 gから M gまでの全ての重さを 1 g単位で量りたいです。 そのような種類数 N を出力してください。

制約

• 1 \leq M \leq 10^9
• 1 \leq K \leq 10^5
• 入力は全て整数である。

入力例 1

5 1

出力例 1

3

例えば 1,\ 2,\ 3 gの分銅を用意すると、

• 左の皿に 1 gの分銅を乗せることで 1 g
• 左の皿に 2 gの分銅を乗せることで 2 g
• 左の皿に 3 gの分銅を乗せることで 3 g
• 左の皿に 2,\ 3 gの分銅を、右の皿に 1 gの分銅を乗せることで 4 g
• 左の皿に 2,\ 3 gの分銅を乗せることで 5 g

を量ることができます。2 種類の分銅では1 \sim 5 gを量ることはできないのでこれが最小です。

入力例 2

8 2

出力例 2

2

例えば 1,\ 3 gの分銅を用意すればよいです。

問題文

2N 枚のカードがあります。 i~(1 \leq i \leq 2N) 番目のカードには、整数 i が書かれています。

千咲さんと月乃瀬さんは、これらのカードを使って次のようなゲームをすることにしました。

1. カードをよくシャッフルし、N 枚ずつ取ってお互いの最初の手札とする。
2. ゲームは N ラウンドからなる。各ラウンドでは、2 人のプレイヤーは手札の中で最も小さい数が書かれたカードを選び、見せ合う。見せたカードに書かれた数の大きいほうが、そのラウンドの勝者になる。見せたカードはお互いに手札から取り除き、それ以降のラウンドでは考慮しない。

千咲さんと月乃瀬さんは、このゲームを 1 回プレイしました。

ゲームの結果が 0 と 1 のみからなる長さ N の文字列 S として与えられます。 任意の整数 i\ (1 \leq i \leq N) について、S_i が 1 のとき、 千咲さんがゲームの i 回目のラウンドの勝者になったことを、S_i が 0 のとき、そうでないことを意味します。

このようなゲームの結果を与える千咲さんの最初の手札として、ありえるものは何種類あるでしょうか？ 答えはとても大きくなることがあるため、998244353 で割った余りを出力してください。

制約

• 1 \leq N \leq 10^5
• S は 0 と 1 のみからなる長さ N の文字列である。

入力例 1

2
01

出力例 1

1

千咲さんの最初の手札に 1 と 4 が、月乃瀬さんの最初の手札に 2 と 3 が書かれたカードがある場合を考えます。このとき、

• 1 回目のラウンドでは、千咲さんは 1 が書かれたカードを、月乃瀬さんは 2 が書かれたカードをお互いに見せ、月乃瀬さんがラウンドの勝者になります。
• 2 回目のラウンドでは、千咲さんは 4 が書かれたカードを、月乃瀬さんは 3 が書かれたカードをお互いに見せ、千咲さんがラウンドの勝者になります。

よって、千咲さんのこの最初の手札は、与えられたゲーム結果を満たします。

入力例 2

15
111110001011100

出力例 2

2100

問題文

N 個の根付き木があります。それぞれの木は、木 1, 木 2,   \ldots   , 木 N と名付けられています。 木 i の頂点の数は M_i で、それぞれ頂点 1, 頂点 2,   \ldots   , 頂点 M_i と名付けられています。 また、木 i の根は頂点 1 で、木 i の頂点 j (2 \leq j \leq M_i) の親は頂点 p_{ij} です。

AliceさんとBobさんが、これらの木と一つのチェスの駒を使ってゲームをしようとしています。ルールは以下のようになっています。

• 最初、駒は「スタート地点」に置かれている。
• プレイヤーはAliceさんから交互に以下の行動を行う。
  • もし駒が「スタート地点」にあるならば、まだ選ばれていない木を一つ選び、その木の根に駒を動かす。もし、まだ選ばれていない木が無いならば、現在のプレイヤーは敗北する。
  • 駒が木の葉にあるならば、「スタート地点」に駒を動かす。
  • 駒が木の葉でない頂点にあるならば、その子頂点のいずれかに駒を動かす。

AliceさんとBobさんが勝利のために最適に行動するとき、勝利するのはどちらになるでしょうか。

制約

• 1 \leq N \leq 10^5
• 2 \leq M_i \leq 10^5
• 1 \leq p_{ij} \leq j-1
• \sum_{i=1}^{N} M_i \leq 2 \times 10^5

入力例 1

1
4
1 1 2

出力例 1

Bob

二人は以下のように行動します。

• Aliceさんが、コマを木 1 の根である頂点 1 に動かす。
• Bobさんが、コマを頂点 1 の子である頂点 2 に動かす。
• Aliceさんが、コマを頂点 2 の子である頂点 4 に動かす。
• Bobさんが、頂点 4 は葉なので、コマをスタート地点に動かす。

この後、Aliceさんはもうコマを動かせないので、Bobさんが勝利します。

入力例 2

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

出力例 2

Bob

問題文

カズマ王国には N 個の街があり、それぞれの街には 1 人の勇者がいます。

i (1 \leq i \leq N) 番目の街の勇者は合計して A_i 体までのモンスターを倒すことができます。

勇者は経験値が欲しいので、自分の街に来たモンスターはできるだけ多く倒します。

あなたは魔王で、M 個の拠点を支配下に置いています。

j (1 \leq j \leq M) 番目の拠点からは合計 B_j 体のモンスターを自由に L_j, L_j+1, ..., R_j 番目の街に派遣します。

その結果、勇者に倒されなかったモンスターの数だけカズマ王国にダメージを与えることができます。

カズマ王国に与えられる合計ダメージの最大値を求めてください。

制約

• 入力はすべて整数である。
• 1 \leq N \leq 3000
• 1 \leq M \leq 3000
• 1 \leq A_i \leq 10^9
• 1 \leq B_j \leq 10^9
• 1 \leq L_j \leq R_j \leq N

入力例 1

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

出力例 1

7

次のように派遣するとカズマ王国に合計して 7 ダメージを与えることができます。

• 1 番目の拠点から 5 体のモンスターを 2 番目の街に、2 体のモンスターを 3 番目の街にそれぞれ派遣します。
• 2 番目の拠点から 4 体のモンスターを 2 番目の街に派遣します。
• 3 番目の拠点から 3 体のモンスターをそれぞれ 3 番目の街に派遣します。

入力例 2

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

出力例 2

4

入力例 3

10
9 7 4 11 5 100 95 3 55 12
12
2 3 6
1 2 2
1 4 8
3 5 5
3 5 6
4 4 6
5 7 3
5 8 5
1 10 52
9 10 13
7 9 2
8 9 5

出力例 3

83

入力例 4

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

出力例 4

9999999999

オーバーフローに気をつけてください。

問題文

N 個のグリッドがあります。i\ (1 \leq i \leq N) 番目のグリッドの大きさは H_i 行 W_i 列です。N 個のグリッドそれぞれについて、以下の条件を満たすようにグリッドの各マスに A, B, C のいずれかを書き込んでください。

• (一方に A が、もう一方に B が書かれている隣接したマスのペアの個数) =
  (一方に B が、もう一方に C が書かれている隣接したマスのペアの個数) =
  (一方に C が、もう一方に A が書かれている隣接したマスのペアの個数)
• グリッドの各行・各列に A, B, C はそれぞれ一つ以上書かれている。

ただし、グリッド上の 2 つのマスは頂点または辺を共有するときに隣接していると見なします。

なお、この問題の制約の範囲で、条件を満たすようなグリッドへの書き込み方が必ず存在することが証明できます。

制約

• 1 \leq N \leq 1,000
• 4 \leq H_i \leq 1,000
• 4 \leq W_i \leq 1,000
• \sum_{i=1}^{N} H_i \times W_i \leq 10^6
• 入力は全て整数である。

入力例1

1
4 4

出力例1

ABCC
CACB
BCAA
CABA

下の図は出力例 1 の、A とB、B と C、C と A が書かれた隣接 2 マスをそれぞれ赤線、緑線、青線で示しています。赤線、緑線、青線はそれぞれ等しく 10 本ずつあり、各行・各列に A, B, C がそれぞれ一つ以上含まれているため、この出力は条件を満たしています。

出力例 1 の隣接マス

入力例2

2
4 5
5 4

出力例2

CACCB
CBBAA
ACABC
BACBB
BCBA
CAAB
AACB
ABCC
BBCA

出力している 4 行 5 列のグリッドと 5 行 4 列のグリッドはそれぞれ条件を満たしています。

問題文

あなたはペンシルパズルを作っています。

このパズルは N 個の頂点と M 本の有向辺からなる単純グラフの形をしています。

頂点には 1 から N までの番号が、辺には 1 から M までの番号がついています。

辺 i は、頂点 u_i から頂点 v_i へ向かう辺であり、ラベル l_i (l_i \in \{0,1\}) がついています。

このパズルの遊び方は以下の通りです。

• 各頂点に数 1,2,3 のうちの 1 つを書き込む。頂点 i に書かれた数を A_i とする。
• すべての i (1 \leq i \leq M) について以下を満たす書き込み方が、パズルの解である。
  • l_i = 0 のとき、A_{u_i} < A_{v_i}
  • l_i = 1 のとき、A_{u_i} \leq A_{v_i}

あなたは上のようなパズルを思いつきましたが、解の存在についてはまだ確認していません。

解が存在しない場合でもできるだけ満足する答えを探したいので、あなたは以下で定義される不満度が最小となるような書き込み方を求めようとしています。

• すべての i (1 \leq i \leq M) について、次のようにして C_i を求める。
  • l_i = 0 のとき、C_i = \max(0,A_{u_i}-A_{v_i}+1)
  • l_i = 1 のとき、C_i = \max(0,A_{u_i}-A_{v_i})
• 不満度は、 C_i の総和である。

パズルの解が存在するとき、不満度の最小値は 0 となることがわかります。

不満度の最小値を求めてください。

制約

• 2 \leq N \leq 5000
• 1 \leq M \leq \min(5000, N \times (N-1))
• 1 \leq u_i,v_i \leq N
• u_i \neq v_i
• すべての 1 \leq i,j \leq N について、i \neq j ならば (u_i, v_i) \neq (u_j, v_j)
• l_i \in \{0,1\}
• 入力はすべて整数である。

入力例 1

4 3
1 2 0
2 3 1
3 4 0

出力例 1

0

A = (1, 2, 2, 3) とすればよいです。

このとき、

• A_1 < A_2
• A_2 \leq A_3
• A_3 < A_4

のすべてを満たし、不満度は 0 です。

入力例 2

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

出力例 2

1

A = (1, 2, 2, 2, 3, 2) とすれば、C = (0, 0, 1, 0, 0, 0, 0, 0, 0) となり、不満度を 1 にすることができます。 不満度を 0 にすることはできないので、不満度の最小値は 1 です。

問題文

これはインタラクティブな要素がある問題です。

0 以上 10^{18} 以下の整数 X が与えられます。

以下の説明を読み、X を符号化する encode プログラムと、復号する decode プログラムを実装してください。

encode プログラムによって符号化された X の情報だけをもとに、 decode プログラムによって X を復号できれば正答となります。

encode プログラム

encode プログラムでは、与えられた整数 X を 150 行 150 列のグリッド H に符号化する。

まず、整数 X および 150 行 150 列の初期グリッド G の情報が入力される。

G の各マスは空マス . か壁マス # のいずれかであり、後述する「初期グリッド生成」によって生成される。

あなたは G の空マス . それぞれについて以下のいずれかを行うことでグリッド H を作り、出力しなければならない。

• 壁マス # に置き換える。
• Sマス S に置き換える。
• 空マス . のままにする。

ただしグリッド H において、Sマスはグリッド上に必ず 1 マスだけ存在するようにしなければならない。

decode プログラム

decode プログラムでは、グリッド H の情報から整数 X を復号する。

ただし、 H の情報は直接入力されない。その代わりに、グリッド H 上にいるロボットを操作することができる。

グリッドの i 行 j 列目のマスを、マス (i, j) と呼ぶことにする。

はじめ、ロボットは H の Sマスにいる。あなたは以下の「操作」を何回か行うことができる。

• 上下左右の 4 方向のうちの 1 つをロボットに伝える。
• ロボットは、現在いるマスからその向きにある隣り合ったマスに移動しようとする。
  • つまり、ロボットがマス (i, j) にいるとすると、
    • ロボットに伝えた方向が上であるとき、ロボットはマス (i-1, j) に、
    • ロボットに伝えた方向が下であるとき、ロボットはマス (i+1, j) に、
    • ロボットに伝えた方向が左であるとき、ロボットはマス (i, j-1) に、
    • ロボットに伝えた方向が右であるとき、ロボットはマス (i, j+1) に移動しようとする。
• そのマスが壁マス # でなく、グリッドの外でもなければ移動し、壁マス # かグリッドの外であれば移動しない。
• その後、ロボットが Sマスにいるかどうかがあなたに伝えられる。
• ロボットの移動が成功したかどうかはあなたには伝えられない。

何回かの「操作」の後、あなたは復号した整数 X を出力しなければならない。

初期グリッド生成

初期グリッド G には 3800 個の壁マス # がランダムに配置されている。

壁マスの周囲 8 マスには、他の壁マスが存在しないことが保証されている。

マス (i, j) の周囲 8 マスとは、マス (i-1, j-1), (i-1, j), (i-1, j+1), (i, j-1), (i, j+1), (i+1, j-1), (i+1, j), (i+1, j+1) のことである。

具体的には、初期グリッドは以下のように生成される。

• はじめ、グリッドのすべてのマスは空マス . である。
• 3800 個の壁マスが置かれるまで以下を繰り返す。
  • 周囲 8 マスに壁マスがないような空マスを候補として列挙し、その中からランダムに 1 つのマスを選び、それを壁マスに置き換える。
  • グリッドの縁にある空マスについても同様に、その周りに壁マスがなければ候補に含まれる。
  • もしそのようなマスがなく、3800 個の壁マスを置くことができないことがわかったら、そのグリッドを捨てて、新しくグリッドを生成しなおす。
• 3800 個の壁マスが置かれたら、このグリッドを初期グリッドとして採用する。

この方法によって生成された初期グリッドのサンプル 50 個が、共有フォルダ にて配布されている。

なお、これらの配布されているグリッドが実際のテストケースに含まれているとは限らない。

制約

• 0 \leq X \leq 10^{18}
  • X はこの範囲からランダムに選ばれる整数である。
• グリッドの縦幅および横幅は 150 マスである。
• 初期グリッド G の壁マス # の個数は 3800 である。
• 初期グリッド G では、壁マスの周囲 8 マスには他の壁マスは配置されない。
• 整数 X および初期グリッド G は、解答コードの提出ごとに新しく生成される。

部分点

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

解答コードの提出ごとに新しく生成される 25 個のどのテストケースに対しても、

• 65000 回以下の「操作」によって正答した場合は、 10 点
• 6500 回以下の「操作」によって正答した場合は、上に加えて 390 点

が与えられる。

提出

encode プログラムと decode プログラムを 1 つにまとめ、提出せよ。

後述する「ジャッジ」をみればわかるように、提出されたプログラムは encode 用と decode 用に 1 回ずつ起動される。

プログラム起動時には、符号化と復号のどちらを行えばよいかを判別するための文字列が入力される。

入力 （encode プログラム）

入力は以下の形式で標準入力から与えられる。

1 行目には文字列 encode が与えられる。

2 行目には X が入力され、 3 行目以降には G が入力される。

G のマス (i, j) は文字 G_{i,j} で表わされる。

• マス (i, j) が空マスのとき G_{i,j} は文字 . であり、
• マス (i, j) が壁マスのとき G_{i,j} は文字 # である。

文字の間に空白は含まれない。

encode
X
G_{1,1}G_{1,2}...G_{1,150}
:
G_{150,1}G_{150,2}...G_{150,150}

出力 （encode プログラム）

標準出力へ以下の形式で H を出力せよ。

H のマス (i, j) を文字 H_{i,j} で表せ。

• マス (i, j) が空マスのとき H_{i,j} は文字 .、
• マス (i, j) が壁マスのとき H_{i,j} は文字 #、
• マス (i, j) がSマスのとき H_{i,j} は文字 S とせよ。

文字の間に空白を含めてはいけない。

H_{1,1}H_{1,2}...H_{1,150}
:
H_{150,1}H_{150,2}...H_{150,150}

入出力 （decode プログラム）

最初に、文字列 decode が次の形式で標準入力から与えられる。

decode

その後、何回か「操作」を行う。「操作」では次の形式で標準出力へ出力せよ。

ロボットに移動させたい方向を文字 C で表せ。C は文字 U,D,L,R のいずれかであり、それぞれ上下左右の 4 方向を表す。

? C

この「操作」に対する応答は、次の形式で標準入力から与えられる。

ロボットがSマスにいるかどうかが文字 J で表される。

• ロボットがSマスにいるとき J は S であり、
• ロボットがSマスにいないとき J は . である。

J

最後に X を以下の形式で出力せよ。

! X

ジャッジ

ジャッジは以下の手順で行われる。

• 整数 X および初期グリッド G を生成する。
• 提出されたプログラムのプロセスを encode 用として立ち上げる。
• encode 用のプロセスに入力を与える。ただし、EOF は与えない。
• encode 用のプロセスから適切な出力があり、かつ encode 用のプロセスが終了するまで待機する。
• 不適切なグリッドが出力された場合は誤答とする。
• 提出されたプログラムのプロセスを decode 用として立ち上げる。
• decode 用のプロセスと対話を行う。この対話は decode 用のプロセスが終了するまで続く。
• 実行時間制限内に decode 用のプロセスから正しい出力がなされた場合のみ正答とし、それ以外は誤答とする。

注意

• 出力の度に標準出力を flush せよ。そうしない場合、TLE となる可能性がある。
• グリッド H および整数 X を出力した後は、プログラムをすぐに終了せよ。従わない場合のジャッジの挙動は未定義である。
• 出力形式が正しくない場合のジャッジの挙動は未定義である。
• プロセスは、上記によって規定された以外のいかなる通信も行ってはならない。

入力例（encode プログラム）

この例では G は 20 行 20 列のグリッドとして入力されているが、実際には 150 行 150 列である。

また、 この例では G の壁マスの個数は 70 個だが、実際には 3800 個である。

encode
239
#..............#..#.
......#....#.#......
..#............#....
.....#..#..#.#...#..
.#.#...............#
.......#..#..#......
..#..#.........#.#.#
..........#..#......
..#..#..........#.#.
.......#.#..#.......
...#..........#...#.
.#...#...#.#........
.......#.....#.#..#.
#.#......#.#........
....#.#.......#..#..
.........#.........#
#..#.#.#...#.#.#.#..
...................#
..#.....#.#.#.......
.....#.........#.#..

出力例 （encode プログラム）

この例では H は 20 行 20 列のグリッドとして出力されているが、実際には 150 行 150 列である。

####################
#S...###############
..##...#############
######.#############
#####..#############
#.....##############
..######....########
.#####...##..#######
.##########..#######
......####..########
########...#########
##########.#.....###
####..##...#.###..##
#####....###.####..#
############..####.#
#############......#
##################.#
############..###..#
#############.....##
####################

入出力例 （decode プログラム）

符号化が上記の入出力例のように行われた後の復号の例を示す。

decode

? R

.

? U

.

? L

S

! 239

問題文

あるところに、木こりのカズマくんがいました。

カズマくんは 2 つの N 頂点の根付き木 T_1, T_2 を持っています。 T_1, T_2 の根はそれぞれ頂点 1 であり、T_1, T_2 の葉の数は同じです。 また、どちらの木においても頂点 1 は葉ではありません。

T_1 の i 番目の辺は頂点 a_i と b_i を結び、w_i の重みを持つ無向辺です。 同様に T_2 の i 番目の辺は頂点 c_i と d_i を結び、v_i の重みを持つ無向辺です。

カズマくんは T_1, T_2 を組み合わせて、新しい2つの木を以下の手順で作ることにしました。

• T_1 と T_2 の葉を一対一対応させ、対応させた葉同士を縮約し、1 つのグラフを作る。
• その後、作ったグラフからいくつか辺を取り除いて、以下の3つの条件を満たすようにする。
  • T_1 の頂点 1 と T_2 の頂点 1 は非連結である。
  • T_1 の頂点 1 が属する連結成分が木となる。T_2 の頂点 1 についても同様である。
  • 任意の頂点は T_1 の頂点 1 または T_2 の頂点 1 と連結である。

辺を取り除くときには、取り除いた辺の重みの総和分のエネルギーを消費します。 カズマくんが達成できる最小の消費エネルギーを求めてください。

制約

• 3 \leq N \leq 10^5
• 1 \leq a_i, b_i, c_i, d_i \leq N
• 1 \leq w_i, v_i \leq 10^9
• 2 つのグラフはどちらも木である
• 2 つのグラフの葉の数は等しい
• 2 つのグラフのそれぞれにおいて、頂点 1 は葉ではない
• 入力はすべて整数で与えられる

入力例 1

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

出力例 1

6

「T_1 の葉 x と T_2 の葉 y で縮約」を「(x, y) で縮約」と書くことにします。 カズマくんはまず (3, 3), (4, 4), (5, 5) で縮約し、その後上記の図で点線となっている辺を取り除きます。 このとき消費エネルギーは 6 となり、これが最小です。

入力例 2

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

出力例 2

5000000000

入力例 3

7
1 2 8613
3 6 91
2 5 20238
3 7 5018
1 3 10453
2 4 7580
3 7 123
2 5 24095
1 2 6957
2 4 13166
1 3 72
2 6 2444

出力例 3

7625

問題文

アンジェは変数で遊ぶのが好きです。

今日は 3 つの変数 x,~y,~z を用意して、これらを使って遊ぶことにしました。 3 つの変数は 0 で初期化されています。

アンジェは、これらの変数に対して、以下の操作のいずれかを選んで行うことを n 回繰り返すつもりです。

• 変数を 1 つ選ぶ。その変数の値を 1 増やす、もしくは 1 減らす。
• 3 つの変数全ての値を 1 ずつ増やす、もしくは 1 ずつ減らす。

n 回の操作を行ったあとに、x,~y,~z を m で割った余りがそれぞれ p,~q,~r であるとき、 アンジェは満足します。

アンジェは、自分が満足できるような n 回の操作列が何種類あるのかに興味を持ちました。 彼女の代わりに、そのような操作列の種類数を数えて、998244353 で割った余りを出力してください。

ここで 2 つの操作列は、ある整数 i\ (1 \leq i \leq n) が存在して、i 回目の操作後に 1 つ以上の変数の値が異なるとき、別の種類であるとみなします。

制約

• 入力は全て整数である。
• 1 \leq n \leq 10^6
• 1 \leq m \leq 10^6
• 0 \leq p,\ q,\ r < m

入力例 1

1 3 1 2 2

出力例 1

0

1 回の操作で、ある 1 つの変数の値だけを 1 増やし、残り 2 つの変数の値を 1 減らすことはできません。

入力例 2

2 3 1 2 2

出力例 2

2

まず、3 つすべての変数の値を 1 減らします。次に x の値だけを 1 減らすことで、x の値は -2、 y の値は -1、z の値は -1 になります。 これらを 3 で割った余りはそれぞれ 1,~2,~2 であるため、アンジェはこの操作列に満足します。

アンジェが満足する操作列は、この操作列を含めて 2 種類あります。

入力例 3

1000000 4 1 2 3

出力例 3

333551635

問題文

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

1 つの頂点からなる根付き木 T があり、この頂点を頂点 0 とします。頂点 0 には、長さ x_0 で伸びやすさが y_0 のタケノコが生えています。

また、頂点 0 にはすいばか君がいます。

Q 個のクエリが与えられるので順番に処理してください。クエリは 3 種類あり、以下の形式で与えられます。

• クエリ 1 : 1 v x y ― 頂点 v を親とする長さ x で伸びやすさが y のタケノコが生えた新しい頂点を追加せよ。新しい頂点の番号はこの直前に追加された頂点番号（ない場合は 0 ） + 1 とする。
• クエリ 2 : 2 a ― すいばか君が根付き木 T 全体に効果 a の肥料を散布する。これにより根付き木 T の任意の頂点に生えているタケノコは、現在の長さが x で伸びやすさが y とすると長さが x + a \times y に変わる。
• クエリ 3 : 3 v ― すいばか君に頂点 v までの単純パス上（両端を含む）に見えているタケノコの本数を尋ねる。すいばか君は 30 本以下のタケノコは正確に数えて答えることができるが、31 本以上は数えるのがめんどくさくなってしまうため many と答える。あなたはこの答えを予想して出力せよ。

ただし、すいばか君にタケノコ t が見えているとは、頂点 0 からタケノコ t の生えている頂点までの単純パス上（両端を含む）の頂点に生えているタケノコの高さを順番に h_1, h_2, ..., h_n とするとき、h_i < h_n (1 \leq i \leq n - 1) を満たすことを指します。また、すいばか君に頂点 0 のタケノコは見えています。

制約

• 1 \leq Q \leq 2 \times 10^5
• 1 \leq x_0 \leq 10^9
• 1 \leq y_0 \leq 10^6
• 0 \leq v \leq （最後に追加された頂点番号（ない場合は 0 ））
• 1 \leq x \leq 10^9
• 1 \leq y \leq 10^6
• -10^6 \leq a \leq 10^6
• クエリ 3 の数は 3 \times 10^4 を超えない。
• 入力は全て整数である。

入力例 1

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

出力例 1

2
1

• 1 つ目のクエリでは、頂点 0 を親とする頂点 1 が追加されます。頂点 1 のタケノコは高さ 2 で伸びやすさ 2 です。
• 2 つ目のクエリでは、頂点 0, 1 のタケノコのうちすいばか君が見えるものを数えます。頂点 0, 1 のタケノコの高さはそれぞれ 1, 2 であり、すいばか君には両方のタケノコが見えます。なので、答えは 2 になります。
• 3 つ目のクエリでは、頂点 0, 1 のタケノコの高さがそれぞれ -1, -2 に変わります。このように、タケノコの高さは負になることもあります。
• 4 つ目のクエリでは、頂点 0, 1 のタケノコのうちすいばか君が見えるものを数えます。このとき、頂点 1 のタケノコは、 (頂点 0 のタケノコの高さ) < (頂点 1 のタケノコの高さ) を満たさないため見えません。なので、答えは 1 になります。タケノコの高さが負でもすいばか君への見え方は問題文中に書いてある通りであることに注意してください。

入力例 2

12 1 1
1 0 5 1
1 1 2 3
2 1
3 2
1 2 1 5
2 2
3 3
1 2 1 1
2 -4
3 3
2 5
3 4

出力例 2

2
3
2
3

入力例 3

34 1 1
1 0 1 2
1 1 1 3
1 2 1 4
1 3 1 5
1 4 1 6
1 5 1 7
1 6 1 8
1 7 1 9
1 8 1 10
1 9 1 11
1 10 1 12
1 11 1 13
1 12 1 14
1 13 1 15
1 14 1 16
1 15 1 17
1 16 1 18
1 17 1 19
1 18 1 20
1 19 1 21
1 20 1 22
1 21 1 23
1 22 1 24
1 23 1 25
1 24 1 26
1 25 1 27
1 26 1 28
1 27 1 29
1 28 1 30
1 29 1 31
3 30
2 1
3 29
3 30

出力例 3

1
30
many