問題文

JOI 高校の葵は新しいすごろくを購入した．このすごろくは N+2 個のマスが横一列に並んだ形をしている．これらのマスには，左端のマスから右端のマスへと順に，0 から N+1 までの番号がついている．初め，マス 0 とマス N+1 には X が，マス i (1 \leqq i \leqq N) には S_i が書かれている．ただし，S_i は文字 . または # である．

葵はこのすごろくと 1 つの駒を使って遊んでいる．初め，駒はマス A (1 \leqq A \leqq N) に右を向いた状態で置かれている．ただし，S_A は文字 . である．葵は 1 秒経つごとに，駒を向いている方向へ 1 マス移動させる．

このすごろくには次のようなルールが設定されている．

• X が書かれたマスに駒が乗ると，駒の向きは反転する．
• . が書かれたマスに駒が乗ったとしても，何も起こらない．
• # が書かれたマスに駒が乗ると，駒の向きは反転する．このとき，このマスに書かれた文字を . に変更する．したがって，その後はこのマスに駒が乗ったとしても向きは反転しない．

なお，駒の反転や文字の変更にかかる時間は無視できる．

すごろくと駒の初めの状態が与えられたとき，# が書かれたマスがすべてなくなるまでに要する時間を求めるプログラムを作成せよ．

制約

• 2 \leqq N \leqq 200\,000．
• 1 \leqq A \leqq N．
• S_i は文字 . または # である (1 \leqq i \leqq N)．
• S_A は文字 . である．
• S_i が文字 # であるような i (1 \leqq i \leqq N) が少なくとも 1 つ存在する．

小課題

1. (40 点) N \leqq 3\,000．
2. (60 点) 追加の制約はない．

入力例 1

7 3
.#.#..#

出力例 1

8

時間が経過するにつれてすごろくの状態は次のように変化する．ただし，右向きの駒が置かれたマスを >，左向きの駒が置かれたマスを < で表す．

0.  X.#>#..#X
1.  X.#.<..#X
2.  X.#<...#X
3.  X.>....#X
4.  X..>...#X
5.  X...>..#X
6.  X....>.#X
7.  X.....>#X
8.  X......<X

したがって，8 秒で # が書かれたマスがすべてなくなるので，8 を出力する．

入力例 2

4 1
.#.#

出力例 2

7

時間が経過するにつれてすごろくの状態は次のように変化する．

0.  X>#.#X
1.  X.<.#X
2.  X<..#X
3.  >...#X
4.  X>..#X
5.  X.>.#X
6.  X..>#X
7.  X...<X

したがって，7 秒で # が書かれたマスがすべてなくなるので，7 を出力する．

入力例 3

6 6
#####.

出力例 3

35

問題文

ビ太郎はパンケーキ店で働いている．

この店で最も人気のあるメニューは N 枚のパンケーキが積み重なったパンケーキタワーである．店で作られているパンケーキには 3 種類の味があり，それぞれ A，B，C と呼ぶことにする．

ここで，パンケーキの並び方が次の条件を満たすようになっているパンケーキタワーを良いパンケーキタワーと呼ぶことにする．

• すべての味 A のパンケーキと味 B のパンケーキの組において，味 A のパンケーキが味 B のパンケーキより上にある．
• すべての味 A のパンケーキと味 C のパンケーキの組において，味 A のパンケーキが味 C のパンケーキより上にある．
• すべての味 B のパンケーキと味 C のパンケーキの組において，味 B のパンケーキが味 C のパンケーキより上にある．

例えば，パンケーキの味がそれぞれ上から順に AABBBC，ACC，BBBB となっているパンケーキタワーはどれも良いパンケーキタワーであるが，AABABCC，CA となっているパンケーキタワーはどれも良いパンケーキタワーではない．

盛り付け担当のビ太郎はパンケーキタワーに対して次の操作を行うことができる．

• 操作 k (2 \leqq k \leqq N)：上から k 枚目のパンケーキの下側にフライ返しを差し込み，そこから上のパンケーキをひっくり返す．すなわち，上から k 枚のパンケーキの並び方を反転させる．

例えば，パンケーキの味が上から順に ABCB となっているパンケーキタワーに操作 2，操作 3，操作 4 をそれぞれ行った場合，パンケーキの並び方は BACB，CBAB，BCBA となる．

今，Q 皿のパンケーキタワーがあり，i 皿目 (1 \leqq i \leqq Q) のパンケーキタワーはパンケーキの味が上から順に S_{i,1}S_{i,2} \cdots S_{i,N} となっている．ビ太郎はそれぞれのパンケーキタワーについて，できる限り少ない回数の操作で良いパンケーキタワーにしたい．

