問題文

京都大学の今年の学費は X 円で今後毎年 Y 円ずつ上がります。

国内には京都大学以外に N 校の大学があり、i (1 \le i \le N) 番目の大学の今年の学費は A_i 円で今後毎年 B_i 円ずつ上がります。

今年以降(今年を含む)で、京都大学が国内で最も学費の安い大学(同率一位を含む)となる年はありますか？

ある場合は Yes、ない場合は No を出力してください。

制約

• 入力は全て整数
• 1 \le N \le 5 \times 10^{5}
• 1 \le X \le 10^{9}
• 0 \le Y \le 10^{9}
• 1 \le A_i \le 10^{9}
• 0 \le B_i \le 10^{9}

入力例 1

3 535800 10000
520000 20000
550000 4000
580000 10000

出力例 1

Yes

2 年後、京都大学の学費は555{,}800円、国内の他の大学の学費はそれぞれ 560{,}000 円、558{,}000 円、580{,}000 円となっているため、京都大学が国内で最も学費の安い大学となり ます。よって Yes を出力します。

入力例 2

2 535800 10000
535800 107160
535801 0

出力例 2

Yes

今年の時点で京都大学が国内で最も学費の安い大学となっているので、Yes を出力します。

入力例 3

3 4 4
2 5
4 3
6 1

出力例 3

No

問題文

以下の条件を全て満たす長方形グリッドを 1 つ構築してください。
但し、そのような長方形グリッドが存在しない場合はその旨を報告してください。

• グリッドのマスの総数は 1 以上 2 \times 10^5 以下である
• グリッドの各マスは白または黒のいずれかで塗られている
• グリッド全体において、白く塗られたマスの数と黒く塗られたマスの数の比は A:B である
• グリッドの各マスについて、そのマスに隣接するマスのうち少なくとも一つは、そのマスと異なる色で塗られている

ただし、グリッドの行数を H、列数を W とし、上から i+1 行目 左から j+1 列目のマスを (i, j) と表すとき、

(i, j) に隣接するマスとは、((i-1)\bmod H, j)、((i+1)\bmod H, j)、(i, (j-1)\bmod W)、(i, (j+1)\bmod W) の高々 4 つのマスを指すものとします。

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

制約

• 入力は全て整数
• 1 \le T \le 10
• 0 \le A \le 1000
• 0 \le B \le 1000
• A + B \gt 0
• \gcd(A, B) = 1

入力例 1

3
1 2
1 1
0 1

出力例 1

3 4
.@@@
.@.@
.@@@
6 6
@.@.@.
.@.@.@
@.@.@.
.@.@.@
@.@.@.
.@.@.@
-1

1 番目のテストケースについて、白く塗られたマスの数は 4、黒く塗られたマスの数は 8 で、4:8 = 1:2 です。黒く塗られたマスに隣接するマスのうち少なくとも一つは白く塗られており、白く塗られたマスに隣接するマスのうち少なくとも一つは黒く塗られているため、条件を満たします。正答はこの他にも複数存在します。

3 番目のテストケースについて、全てのマスが黒く塗られた長方形グリッドで条件を満たすものはありません。

問題文

今日は、双子の K 君と U 君の誕生日です。

2 人のために、xy 平面上の 0 \le x, y \le N で表される領域に各辺の長さが N の正方形の形をした誕生日ケーキが用意してあります。

1 \le i,j \le N をみたす整数 i,j について、c_{i,j} は平面上の i-1 \le x \le i かつ j-1 \le y \le j で表される領域に何のクリームが塗られているかを表しています。

• c_{i,j} = c のとき、その領域にはチョコレートクリームが塗られている。
• c_{i,j} = s のとき、その領域にはストロベリークリームが塗られている。
• c_{i,j} = . のとき、その領域にはバタークリームが塗られている。

