Aoi, học sinh trường trung học JOI, vừa mua một bộ trò chơi sugoroku mới. Bàn chơi gồm \(N+2\) ô xếp thành một hàng ngang, được đánh số từ \(0\) đến \(N+1\) từ trái sang phải. Ban đầu, hai ô \(0\) và \(N+1\) ghi ký tự X; ô \(i\) (\(1 \le i \le N\)) ghi ký tự \(S_i\), là . hoặc #.

Aoi chơi bằng một quân cờ. Ban đầu, quân cờ được đặt ở ô \(A\) (\(1 \le A \le N\)), quay sang phải. Ký tự \(S_A\) là .. Cứ sau mỗi giây, Aoi di chuyển quân cờ một ô theo hướng quân cờ đang quay.

Trò chơi có các quy tắc sau:

• Khi quân cờ đến ô ghi X, nó đổi sang hướng ngược lại.
• Khi quân cờ đến ô ghi ., không có gì xảy ra.
• Khi quân cờ đến ô ghi #, nó đổi sang hướng ngược lại, đồng thời ký tự trên ô đó được đổi thành .. Vì vậy, những lần sau khi quân cờ đến ô này, nó không đổi hướng nữa.

Thời gian đổi hướng và thay đổi ký tự được xem là không đáng kể.

Cho trạng thái ban đầu của bàn chơi và quân cờ, hãy viết chương trình tính thời gian cần thiết để không còn ô nào ghi #.

Dữ liệu vào

Dòng thứ nhất chứa hai số nguyên \(N, A\).

Dòng thứ hai chứa xâu \(S\) có độ dài \(N\), trong đó ký tự thứ \(i\) (\(1 \le i \le N\)) là \(S_i\).

Dữ liệu ra

In ra trên một dòng số giây cần thiết để không còn ô nào ghi #.

Ràng buộc

• \(2 \le N \le 200\,000\).
• \(1 \le A \le N\).
• \(S_i\) là . hoặc # với mọi \(1 \le i \le N\).
• \(S_A\) là ..
• Có ít nhất một chỉ số \(i\) (\(1 \le i \le N\)) mà \(S_i\) là #.

Phân nhóm

Mọi phân nhóm đều thỏa mãn các ràng buộc chung ở trên.

1. (40 điểm) \(N \le 3000\).
2. (60 điểm) Không có ràng buộc bổ sung.

Ví dụ

7 3
.#.#..#

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

4 1
.#.#

7

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

6 6
#####.

35

Nguồn

Bản dịch tiếng Việt từ đề gốc tiếng Nhật của Ủy ban Olympic Tin học Nhật Bản. Đề gốc và bản dịch được cung cấp theo giấy phép CC BY-SA 4.0.