레이팅 미적용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 つ存在する.
( 40 点) N ≦ 3 000 .
( 60 点) 追加の制約はない.
入力は以下の形式で標準入力から与えられる.
N A
S
ただし, S は長さ N の文字列で,その i 文字目 ( 1 ≦ i ≦ N ) は S i である.
標準出力に, # が書かれたマスがすべてなくなるまでに何秒かかるかを 1 行で出力せよ.
7 3
.#.#..#
8
4 1
.#.#
7
6 6
#####.
35