Q 皿のパンケーキタワーの並び方の情報が与えられるので，それぞれのパンケーキタワーについて，良いパンケーキタワーにするのに必要な操作の回数の最小値を求めるプログラムを作成せよ．

制約

• 2 \leqq N \leqq 13．
• 1 \leqq Q \leqq 100\,000．
• S_{i,j} は A，B，C のいずれかである (1 \leqq i \leqq Q，1 \leqq j \leqq N)．

小課題

1. (4 点) N \leqq 5，Q = 1．
2. (10 点) N \leqq 5．
3. (60 点) Q = 1．
4. (26 点) 追加の制約はない．

入力例 1

5 3
ABCBA
CCBAB
AAAAA

出力例 1

3
2
0

1 皿目のパンケーキタワーの場合，以下の 3 回の操作を行うことによって良いパンケーキタワーにすることが可能である．

1. 操作 4 を行う．パンケーキの味は上から順に BCBAA となる．
2. 操作 2 を行う．パンケーキの味は上から順に CBBAA となる．
3. 操作 5 を行う．パンケーキの味は上から順に AABBC となる．

2 回以下の操作によって良いパンケーキタワーにすることは不可能であるので，1 行目に 3 を出力する．

2 皿目のパンケーキタワーの場合，以下の 2 回の操作を行うことによって良いパンケーキタワーにすることが可能である．

1. 操作 5 を行う．パンケーキの味は上から順に BABCC となる．
2. 操作 2 を行う．パンケーキの味は上から順に ABBCC となる．

1 回以下の操作によって良いパンケーキタワーにすることは不可能であるので，2 行目に 2 を出力する．

3 皿目のパンケーキタワーの場合，既に良いパンケーキタワーになっているので操作を行う必要がない．したがって，3 行目に 0 を出力する．

入力例 2

2 5
AC
AC
AC
AC
AC

出力例 2

0
0
0
0
0

パンケーキの並び方が同じであるようなパンケーキタワーが複数個存在する場合もあることに注意せよ．

入力例 3

13 1
ABCCABCBACBAA

出力例 3

9

入力例 4

13 4
CCAAACBAAAABB
BBBCCBCCCBCBC
CCCAAAABBBBBB
AABCBCACBACBA

出力例 4

4
6
2
10

問題文

IOI 国には 2 個の町があり，それぞれ 1, 2 と番号がついている．

これらの町では合計 N 個のイベントが行われる．これらのイベントには 1 から N までの番号がついている．イベント i (1 \leqq i \leqq N) は町 P_i で開催され，開催時刻は時刻 S_i + 0.1 から時刻 S_i + 0.9 までである．ここで S_i は整数である．JOI 君がイベント i に参加するためには，時刻 S_i + 0.1 から時刻 S_i + 0.9 までの間，ずっと町 P_i にいる必要がある．

JOI 君はイベント巡りを行うことにした．イベント巡りではいくつかのイベントに参加し，必要ならば町と町の間を移動することもできる．JOI 君は時刻 0 からイベント巡りを開始する．このとき，好きな町から始めることができる．

JOI 君は町 1 と町 2 の間を双方向に移動することができる．2 つの町の間を移動するのにかかる時間は，JOI 君がその移動を開始する時刻までに参加したイベントの数を j として，D + K \times j となる．

イベントと町の間の移動に関する情報が与えられるので，JOI 君が参加できるイベントの数の最大値を求めるプログラムを作成せよ．

制約

• 1 \leqq N \leqq 200\,000．
• 1 \leqq D \leqq 10^{12}．
• 0 \leqq K \leqq 10^{12}．
• 1 \leqq P_i \leqq 2 (1 \leqq i \leqq N)．
• 1 \leqq S_i \leqq 10^{12} (1 \leqq i \leqq N)．
• S_i \neq S_j (1 \leqq i < j \leqq N)．
• 入力される値はすべて整数である．

小課題

1. (8 点) K = 0，N \leqq 20．
2. (11 点) K = 0，N \leqq 4\,000．
3. (24 点) K = 0．
4. (12 点) N \leqq 160．
5. (23 点) N \leqq 4\,000．
6. (22 点) 追加の制約はない．

入力例 1

5 3 0
1 1
1 2
1 10
2 5
2 6

出力例 1

4

例えば，以下のように行動することで，JOI 君は 4 個のイベントに参加することができる．

