题目描述

JOI 高中的葵购买了一条新的滑道。该滑道由 $N+2$ 个格子横向排列组成。这些格子从左至右依次编号为 $0$ 到 $N+1$。初始时，格子 $0$ 和格子 $N+1$ 上写有字母 x，而格子 $i$（$1 \le i \le N$）上写有字符 $S_i$。其中，$S_i$ 为一个字母或符号 #。

葵使用这条滑道和一个棋子进行游戏。初始时，棋子位于格子 $A$（$1 \le A \le N$），且朝向右方。注意，$S_A$ 必须是一个字母。葵每隔 $1$ 秒钟，将棋子向其当前朝向的方向移动 $1$ 格。

滑道上设定有如下规则：

• 当棋子落在写有 x 的格子上时，棋子的朝向会反转。
• 当棋子落在写有 . 的格子上时，不会发生任何变化。
• 当棋子落在写有 # 的格子上时，棋子的朝向会反转，且该格子上的字符会变为 .。此后，即使棋子再次落在该格子上，朝向也不会再反转。

此外，棋子反转方向或字符变更所耗费的时间可忽略不计。

当给定滑道与棋子的初始状态时，请编写程序，计算所有写有 # 的格子均变为 . 所需的时间。

输入格式

输入通过标准输入以如下格式给出：

$N$ $A$

$S$

其中，$S$ 是一个长度为 $N$ 的字符串，其第 $i$ 个字符（$1 \le i \le N$）为 $S_i$。

输出格式

在标准输出中，输出一行：从开始到所有写有 # 的格子均变为 . 所需的秒数。

7 3
.#.#..#

8

4 1
.#.#

7

6 6
#####.

35

提示

样例 1 解释

随着时间的推移，棋盘的状态将发生如下变化。将右向棋子所在的格子用 > 表示，将左向棋子所在的格子用 < 表示：

 X.#>#..#X
 X.#.<..#X
 X.#<...#X
 X.>....#X
 X..>...#X
 X...>..#X
 X....>.#X
 X.....>#X
 X......<X

样例 2 解释

 X>#.#X
 X.<.#X
 X<..#X
 >...#X
 X>..#X
 X.>.#X
 X..>#X
 X...<X

数据范围

• $2 \le N \le 200\,000$。
• $1 \le A \le N$。
• $S_i$ 为一个字母或符号 #（$1 \le i \le N$）。
• $S_A$ 为一个字母。
• 至少存在一个 $i$（$1 \le i \le N$），使得 $S_i$ 为 #。

子任务

1. （40 分）$N \le 3\,000$；
2. （60 分）无额外约束。

翻译由 Qwen3-235B 完成