현대모비스 자율 주행 테스팅 2

이 문제는 현대모비스 자율 주행 테스팅 1 문제와 입력 형식이 다릅니다. 이 문제의 코드로 현대모비스 자율 주행 테스팅 1 문제를 해결할 수 없음에 유의하세요.

현대모비스는 모빌리티 플랫폼 프로바이더로서 SDV(Software Defined Vehicle)의 시대를 선도하고자 자율주행, 전동화, 커넥티비티 등 다양한 분야에서 SW 연구개발을 적극 진행하고 있다. 특히 현대모비스의 서산 주행 시험장에서는 자율 주행 자동차 개발을 위한 시범 주행이 한창이다. 샘플 주행 트랙은 모두 $M$종류이며, 각 샘플 주행 트랙에는 $1$번부터 $M$번까지의 번호가 매겨져 있다. $i$번 샘플 주행 트랙은 $2$행 $N\_i$열로 이루어져 있으며, 트랙의 각 칸은 도로 혹은 장애물 중 하나로 구성되어 있다. 시범 주행 트랙은 $K$개의 샘플 주행 트랙을 차례로 이어 붙여 만든 형태이다. 시범 주행 트랙에 쓰인 샘플 주행 트랙의 번호를 차례로 $A\_1,A\_2,\cdots ,A\_K$라 하면 시범 주행 트랙은 $2$행 $\sum\_{i=1}^KN\_{A\_i}$열의 형태가 된다. 자동차는 아래의 두 가지 방법을 이용하여 트랙 위를 이동할 수 있다.

• 차선 변경: 자동차가 같은 열의 다른 행으로 이동한다. 즉 자동차의 현재 위치가 $1$행 $j$열이라면 $2$행 $j$열로, $2$행 $j$열이라면 $1$행 $j$열로 이동한다.
• 직진: 자동차가 같은 행의 다음 열로 이동한다. 즉 자동차의 현재 위치가 $i$행 $j$열이라면 $i$행 $j+1$열로 이동한다.

두 경우 모두 도착하는 칸에 장애물이 있어서는 안 된다.

시범 주행은 시범 주행 트랙의 첫 번째 열에서 시작하며, 마지막 열에 도달하면 끝난다. 시작하는 칸이나 끝나는 칸은 자유롭게 정할 수 있다. 단, 시작하는 칸과 끝나는 칸은 모두 도로여야 한다. 자율 주행 자동차가 시범 주행 트랙을 완주할 수 있는지 판별하고, 완주하는 것이 가능하다면 완주하기 위해 필요한 최소 이동 횟수를 구하여라.

첫째 줄에 샘플 주행 트랙의 종류 수 $M$, 샘플 주행 트랙을 이어 붙인 횟수 $K$가 공백으로 구분되어 주어진다. $(1 \le M, K \le 200\ 000)$

둘째 줄에 시범 주행 트랙을 구성하는 샘플 주행 트랙의 번호 $A\_1, A\_2, \cdots, A\_K$가 공백으로 구분되어 차례대로 주어진다. $(1 \le A\_i \le M)$

셋째 줄부터 $2M$개의 줄에 걸쳐 $i$번 샘플 주행 트랙의 정보가 주어진다.

$2i+1$번째 줄에 $i$번 샘플 주행 트랙의 $1$행을 나타내는 길이가 $N\_i$인 문자열 $S\_{i1}$이 주어진다. $(1 \le N\_i \le 500\ 000)$

$2i+2$번째 줄에 $i$번 샘플 주행 트랙의 $2$행을 나타내는 길이가 $N\_i$인 문자열 $S\_{i2}$가 주어진다.

모든 문자열은 . 또는 #으로 구성됨이 보장된다. .은 도로, #은 장애물을 의미한다. $N\_i$의 합이 $500\ 000$ 이하임이 보장된다.

자율 주행 자동차가 시범 주행 트랙을 완주하기 위해 필요한 최소 이동 횟수를 출력하여라. 트랙을 완주하는 것이 불가능하면 대신 -1을 출력하여라.