1. 時刻 0 において JOI 君は町 1 にいる．
2. 時刻 1.1 から時刻 1.9 まで町 1 でイベント 1 に参加する．
3. 時刻 2.1 から時刻 2.9 まで町 1 でイベント 2 に参加する．
4. 時刻 3 から時刻 6 まで時間 3 (= D + K \times 2) をかけて町 1 から町 2 に移動する．
5. 時刻 6.1 から時刻 6.9 まで町 2 でイベント 5 に参加する．
6. 時刻 7 から時刻 10 まで時間 3 (= D + K \times 3) をかけて町 2 から町 1 に移動する．
7. 時刻 10.1 から時刻 10.9 まで町 1 でイベント 3 に参加する．

どのように行動しても 5 個以上のイベントに参加することはできないため，4 を出力する．

この入力例はすべての小課題の制約を満たす．

入力例 2

7 2 3
2 2
1 8
1 10
1 11
2 23
2 24
2 25

出力例 2

6

例えば，以下のように行動することで，JOI 君は 6 個のイベントに参加することができる．

1. 時刻 0 において JOI 君は町 2 にいる．
2. 時刻 2.1 から時刻 2.9 まで町 2 でイベント 1 に参加する．
3. 時刻 3 から時刻 8 まで時間 5 (= D + K \times 1) をかけて町 2 から町 1 に移動する．
4. 時刻 8.1 から時刻 8.9 まで町 1 でイベント 2 に参加する．
5. 時刻 11.1 から時刻 11.9 まで町 1 でイベント 4 に参加する．
6. 時刻 12 から時刻 23 まで時間 11 (= D + K \times 3) をかけて町 1 から町 2 に移動する．
7. 時刻 23.1 から時刻 23.9 まで町 2 でイベント 5 に参加する．
8. 時刻 24.1 から時刻 24.9 まで町 2 でイベント 6 に参加する．
9. 時刻 25.1 から時刻 25.9 まで町 2 でイベント 7 に参加する．

どのように行動しても 7 個以上のイベントに参加することはできないため，6 を出力する．

この入力例は小課題 4, 5, 6 の制約を満たす．

入力例 3

12 153 0
1 155
2 861
1 646
1 218
2 450
2 56
1 932
2 295
2 863
1 612
2 38
2 768

出力例 3

8

この入力例はすべての小課題の制約を満たす．

入力例 4

15 89 104
1 4379
1 738
1 4862
1 4236
2 1416
1 9905
1 4775
2 4574
2 439
1 3956
1 955
2 8862
2 801
2 2299
2 575

出力例 4

11

この入力例は小課題 4, 5, 6 の制約を満たす．

問題文

JOI 市には 1 本の十分に長い道路がある．この道路は数直線とみなすことができ，各地点は 1 個の実数による座標で表される．また JOI 市にはこの道路に沿って N 個の施設が設置されており，座標の小さい順に 1 から N までの番号がつけられている．施設 i (1 \leqq i \leqq N) の位置は座標 A_i である．

JOI 市ではこれから施設の安全点検が行われる．施設 i には点検しなければならない項目が B_i 個ある．今，点検を行うことができる K 人の大工が集められた．安全点検の開始のとき，大工は全員が座標 0 にいる．点検が始まると，各大工は 1 分間で，次の 2 つの行動のどちらかをとることができる．

• 距離 1 だけ座標を移動する．
• 今いる座標にある施設の点検項目のうち，1 個の項目を選んで点検する．

安全点検を終えるとき，すべての建物のすべての点検項目が，1 人以上の大工によって点検されていなければならない．

大工の人数と施設の情報が与えられるので，安全点検を終えるのに最短で何分かかるかを求めるプログラムを作成せよ．

制約

• 1 \leqq N \leqq 100\,000．
• 1 \leqq K \leqq 10^{9}．
• 1 \leqq A_i \leqq 10^{9} (1 \leqq i \leqq N)．
• A_i < A_{i+1} (1 \leqq i \leqq N-1)．
• 1 \leqq B_i \leqq 10^{9} (1 \leqq i \leqq N)．
• 入力される値はすべて整数である．

小課題

1. (3 点) K = 1．
2. (15 点) K = 2．
3. (82 点) 追加の制約はない．

入力例 1

3 3
1 3 4
4 2 4

出力例 1

7

例えば，以下のように行動することで，7 分間で点検を終えることができる．ただし 3 人の大工に番号をつけて，それぞれ大工 1,2,3 と表す．

