20369번 - X부터 시작하는 2세계 생활

제 이름은 베가입니다. 2세계라는 이름은 해당 세계가 2 x N 형태의 격자 모양인 데서 유래됐다고 합니다. 종종 지구의 사람들은 2세계의 어딘가로 소환되는데, 그 사람이 2세계에 있는 보물을 전부 모으면 지구로 다시 돌아갈 수 있다고 전해집니다. 하지만, 2세계는 너무 광활하여 최대한 빠르게 보물을 모으지 않으면 도중에 굶어 죽는다고 합니다. 얼마 전, 소환된 어느 야바위꾼과 농부도 그렇게 목숨을 잃었지요. 저는 2세계에서 목숨을 잃는 지구인들을 더 이상 두고 볼 수 없습니다. 오랜 정보 수집을 바탕으로 저는 마침내, 보물의 위치가 전부 표시된 2 x N 형태의 지도를 완성시켰습니다.

여러분들께 부탁이 있습니다. 1 ≤ i ≤ 2, 1 ≤ j ≤ N을 만족하는 모든 (i, j)쌍에 대해, (i, j)에 소환된 지구인이 모든 보물을 모을 때까지의 가장 빠른 시간을 알려주셨으면 합니다. 지구인은 상하좌우로 인접한 칸으로 이동하는 데에 1초가 걸린다고 합니다. 그리고 보물이 있는 칸에 도착하면, 그 보물은 0초 만에 즉시 회수된다고 합니다.

지구의 사람들을 구할 수 있게 도와주세요!

첫째 줄에 정수 N (1 ≤ N ≤ 200,000)이 주어진다.

둘째 줄부터 셋째 줄까지 베가가 완성한 2 x N 형태의 지도가 주어진다.

'#'은 보물이 있는 칸, '.'은 비어있는 칸을 의미한다. i+1번째 줄의 j번째 문자는 좌표 (i, j)에 대응된다.

1 ≤ i ≤ 2, 1 ≤ j ≤ N을 만족하는 모든 (i, j)쌍에 대해, (i, j)에 소환된 지구인이 모든 보물을 모을 때까지의 가장 빠른 시간을 출력하라.

i번째 줄의 j번째 정수는 좌표 (i, j)에서 소환된 경우에 대응된다.