Problem Description

Aoi from JOI High School has purchased a new board game. This board game consists of $ N+2 $ squares arranged in a single row. These squares are numbered from $ 0 $ to $ N+1 $ starting from the leftmost square to the rightmost square. Initially, squares $ 0 $ and $ N+1 $ are marked with X, and square $ i $ ($1 \leq i \leq N$) is marked with $ S_i $, where $ S_i $ is either a . or a #.

Aoi is playing this board game with a single piece. Initially, the piece is placed on square $ A $ ($1 \leq A \leq N$) facing right. Note that $ S_A $ is a . . Aoi moves the piece one square in the direction it is facing every second.

The board game has the following rules:

• When the piece lands on a square marked with X, the direction of the piece is reversed.
• When the piece lands on a square marked with ., nothing happens.
• When the piece lands on a square marked with #, the direction of the piece is reversed, and the mark on this square is changed to .. Therefore, the piece will not reverse direction if it lands on this square again.

The time taken to reverse the direction of the piece or change the mark on a square is negligible.

Given the initial state of the board game and the piece, write a program to determine the time required until all squares marked with # are gone.

Input Format

The input is given from the standard input in the following format:

$ N $ $ A $ $ S $

where $ S $ is a string of length $ N $, and its $ i $ -th character ($1 \leq i \leq N$) is $ S_i $.

Output Format

Output the number of seconds required for all squares marked with # to disappear on a single line to the standard output.

Sample Input and Output

Sample Input #1

7 3
.#.#..#

Sample Output #1

8

Sample Input #2

4 1
.#.#

Sample Output #2

7

Sample Input #3

6 6
#####.

Sample Output #3

35

Notes/Hints

Constraints

• $2 \leq N \leq 200,000$.
• $1 \leq A \leq N$.
• $ S_i $ is either . or # ($1 \leq i \leq N$).
• $ S_A $ is . .
• There is at least one $ i $ ($1 \leq i \leq N$) such that $ S_i $ is #.

Subtasks

1. ($ 40 $ points) $N \leq 3,000$.
2. ($ 60 $ points) No additional constraints.

见题面 Input 部分

见题面 Output 部分