왕복 주사위 말판놀이

문제

JOI 고등학교의 아오이는 새로운 주사위 말판놀이를 구입했다. 이 주사위 말판놀이는 $N+2$ 개의 칸이 가로로 한 줄로 늘어선 형태를 하고 있다. 이 칸들에는 왼쪽 끝 칸부터 오른쪽 끝 칸까지 순서대로 $0$ 부터 $N+1$ 까지의 번호가 붙어 있다. 처음에 칸 $0$ 과 칸 $N+1$ 에는 X 가, 칸 $i$ ($1 \le i \le N$) 에는 $S_{i}$ 가 쓰여 있다. 단, $S_{i}$ 는 문자 . 또는 # 이다.

아오이는 이 주사위 말판놀이와 $1$ 개의 말을 사용하여 놀고 있다. 처음에 말은 칸 $A$ ($1 \le A \le N$) 에 오른쪽을 향한 상태로 놓여 있다. 단, $S_{A}$ 는 문자 . 이다. 아오이는 $1$ 초가 지날 때마다 말을 향하고 있는 방향으로 $1$ 칸 이동시킨다.

이 주사위 말판놀이에는 다음과 같은 규칙이 설정되어 있다.

• X 가 쓰인 칸에 말이 올라가면 말의 방향이 반전된다.
• . 가 쓰인 칸에 말이 올라가더라도 아무 일도 일어나지 않는다.
• # 가 쓰인 칸에 말이 올라가면 말의 방향이 반전된다. 이때 이 칸에 쓰인 문자를 . 로 변경한다. 따라서 그 이후에는 이 칸에 말이 올라가더라도 방향이 반전되지 않는다.

또한, 말의 반전이나 문자의 변경에 걸리는 시간은 무시할 수 있다.

주사위 말판놀이와 말의 처음 상태가 주어졌을 때, # 가 쓰인 칸이 모두 없어질 때까지 걸리는 시간을 구하는 프로그램을 작성하시오.

제한

• $2 \le N \le 200\,000$.
• $1 \le A \le N$.
• $S_{i}$ 는 문자 . 또는 # 이다 ($1 \le i \le N$).
• $S_{A}$ 는 문자 . 이다.
• $S_{i}$ 가 문자 # 인 $i$ ($1 \le i \le N$) 가 적어도 $1$ 개 존재한다.

서브태스크

1. ($40$ 점) $N \le 3\,000$.
2. ($60$ 점) 추가 제약이 없다.

입력

입력은 다음 형식으로 표준 입력에서 주어진다.
$N$ $A$
$S$

단, $S$ 는 길이 $N$ 의 문자열이며, 그 $i$ 번째 문자 ($1 \le i \le N$) 는 $S_{i}$ 이다.

출력

표준 출력에 # 가 쓰인 칸이 모두 없어질 때까지 몇 초가 걸리는지를 $1$ 줄로 출력한다.

예제 입력 1

7 3
.#.#..#

예제 출력 1

8

시간이 경과함에 따라 주사위 말판놀이의 상태는 다음과 같이 변화한다. 단, 오른쪽을 향한 말이 놓인 칸을 >, 왼쪽을 향한 말이 놓인 칸을 < 로 나타낸다.

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

따라서 $8$ 초 만에 # 가 쓰인 칸이 모두 없어지므로 $8$ 을 출력한다.

예제 입력 2

4 1
.#.#

예제 출력 2

7

시간이 경과함에 따라 주사위 말판놀이의 상태는 다음과 같이 변화한다.

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

따라서 $7$ 초 만에 # 가 쓰인 칸이 모두 없어지므로 $7$ 을 출력한다.

예제 입력 3

6 6
#####.

예제 출력 3

35