今からこのケーキを 2 つに切り、それぞれ K 君と U 君に渡す必要があるのですが、2 人ともチョコレートクリームとストロベリークリームに目が無いので、2 つに分けられたケーキに含まれるチョコレートクリームとストロベリークリームの面積が一方でも異なっていると満足してくれません(バタークリームの面積は気にしません)。

あなたの仕事は、ケーキをある 1 本の直線に沿って切り、2 人を満足させることです。そのような切り方が存在する場合は切るべき直線とケーキの輪郭の 2 交点の座標を、存在しない場合はその旨を出力してください。

制約

• N は 1 \le N \le 2025 を満たす整数
• c_{i,j} は c、s、. のいずれか
• c_{i,j} = c または c_{i,j} = s をみたす (i,j) が少なくとも 1 組存在する

部分点

以下の制約を満たすデータセットに正解した場合は 1 点が与えられる。

• N は 1 \le N \le 105 を満たす整数
• c_{i,j} は c、s のいずれか

入力例 1

3
scs
..c
.sc

出力例 1

Yes
0.23670068 0.00000000
1.81649658 3.00000000

入力例 2

2
sc
cs

出力例 2

Yes
0.00000000 2.00000000
2.00000000 0.00000000

入力例 3

11
.c..c.s..s.
.c.c..s..s.
.cc...s..s.
.c.c..s..s.
.c..c..ss..
...........
.sss...ccc.
.s..s.c....
.sss..c....
.s....c....
.s.....ccc.

出力例 3

Yes
11.00000000 10.60555128
0.39444872 0.00000000

問題文

京都大学の構内には N 個の地雷が置かれています。構内を 2 次元平面で表したとき、 i 番目の地雷は座標 (X_i,Y_i) にあります。

ある地雷が爆発すると、爆発した地雷と同じ X 座標にある地雷と、同じ Y 座標にある地雷が連鎖的に爆発します。

あなたの仕事は好きな座標に新しく地雷を 1 つ設置し、それを爆発させることによって、なるべく多くの地雷を爆発させることです。

新しく設置した地雷も含めて爆発させることのできる地雷の個数の最大値を求めてください。

制約

• 入力は全て整数
• 1 \le N \le 2 \times 10^5
• |X_i|,|Y_i| \le 10^9

入力例 1

4
1 1
2 4
3 3
5 4

出力例 1

4

新しい地雷を (2,1) に設置すると、地雷 1,2,4 も同時に爆発します。

入力例 2

12
-7 3
3 4
8 -5
3 -2
-2 8
-5 -3
4 -5
-5 -3
-6 8
8 -5
-7 -5
-2 -7

出力例 2

9

問題文

18 個の整数 A_1,A_2,\ldots,A_9,B_1,B_2,\ldots,B_9 が与えられます。

9\times 9 のマス目があり、i 行 j 列には A_i \times B_j を書き込みます。書き込まれた数字 81 個の総和を求めてください。

制約

• 入力は全て整数
• 0 \le A_i,B_i \le 10^6 \ (1 \leq i \leq 9)

入力例 1

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

出力例 1

2025

書き込まれた表は一般的な九九と同じになり、その総和は 2025 であることが知られています。

入力例 2

2860 2762 2680 2585 2502 2234 2160 2149 2114
2029 1986 1832 1672 1522 1422 1268 1234 1214

出力例 2

312590234

問題文

非負整数 N, M が与えられます。

10^{18} 以下の正整数 x であって x^x \equiv N \pmod M を満たすものが存在するか判定し、存在する場合はそのような x を 1 つ求めてください。

制約

• 0 \leq N < M \leq 10^9
• 入力される値はすべて整数

部分点

以下の制約を満たすデータセットに正解した場合には 1 点が与えられる。

• M が素数

入力例 1

3 7

出力例 1

5

5^5 = 3125 \equiv 3 \pmod 7 です。

入力例 2

2 6

出力例 2

-1

x^x \equiv 2 \pmod 6 なる 10^{18} 以下の正整数 x は存在しません。

問題文

正整数 N,A,B が与えられます。