1. 大工 1,2,3 が座標 1 に移動する．
2. 大工 1,2,3 がそれぞれ施設 1 の点検を 1 項目ずつ行う．
3. 大工 1,2 が座標 2 に移動し，大工 3 が施設 1 の点検を 1 項目行う．
4. 大工 1,2 が座標 3 に移動し，大工 3 が座標 2 に移動する．
5. 大工 1,2 が座標 4 に移動し，大工 3 が座標 3 に移動する．
6. 大工 1,2 がそれぞれ施設 3 の点検を 1 項目ずつ行い，大工 3 が施設 2 の点検を 1 項目行う．
7. 大工 1,2 がそれぞれ施設 3 の点検を 1 項目ずつ行い，大工 3 が施設 2 の点検を 1 項目行う．

どのように行動しても 7 分未満で点検を終えることはできないので 7 を出力する．

入力例 2

6 1
1 4 5 6 11 15
12 5 9 8 10 4

出力例 2

63

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

入力例 3

6 2
1 4 5 6 11 15
12 5 9 8 10 4

出力例 3

35

この入力例は小課題 2,3 の制約を満たす.

入力例 4

6 5
1 4 5 6 11 15
12 5 9 8 10 4

出力例 4

19

問題文

JOI 国には N 人の議員がおり，1 から N までの番号がつけられている．JOI 国の大臣であるあなたは，議員の中にいるスパイを探し出そうとしている．あなたは各議員 i (1 \leqq i \leqq N) について次のような情報を得た．

• T_i = 1 のとき，議員 i はスパイである．
• T_i = 2 のとき，議員 i はスパイではない．
• T_i = 3 のとき，議員 i がスパイであるかどうかは不明である．

更に聞き取り調査を行った結果，新たに M 個の情報を得ることができた．j 番目の聞き取り調査の情報 (1 \leqq j \leqq M) は，議員 A_j (1 \leqq A_j \leqq N) が「議員 B_j (1 \leqq B_j \leqq N) はスパイであり，かつ議員 C_j (1 \leqq C_j \leqq N) はスパイでない」と証言したというものである．

ただし，議員 A_j がスパイであれば，j 番目の聞き取り調査の情報における証言は事実とは異なる．すなわち，もし議員 A_j がスパイであれば，「議員 B_j はスパイである」「議員 C_j はスパイでない」のうち，少なくとも一方は事実ではない．一方で，議員 A_j がスパイでないとき，j 番目の聞き取り調査の情報における証言は事実かもしれないし，そうでないかもしれない．

各議員の情報と，聞き取り調査の結果が与えられるので，それら N + M 個の情報が矛盾しているかを判定し，矛盾していないなら，それぞれの議員がスパイかどうかを求めるプログラムを作成せよ．N + M 個の情報と合致する答えが複数存在する場合は，そのうちどれを出力してもよい．

制約

• 1 \leqq N \leqq 300\,000．
• 1 \leqq M \leqq 300\,000．
• 1 \leqq T_i \leqq 3 (1 \leqq i \leqq N)．
• 1 \leqq A_j \leqq N (1 \leqq j \leqq M)．
• 1 \leqq B_j \leqq N (1 \leqq j \leqq M)．
• 1 \leqq C_j \leqq N (1 \leqq j \leqq M)．
• A_j \neq B_j (1 \leqq j \leqq M)．
• A_j \neq C_j (1 \leqq j \leqq M)．
• B_j \neq C_j (1 \leqq j \leqq M)．

小課題

1. (7 点) N \leqq 16，M \leqq 100．
2. (38 点) N \leqq 3\,000，M \leqq 3\,000．
3. (55 点) 追加の制約はない．

入力例 1

4 1
1 3 2 3
1 2 3

出力例 1

1
2
2
1

出力例 1 において議員 1 はスパイであり，「議員 2 はスパイであり，かつ議員 3 はスパイでない」という証言は議員 2 がスパイでないため事実と異なる．したがって，出力例 1 は与えられた情報に合致しており，正解となる．

この他に，議員 1 のみがスパイであり，他の議員はスパイではない，という答えも正解となる．

入力例 2

4 2
2 1 3 1
4 3 1
2 4 3

出力例 2

-1

議員 3 がスパイであるとすると，1 番目の聞き取り調査の情報と合致しない．議員 3 がスパイでないとすると，2 番目の聞き取り調査の情報と合致しない．情報が矛盾しているため，-1 を出力する．

入力例 3

3 2
1 2 2
2 1 3
2 3 1

出力例 3

1
2
2

入力例 3 において，すべての議員はスパイかそうでないかの情報が与えられている．これらは聞き取り調査の情報とも合致しているため，出力例 3 が唯一の正解となる．スパイでない議員の証言は，事実であるかもしれないし，そうでないかもしれないことに注意せよ．