問題文

高橋くんは寿司職人です。 今高橋くんの前には、0 から N-1 までの番号のついた N 個のシャリと、0 から M-1 までの番号のついた M 個のネタがあります。 シャリ i の重さは A_i です。 また、ネタ i の重さは B_i です。

高橋くんは、寿司の握りを 2 つ作りたいです。 1 つの握りは、ちょうど 1 つのシャリとネタを組み合わせることで作られます。

高橋くんは、2 つの握りの重さが等しくなるようにしたいです。 これが可能かどうか判定し、可能ならば作り方を 1 つ示してください。 なお、同じシャリやネタを 2 回使うことはできません。

制約

• 2 \leq N \leq 2 \times 10^5
• 2 \leq M \leq 2 \times 10^5
• 1 \leq A_i \leq 10^6
• A_i \neq A_j (i \neq j)
• 1 \leq B_i \leq 10^6
• B_i \neq B_j (i \neq j)
• 入力される値はすべて整数である。

入力例 1

3 4
1 2 4
3 6 10 15

出力例 1

0 1 2 0

シャリ 0 とネタ 1 を組み合わせた握りの重さは 1+6=7 です。 また、シャリ 2 とネタ 0 を組み合わせた握りの重さは 4+3=7 です。 よって、0 1 2 0 という出力は正解と判定されます。

入力例 2

3 3
3 2 1
30 20 10

出力例 2

-1

重さの等しい 2 つの握りを作ることはできません。

問題文

高橋くんは青木くんから、3N 頂点からなる有向グラフをもらいました。 このグラフの頂点には、x_0,x_1,\cdots,x_{N-1},y_0,y_1,\cdots,y_{N-1},z_0,z_1,\cdots,z_{N-1} と名前がついています。 このグラフの辺は全て、x の頂点から y の頂点へ向かう辺、または、y の頂点から z の頂点へ向かう辺です。 なお、多重辺は存在しません。

高橋くんはこのグラフで遊んでいるうちに、2N 個の長さ N の文字列 A_0,A_1,\cdots,A_{N-1},B_0,B_1,\cdots,B_{N-1} を得ました。 これらの文字列には、以下の性質があります。

• A_i の j 文字目 (0 \leq i,j \leq N-1) は、 頂点 x_i から頂点 y_j へ向かう辺が存在するときは 1、存在しないときは 0 である。
• B_i の j 文字目 (0 \leq i,j \leq N-1) は、 頂点 x_i から頂点 z_j へ向かうパスが存在するときは 1、存在しないときは 0 である。

高橋くんはうっかりこのグラフを壊してしまいましたが、上述の 2N 個の文字列は覚えています。 高橋くんの代わりに、もとのグラフとしてありうるものを 1 つ示してください。 ただし、高橋くんの記憶が間違っており、もとのグラフとしてありうるものが存在しない場合は、そのように指摘してください。

制約

• 1 \leq N \leq 300
• A_i は 0,1 からなる長さ N の文字列である。
• B_i は 0,1 からなる長さ N の文字列である。

入力例 1

3
010
001
101
110
010
011

出力例 1

011
110
010

例えば、高橋くんの記憶によれば頂点 x_2 から頂点 z_1 へ向かうパスが存在しますが、 出力例のグラフには、x_2 → y_2 → z_1 というパスが存在します。

入力例 2

3
010
001
101
110
010
001

出力例 2

-1

もとのグラフとしてありうるものは存在しません。

問題文

高橋くんは、長さ L の横に長いケーキを持っています。 このケーキの左端から距離 x の点を、座標 x の点と呼ぶことにします。 最初、このケーキの上には 1 つだけイチゴが置かれていて、その座標は X です。

高橋くんはこれから、N 回の操作を行います。 具体的には、i (0 \leq i \leq N-1) 回目の操作では以下のことをします。

• 座標 A_i にイチゴが置かれていない場合: 座標 A_i にイチゴを置く。
• 座標 A_i にイチゴが置かれている場合: 座標 A_i にあるイチゴを取り除く。

なお、それぞれの操作のあと、ケーキの上に 2 つ以上のイチゴが置かれていることが保証されます。

あるケーキの美しさを、以下のように定義します。

• 次の操作を何回でも自由に行えるとした時、「最も近い 2 つのイチゴの間の距離」としてありうる最大の値がケーキの美しさになる。
  • 座標 x に置かれているイチゴを、座標 L-x に移動する。なお、移動先に別のイチゴが置かれている場合は操作を行えない。

全ての i (0 \leq i \leq N-1) について、i 回目の操作のあとのケーキの美しさを求めてください。 なお、ケーキの美しさを求める際に、実際にイチゴを動かすことはありません。

制約