\lbrace 1,\ldots,N \rbrace を区別のない 1 つ以上のグループに分けた族 \lbrace S_1,\ldots,S_K \rbrace を分割と呼びます。例えば、 \lbrace 1,2,3,4 \rbrace の分割 \lbrace \lbrace 1,3 \rbrace,\lbrace 2,4 \rbrace \rbrace,\lbrace \lbrace 2,4 \rbrace,\lbrace 1,3 \rbrace \rbrace は同じ分割とみなします。

分割 \lbrace S_1,\ldots,S_K \rbrace と相異なる正整数の組 \lbrace H_1,\ldots,H_K \rbrace について、源氏香の図を以下のように定義します。

• 各 1 \le i \le K について S_i に対応する 2|S_i|-1 本の線分を 2 次元平面上に描き、これを源氏香の図と呼ぶ。
  • x \in S_i について、(x,0),(x,H_i) 間を結ぶ。
  • 各 1 \le j \le |S_i|-1 について、(S_{i,j},H_i),(S_{i,j+1},H_i) 間を結ぶ。ここで、 S_{i,j} は S_i に含まれる j 番目に大きい整数。

また、次の条件を満たす分割を良い分割と呼びます。

• 任意の相異なる正整数の組 \lbrace H_1,\ldots,H_K \rbrace に対する源氏香の図について、描いた線分のみを通って各 1 \le x \le N の点 (x,0) が全て連結になる。

\lbrace 1,\ldots,N \rbrace の分割 \lbrace S_1,\ldots,S_K \rbrace であって各部分集合 S_i の個数が A 以上 B 以下であるもののうち、良い分割であるものの個数を 998244353 で割った余りを求めてください。

制約

• 入力は全て整数
• 1 \le A \le B \le N \le 10^5

入力例 1

6 1 4

出力例 1

20

良い分割の例として \lbrace \lbrace 1,4 \rbrace,\lbrace 2,6 \rbrace,\lbrace 3,5 \rbrace \rbrace が挙げられます。あり得る源氏香の図として以下の形があり、線分の交点も接続されていることに注意するとこれは連結になっています。

入力例 2

1897 6 18

出力例 2

238507463

答えを 998244353 で割った余りを出力してください。

問題文

この問題は output only です。また、非常に特殊なジャッジ形式に注意してください。

以下の問題を問題 A とします。 これは、 ABC367 の F 問題 と同じです。

長さ N の正整数列 A=(A_1,A_2,\dots,A_N), B=(B_1,B_2,\dots,B_N) が与えられます。
Q 個のクエリが与えられるので順に処理してください。 i 番目のクエリは以下で説明されます。

• 正整数 l_i,r_i,L_i,R_i が与えられる。数列 (A_{l_i},A_{l_i+1},\dots,A_{r_i}) を並び替えることで (B_{L_i},B_{L_i+1},\dots,B_{R_i}) に一致させることができるならば Yes を、できないならば No を出力せよ。

問題 A に対する以下の解法を、制約を満たすようなテストケースをひとつ挙げることにより撃墜してください。

• i = 1,2,\dots,N について、 f[i] を 1 以上 998244352 以下の一様ランダムな整数で定める。
• A の全ての要素について、 A_i = f[A_i] と置換する。
• B の全ての要素について、 B_i = f[B_i] と置換する。
• その後、全てのクエリについて Yes か No かを以下の通りに判定する。
  • \prod_{k=l_i}^{r_i} A_k \equiv \prod_{k=L_i}^{R_i} B_k が \rm{mod} 998244353 上で成立する時、またその時に限り、 Yes と判定する。

制約

• 1 \le N,Q
• N+Q \le 10^6
• 1 \le A_i,B_i \le N
• 1 \le l_i \le r_i \le N
• 1 \le L_i \le R_i \le N
• 入力は全て整数

問題文

正整数 N,M が与えられます。

非負整数からなる長さ N の数列 A について、次を満たす非負整数 X_{i,j}\ (1\leq j\leq i\leq N) が一意に存在します。

