第20回日本情報オリンピック　二次予選

2020年12月14日
情報オリンピック日本委員会

問題文

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

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

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

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

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

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

制約

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

小課題

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

入力

入力は以下の形式で標準入力から与えられる．
N A
S

ただし，S は長さ N の文字列で，その i 文字目 (1 ≦ i ≦ N) は S_i である．

出力

標準出力に，# が書かれたマスがすべてなくなるまでに何秒かかるかを 1 行で出力せよ．

入出力例

入力例 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