• 1 \leq N \leq 2 \times 10^5
• 1 \leq L \leq 10^9
• 0 \leq X \leq L
• 0 \leq A_i \leq L
• 全ての i (0 \leq i \leq N-1) について、i 回目の操作のあとにケーキの上に 2 つ以上のイチゴが置かれている。
• 入力される値はすべて整数である。

入力例 1

5 10 0
6
9
3
0
3

出力例 1

6
4
3
3
5

例えば、1 回目の操作が終わった時、ケーキの上には 3 つのイチゴが置かれており、その座標は 0,6,9 です。 座標 6 にあるイチゴを座標 4 に動かすと、イチゴの座標は 0,4,9 になります。 このとき、「最も近い 2 つのイチゴの間の距離」は 4 になり、これが最大です。 よって、このケーキの美しさは 4 です。

入力例 2

10 10 7
10
2
6
2
10
4
1
4
10
3

出力例 2

7
3
2
3
3
1
1
3
3
1

問題文

長さ N の整数列 A_0,A_1,\cdots,A_{N-1} と B_0,B_1,\cdots,B_{N-1} が与えられます。

全ての k (2 \leq k \leq N) について、次の問題を解いてください。

• 整数列 C_0,C_1,\cdots,C_{k-1} をつくる。 ここで、全ての i (0 \leq i \leq k-1) について、A_i \leq C_i \leq B_i を満たさなくてはならない。 「C_{i+1}-C_i (0 \leq i \leq k-2) の最大値」としてありうる最小の値はいくらか。

制約

• 1 \leq N \leq 2 \times 10^5
• 0 \leq A_i \leq B_i \leq 10^9
• 入力される値はすべて整数である。

入力例 1

4
0 0 1 2
2 1 3 3

出力例 1

-2
0
1

各 k について、「C_{i+1}-C_i の最大値」が最小になる整数列 C の例を示します。

• k=2: C=(2,0)
• k=3: C=(1,1,1)
• k=4: C=(1,1,1,2)

入力例 2

10
24 8 6 8 13 25 4 1 4 7
100 89 65 46 66 58 22 16 11 10

出力例 2

-92
-47
-30
-21
-10
-10
-10
-8
-4

問題文

高橋くんは、文字列 a に対して、以下の 2 種類の操作が行なえます。

• a の先頭、または末尾の 1 文字を削除する。これには X のコストがかかる。
• a の末尾に、好きな 1 文字を追加する。これには Y のコストがかかる。

高橋くんは今、N 個の文字列 S_0,S_1,\cdots,S_{N-1} を持っています。 高橋くんの友達の青木くんは、高橋くんに次の Q 個の質問を行います。

• 質問 i (0 \leq i \leq Q-1): 青木くんが文字列 T_i を見せる。 T_i に上記の操作を繰り返し行い、高橋くんの持っている N 個の文字列のいずれかに一致させるために必要なコストの最小値を求めよ。

多忙な高橋くんの代わりに、これらの質問に答えるプログラムを作成してください。

制約

• 1 \leq N \leq 10^5
• 1 \leq Q \leq 10^5
• 1 \leq X,Y \leq 10^9
• 1 \leq |S_i|
• \sum_{i=0}^{N-1} |S_i| \leq 5 \times 10^5
• S_i \neq S_j (i \neq j)
• 1 \leq |T_i|
• \sum_{i=0}^{Q-1} |T_i| \leq 5 \times 10^5
• T_i \neq T_j (i \neq j)
• 入力される数はすべて整数である。
• 入力される文字列はすべて英小文字からなる文字列である。

入力例 1

3 3 4 2
b
bcd
cd
a
ab
abc

出力例 1

6
4
6

例えば、質問 2 について考えると、以下のように操作するのが最適です。

• abc の先頭の文字を削除して、bc を得る。コストが 4 かかる。
• bc の末尾に d を追加して、bcd を得る。コストが 2 かかる。

入力例 2

4 3 1 100
a
aaaa
aaaaaaa
aaaaaaaaaa
aaa
aaaaaa
aaaaaaaaa

出力例 2

2
2
2

入力例 3

10 10 86 69
bbabbaaaaa
babaababab
bbababbbba
aaaaaaaaab
bbbbbbaabb
aabbabbbba
babbbbbbaa
baaabbaaaa
aaaaababbb
ababaaaaaa
bbaabbbbaa
abbbbabbbb
abbaaabaaa
ababaaaaab
bbaabbaaaa
abbbbbbabb
aabbbabbba
aaabbbaaaa
abbbababab
babaaabbbb

出力例 3

930
620
775
155
775
465
775
930
620
620

問題文

長さ N の数列 A_0,A_1,\cdots,A_{N-1} があります。 次の Q 個の質問に答えてください。