• X_{i,1}=A_i\ (1\leq i\leq N)
• X_{i,j}=X_{i-1,j-1}\oplus X_{i,j-1}\ (2\leq j\leq i\leq N)

ただし \oplus はビットごとの排他的論理和を表します。 このとき \sum_{i=1}^{N}\sum_{j=1}^{i}X_{i,j} の値を A の スコア とします。

S=1,2,\dots,M のそれぞれに対し、非負整数からなる長さ N の数列で総和が S であるもの全てについてのスコアの総和を 998244353 で割ったあまりを求めてください。

制約

• 1\leq N\leq 10^{9}
• 1\leq M\leq 10^{5}
• 入力は全て整数

部分点

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

• N \leq 3000, M = 1 を満たすデータセットに正解した場合 1 点が与えられる。
• N \leq 10^6, M = 1 を満たすデータセットに正解した場合追加で 1 点が与えられる。

入力例 1

4 1

出力例 1

18

例えば A=(0,1,0,0) のとき X_{i,j} は以下のようになりスコアは 5 です。

• X_{1,1}=0
• X_{2,1}=1,X_{2,2}=1
• X_{3,1}=0,X_{3,2}=1,X_{3,3}=0
• X_{4,1}=0,X_{4,2}=0,X_{4,3}=1,X_{4,4}=1

入力例 2

202515 1

出力例 2

631322682

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

入力例 3

1000000000 20

出力例 3

450736580
222005843
791558300
565944390
287066035
818826101
538663305
222889651
450257059
718428507
230132846
653810630
380943894
21756026
863202268
823515972
834078326
615162787
221193562
85328814

問題文

K, U, P, C からなる文字列 S が与えられます。正整数 k について、この S を k 回連続で並べた文字列を S^k と呼びます。

長さ L の K, U, P, C からなる文字列全体の集合 U を考えます ( U は 4^L 個の文字列からなります )。
S^k が U の全ての要素を (連続でなくともよい) 部分列として含む時、 k としてありうる最小値を求めてください。
但し、そのような k が存在しない場合は代わりに -1 と出力してください。

制約

• S は K, U, P, C からなる長さ 1 以上 5 \times 10^5 以下の文字列
• L は 1 \le L \le 10^{18} を満たす整数

入力例 1

KUPCCPUK
3

出力例 1

2

この入力では、 S= KUPCCPUK 、 L=3 です。

• S^1= KUPCCPUK 、 S^2= KUPCCPUKKUPCCPUK 、 \dots です。
• U の要素のうち、例えば KCC は S^1 に部分列として含まれます。
• U の要素のうち、例えば UUP は S^1 に部分列として含まれませんが、 S^2 には部分列として含まれます。
• U の 4^3 個の要素全てが S^2 に部分列として含まれます。

以上より、答えは 2 です。

入力例 2

UUUPPPCCC
4

出力例 2

-1

この入力では、 S= UUUPPPCCC 、 L=4 です。

KCPC は U の要素ですが、どのような正整数 k についても、 S^k が KCPC を部分列として含むことはありません。よって、 -1 と出力します。

入力例 3

PPCPCPKCPCPUUUUPKPCPKCPKUPCCKPPCPUKUPPPUPPUKUUKUUKPKPKPCUKKKUKUKUCPCCPUUUKCUPPCCKKKKCU
1000000000000000000

出力例 3

111111111111111112

問題文

整数 N と素数 P が与えられます。

K, Y, O, T の文字を N 個ずつ含む長さ 4N の文字列 S であって、 KYOTO を（連続する）部分文字列に含み TOKYO を（連続する）部分文字列に含まないものの個数を P で割った余りを求めてください。

制約

• 入力は全て整数
• 1 \le N \le 500
• 9 \times 10^8 \le P \le 10^9+7
• P は素数

部分点

以下の制約を満たすデータセットに正解した場合は 1 点が与えられる。

• N \le 50

入力例 1

2 998244353

