问题描述

JOI 高校的葵购买了一个新的走格子游戏。这个走格子游戏是由 $N+2$ 个方格按照横向排列而成的。这些方格从左边开始到右边分别标有编号从 $0$ 到 $N+1$。一开始，方格 $0$ 和方格 $N+1$ 上分别写有 X，方格 $i$ ($1 \leq i \leq N$) 上写有 $S_i$。其中，$S_i$ 是字符 . 或 #。

葵使用这个走格子游戏和一个棋子进行游戏。一开始，棋子被放置在方格 $A$ ($1 \leq A \leq N$) 上，且面向右边。其中，$S_A$ 是字符 .。每经过 $1$ 秒，葵都会将棋子向当前面朝方向移动 $1$ 个格子。

这个走格子游戏有如下规则：

• 当棋子站在标有 X 的方格时，棋子的朝向会翻转。
• 当棋子站在标有 . 的方格时，不会发生任何改变。
• 当棋子站在标有 # 的方格时，棋子的朝向会翻转，并且该方格上的字符会被修改为 .。因此，此后即使棋子站在该方格上，朝向也不会翻转。

需要注意的是，忽略棋子翻转和字符修改所需的时间。

给定走格子游戏和棋子的初始状态，编写一个程序来求解所有标有 # 的方格消失所需的时间。

约束条件

• $2 \leq N \leq 200,000$。
• $1 \leq A \leq N$。
• $S_i$ 是字符 . 或 # ($1 \leq i \leq N$)。
• 至少存在一个 $i$ ($1 \leq i \leq N$)，使得 $S_i$ 是字符 #。

子任务

1. ($40$ 分) $N \leq 3,000$。
2. ($60$ 分) 没有额外的约束。

---

输入

输入以以下格式从标准输入中给出。

$N$ $A$ $S$

其中，$S$ 是长度为 $N$ 的字符串，第 $i$ 个字符 ($1 \leq i \leq N$) 是 $S_i$。

输出

将标有 # 的方格全部消失所需的时间以一行输出到标准输出。

---

示例 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