• 質問 i (0 \leq i \leq Q-1): 整数 L_i,R_i (0 \leq L_i < R_i \leq N) が与えられる。 (0,1,\cdots,N-1) の順列 p_0,p_1,\cdots,p_{N-1} であって、次の条件をみたすものの個数を求めよ。
  • 全ての j (L_i \leq j < R_i) について、p_j \neq A_j である。

ただし、答えは非常に大きくなることがあるので、998244353 で割ったあまりを出力してください。

制約

• 1 \leq N \leq 2000
• 0 \leq A_i \leq N-1
• 1 \leq Q \leq 2000
• 0 \leq L_i < R_i \leq N
• 入力される値はすべて整数である。

入力例 1

3 6
0 0 0
0 1
0 2
0 3
1 2
1 3
2 3

出力例 1

4
2
0
4
2
4

例えば質問 0 について考えると、条件をみたす順列は (1,0,2),(1,2,0),(2,0,1),(2,1,0) の 4 通りです。

入力例 2

3 6
0 1 2
0 1
0 2
0 3
1 2
1 3
2 3

出力例 2

4
3
2
4
3
4

入力例 3

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

出力例 3

2170680
2656080
1712520
2620800
2943360
2170680
2656080
2656080
2170680
2943360

問題文

AtCoder 株式会社は、0 から N-1 までの番号のついた N 個の島からなる会社です。 これらの島は、0 から N-2 までの番号のついた N-1 個の橋によって結ばれています。 橋 i は、島 A_i と島 B_i を双方向に結んでいます。 どの島からどの島へも、橋を渡っていくことでたどり着くことができます。

全ての島にはホテルがあります。 しかし現在、全てのホテルは営業休止中です。 そこで、AtCoder の観光部門の担当者である高橋くんは、これから Q 日間にわたるホテルの営業再開、休止の計画を立てました。 具体的には、i (0 \leq i \leq Q-1) 日目の朝に、以下のことが起こります。

• 島 X_i のホテルが営業休止している場合、そのホテルの営業を再開する。
• 島 X_i のホテルが営業している場合、そのホテルの営業を休止する。

なお、全ての i (0 \leq i \leq Q-1) について、i 日目の昼に営業しているホテルが 1 つ以上あることが保証されます。

橋 i が j 日目に重要であるとは、以下のことを意味します。

• j 日目の昼にホテルが営業している 2 つの島 a,b であって、島 a から島 b へ向かうためには橋 i を通らなければならないものが存在する。

それぞれの橋について、その橋が重要である日が Q 日間のうち何日あるか求めてください。

制約

• 2 \leq N \leq 2 \times 10^5
• 0 \leq A_i,B_i \leq N-1
• どの島からどの島へも、橋を渡っていくことでたどり着くことができる。
• 1 \leq Q \leq 2 \times 10^5
• 0 \leq X_i \leq N-1
• 全ての i (0 \leq i \leq Q-1) について、i 日目の昼に営業しているホテルが 1 つ以上存在する。
• 入力される値はすべて整数である。

入力例 1

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

出力例 1

2
3
3
3

例えば、2 日目の昼にホテルが営業している島は 島 0,2,4 であり、この日に重要な橋は 橋 1,2,3 です。

入力例 2

15 15
10 12
7 8
2 13
4 1
11 4
6 9
3 0
5 11
8 2
12 0
2 5
6 2
5 0
0 14
14
9
3
10
13
7
1
3
1
13
7
9
10
9
3

出力例 2

9
5
5
2
2
12
6
2
5
9
12
12
12
13

問題文

長さ N の数列 A_0,A_1,\cdots,A_{N-1} があります。 Q 個のクエリに答えてください。 具体的には、クエリ i (0 \leq i \leq Q-1) では整数 T_i,X_i,Y_i が与えられるので、以下のことをしてください。

• T_i=0 の時: A_{X_i} を Y_i で置き換える。
• T_i=1 の時: 次の条件をみたす整数の組 l,r (X_i \leq l < r \leq Y_i) の個数を答える。
  • A_{l},A_{l+1},\cdots,A_{r-1} が全て異なる。

制約

• 1 \leq N \leq 5 \times 10^5
• 1 \leq Q \leq 5 \times 10^5
• 0 \leq A_i \leq N-1
• 0 \leq T_i \leq 1
• 0 \leq X_i \leq N-1,\ 0 \leq Y_i \leq N-1 (T_i=0)
• 0 \leq X_i < Y_i \leq N (T_i=1)
• T_i=1 をみたす i が少なくとも 1 つ存在する。
• 入力される値はすべて整数である。

入力例 1

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

出力例 1

8
15
5

例としてクエリ 4 を考えます。 このクエリが与えられた時、A=(0,1,4,3,4) です。 また、条件をみたす l,r の組は、(l,r)=(2,3),(2,4),(3,4),(3,5),(4,5) の 5 個です。

入力例 2

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

出力例 2

53
3
10
6
23
34
31
57
16
116
3
94
28
3
10