出力例 1

24

入力例 2

10 1000000007

出力例 2

93856993

答えを P で割った余りを出力してください。

問題文

この問題は インタラクティブ な問題であり、 ジャッジは適応的(adaptive) です。詳しくは注意点を参照してください。

1 から N までの番号がついた N 点が、数直線上にこの順で並んでいます。
各 i (1\le i\le N-1) について、点 i と点 i+1 の距離は 2^{P_i} です。
N および P は入力で与えられます。

ジャッジシステムは 1\le x\le N を隠し持っています。
あなたは以下の質問を行うことができます。

• 整数 i (1\le i\le N) を選ぶ。 N 点のうち点 i が 点 x から何番目に近いかを聞く。
  ただし、距離の順位は 1-indexed であり、例えば i=x の場合 1 番目と数える。

\lfloor\log_{2}{N}\rfloor 回以内の質問で x を当ててください。

制約

• 2\le N\le 2 \times 10^{5}
• N は整数
• P は (1,2,\dots,N-1) の順列

入出力

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

最初に、 N,P を標準入力から受け取ってください。

N
P_1 P_2 \dots P_{N-1}

次に、 x が特定できるまで質問を繰り返してください。 質問は以下の形式で標準出力に出力してください。

? i

ここで、 i は 1 以上 N 以下の整数である必要があります。 これに対する応答は、次の形式で標準入力から与えられます。

r

ここで、 r は質問に対する答えです。ただし、不正な質問を行った、あるいは質問の回数が \lfloor\log_{2}{N}\rfloor 回を超えた場合は r は -1 となります。

ジャッジが -1 を返した場合、提出はすでに不正解とみなされています。この場合、ただちにプログラムを終了してください。

x が特定できたら、解答を以下の形式で出力してください。

! x

この出力の後、ただちにプログラムを終了してください。

注意点

• 出力を行うたびに、末尾に改行を入れて標準出力を flush してください。そうしなかった場合、ジャッジ結果が TLE や WA となる可能性があります。
• 解答を出力したら (または -1 を受け取ったら) ただちにプログラムを終了してください。そうしない場合、ジャッジ結果は不定です。
• 余計な改行は不正なフォーマットの出力とみなされることに注意してください。
• この問題のジャッジシステムは、適応的(adaptive)です。 つまり、ジャッジシステムは、任意のタイミングにおいて、整合性がとれる限り、 x として想定しているものを変更する可能性があります。詳しくは入出力例も参照してください。

入出力例

この入力では N=4,P=(2,1,3) であり、ジャッジシステムは最初 x=2 を想定しています。

問題文

1 から N までの整数が書かれたカードが合計で 3M-1 枚あり、各 1 \leq i \leq N について整数 i の書かれたカードは A_i 枚存在します。

あなたは1 から N までの整数 K を 1 つ選び、整数 K の書かれたカードを追加して以下の条件を満たそうとしています。

• 条件 : 同じ数字の書かれた 3 枚のカード、または連続した数字の書かれた 3 枚のカードを選び取り除くことを M 回繰り返して、持っているカードを空にすることが出来る。

条件を満たすことのできる K を全て列挙してください。

制約

• 入力は全て整数
• 1 \le N \le 5 \times 10^5
• 1 \le M \le 10^8
• 0 \leq A_i \leq 3M-1
• \sum A_i=3M-1

部分点

以下の制約を満たすデータセットに正解した場合は 1 点が与えられる。

• N \le 2000

入力例 1

5 4
0 4 2 2 3

出力例 1

2
2 5

例えば K=5 を追加したとき、\lbrace 2,2,2\rbrace,\lbrace 2,3,4\rbrace,\lbrace 3,4,5\rbrace,\lbrace 5,5,5\rbrace のように 4 つの組を作ることができます。

入力例 2

4 1
1 0 0 1

出力例 2

0

条件を満たす K が存在しないこともあります。

入力例 3

8 15
7 10 4 2 8 6 3 4

出力例 3

