Next Level

걸그룹 aespa는 광야의 한 점에서 출발해 목적지인 KOSMO에 도달하려 한다. 광야의 각 길에는 그 길을 통과하는 데 필요한 최소 레벨 제한이 있어서, aespa의 레벨이 그 값 이상이어야 길을 지날 수 있다. 어떤 지점에 과제 마왕이 있다면, 그 마왕을 처치해야 그 지점을 통과할 수 있다. aespa는 레벨 1로 시작하며, 과제 마왕의 고난을 이겨낼 때마다 Next Level로 나아가 레벨이 1 오른다. 레벨이 오른 aespa는 한층 더 자유롭게 움직일 수 있다.

과제 마왕의 고난을 이겨내려면 그 마왕의 과제에 쓰이는 알고리즘을 미리 알고 있어야 한다. 이겨내면 0개 또는 1개의 알고리즘을 익힐 수 있다. 과제에 필요한 알고리즘이 없을 수도 있다.

그런데 aespa의 적 Black Mamba가 지도를 조각조각 찢어 버렸다. 다행히 aespa의 멤버 카리나가 조각들이 처음에 어떻게 배열되어 있었는지 기억해냈다. 카리나의 기억대로 지도를 다시 만들고, aespa가 지도의 맨 왼쪽 위 지점에서 출발해 맨 오른쪽 아래 지점인 KOSMO에 닿을 수 있는지 알아보자.

조각은 네 종류가 있으며, 과제 마왕은 항상 조각의 중심에만 위치한다. aespa는 지도에 그려진 선을 통해서만 이동할 수 있다. 단, aespa는 과거를 돌아보지 않으므로 한 번 지난 지점은 다시 지나지 않는다. 파란 화살표로 표시된 길만큼 이동하는 데 하루가 걸리며, aespa를 쫓아오는 Black Mamba를 피하려면 18일 이내에 KOSMO에 도착해야 한다. 정확히 18일 후에 도착해도 된다.

첫 줄에 $N$이 주어진다. 지도는 $N \times N$ 격자로 나뉘어 있다. ($1 \le N \le 4$)

다음 $N$개의 줄에 지도의 조각이 A, B, C, D 중 하나로 한 줄에 $N$개씩 주어진다.

그 다음 $N$개의 줄에 각 조각의 최소 레벨 제한이 주어진다. 레벨 제한은 1 이상 16 이하의 정수이다. 어떤 조각에 있는 길을 건너려면 aespa의 레벨이 그 조각의 레벨 제한 이상이어야 한다. 길이 두 조각에 맞닿아 있으면 두 레벨 제한 중 높은 쪽을 따른다.

이어서 다음 $N$개의 줄에 각 조각의 과제 마왕 정보가 주어진다. 각 조각의 정보는 세 개의 문자열로 표현된다.

• 첫 번째 문자열은 조각의 중심에 과제 마왕이 있으면 1, 없으면 0이다.
• 두 번째 문자열은 그 과제 마왕의 과제에 필요한 알고리즘이다. 과제 마왕이 없거나 필요한 알고리즘이 없으면 0으로 표현된다.
• 세 번째 문자열은 그 과제 마왕의 고난을 이겨냈을 때 익힐 수 있는 알고리즘이다. 과제 마왕이 없거나 익힐 수 있는 알고리즘이 없으면 0으로 표현된다.

다음 줄에는 aespa가 처음에 알고 있던 알고리즘의 개수 $a$가 주어지고, 다음 줄에 그 알고리즘들이 나열된다. ($0 \le a \le 4$)

모든 알고리즘은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있으며, 문제에 등장하는 서로 다른 알고리즘은 최대 10개이다.

aespa가 KOSMO에 도달할 수 있으면 Dreams Come True를, 도달할 수 없으면 -1을 출력한다.