회복의 여정

여러 경유지를 거치는 국제 여행 중이다. NWERC 진출을 기념하며 여행을 즐기는 중이다. 저비용 항공사로 항공편을 예약하는 경우가 많아, 출발 직전에 항공편이 취소되어 공항에 발이 묶일 위험이 늘 있다. 보통은 다음 항공편을 타면 되지만, NWERC에는 반드시 제시간에 도착해야 한다.

항공편 중 하나가 출발하려는 바로 그 순간 취소되고 나머지 항공편은 모두 계획대로 운항하면, 그 공항에서 최종 목적지까지 가는 새 일정을 예약한다. 항상 가장 빠른 경로를 고른다고 가정할 때, 최악의 경우 얼마나 늦어지는가?

첫 줄에 전체 항공편 수 $n$ ($1 \le n \le 10^6$)이 주어진다.

이후 $n$개 줄에 항공편 정보가 주어진다. $i$번째 줄에는 공백으로 구분된 네 개의 값이 있다.

• 출발 공항 코드 $s_i$ ($1 \le |s| \le 20$)
• ddhh:mm 형식의 출발 시각 ($1 \le d \le 365$, $0 \le hh \le 23$, $0 \le mm \le 59$)
• 도착 공항 코드 $t_i$ ($1 \le |t| \le 20$)
• ddhh:mm 형식의 도착 시각 ($1 \le d \le 365$, $0 \le hh \le 23$, $0 \le mm \le 59$)

다음 줄에는 행程에 포함된 항공편 수 $m$ ($1 \le m \le n$)이 주어진다. 마지막 줄에는 탑승할 순서대로 항공편 번호 $f_1 \ldots f_m$이 주어진다.

항공편은 항상 서로 다른 공항 사이를 오가며, 시간은 엄격하게 앞으로 흐른다. 행程의 연속한 두 항공편 $u$, $v$에 대해 $u$의 도착 시각은 $v$의 출발 시각보다 같거나 빠르다.

환승은 즉시 이루어진다. 공항에 도착한 같은 분에 바로 출발할 수 있다. 계획된 항공편이 취소되면, 정확히 같은 시각에 출발하는 다른 항공편에 탑승할 수 있다.

탑승 순간에 주어진 항공편 중 하나가 취소될 때 최대로 늦어질 수 있는 시간을 출력한다. 어떤 경우에도 지연이 없거나 일찍 도착할 수 있다면 $0$을 출력한다.

항상 목적지에 도착할 수 없다면 대신 stranded를 출력한다.