3
1 4 7

問題文

各成分が整数である N 行 N 列の行列 A = (A_{i, j}) であって以下の条件を満たすものが存在するか判定し、存在する場合は \max |A_{i, j}| が最小になるものを 1 つ出力してください。

• 各行の数の和が 0、すなわち任意の 1 \leq i \leq N に対して \sum_{j = 1}^{N} A_{i, j} = 0
• 各列の数の和が 0、すなわち任意の 1 \leq j \leq N に対して \sum_{i = 1}^{N} A_{i, j} = 0
• i \neq j のとき A_{i, j} \neq A_{j, i}

制約

• N は 1 以上 1000 以下の整数

入力例 1

3

出力例 1

Yes
1 -1 0 
0 1 -1 
-1 0 1 

A = ((1, -1, 0), (0, 1, -1), (-1, 0, 1)) は条件を満たす行列の 1 つです。

問題文

1 から N までの番号がついた、頂点 1 を根とする N 頂点の根付き木があります。i 番目の辺は頂点 A_i と頂点 B_i を結ぶ辺です。

各頂点には重みが付いており、頂点 v の重みは W_v です。

あなたの目標は次の操作を任意の回数行い、最終的に 1 頂点からなる木にすることです。

• 根から伸びるパスを 1 つ選び、含まれる辺を全て縮約して新しい根とする。そして、新しい根の重みをパスに含まれていた頂点の重みの総和 S に設定し、コストに S を加算する。

目標を達成する操作列で操作回数が最小となるもののうち、かかるコストの最小値と最大値を求めてください。

制約

• 入力は全て整数
• 2 \le N \le 2 \times 10^5
• 1 \le A_i,B_i \le N
• 1 \le W_v \le 10^8
• 入力で与えられるグラフは木

入力例 1

4
1 2
1 3
2 4
20 25 1 5

出力例 1

72 101

1 頂点の木にするための最小の操作回数は 2 回です。

最初にパス 1-2-4 を選ぶと、新しい根（頂点 5 とする）と頂点 3 がつながった状態になり、S=50 が根の重みになります。次に、パス 5-3 を選ぶと木が重み S=51 の 1 頂点となり操作が終了します。このときのコストは 50+51=101 となり、 2 回で目標を達成するときのコストの最大値をとります。

また、パス 1-3 （新しい根を頂点 5 とする）、パス 5-2-4 の順に操作するとコストは 21+51=72 となり、2 回で目標を達成するときのコストの最小値をとります。

入力例 2

10
2 4
3 8
7 9
6 3
2 1
9 5
9 6
3 10
9 2
19359725 62617217 96402215 25620070 46288197 40930485 37441368 32164537 69968419 79525817

出力例 2

1525009090 2231445426

問題文

1 枚の円形のピザがあり、その円周上には円周をちょうど N 等分するように、N 個の点 P_1, P_2, \cdots P_N があります。

最初、ピザに切れ目は入っておらず、次のルールに従って、ピザを M 回切断します。

• i (1 \le i \le M) 回目の切断では、実数 \theta を 0 \lt \theta \lt \pi を満たす実数の一様分布からランダムに選び、点 P_{A_i} におけるピザの円周の接線を 点 P_{A_i} を中心として反時計回りに \theta だけ回転させた直線に沿ってピザを切断する。

全ての切断が終了した後のピザの分割数の期待値を mod 998244353 で求めてください。

制約

• 入力は全て整数
• 1 \le N \le 998244352
• 1 \le M \le 3 \times 10^5
• 1 \le A_i \le N

入力例 1

4 2
1 3

出力例 1

748683268

ピザは \frac{3}{4} の確率で 3 分割、\frac{1}{4} の確率で 4 分割されるため、求める期待値は \frac{13}{4} となります。

入力例 2

2 2
1 1

出力例 2

3

配列 A は同じ整数を複数含むこともあります。

入力例 3

9 7
3 1 4 1 5 9 2

出力例 3

49296032