Next Level

Girl group aespa starts from one point in the wilderness and wants to reach the destination, KOSMO. Each road in the wilderness has a minimum level requirement, and aespa must be at or above that level to use it. If a task demon stands at a point, aespa must defeat that demon to pass through the point. aespa starts at level 1. Each time aespa overcomes a task demon, aespa moves on to the Next Level and gains 1 level. A stronger aespa can move more freely.

To defeat a task demon, aespa must already know the algorithm used in that demon's task. After defeating the demon, aespa may learn 0 or 1 algorithm. A task may require no algorithm.

Black Mamba, an enemy of aespa, tore the map into pieces. Fortunately, aespa member Karina remembers how the pieces were arranged at first. Rebuild the map as Karina remembers it, and find out whether aespa can start at the top-left point of the map and reach KOSMO at the bottom-right point.

There are four kinds of pieces. A task demon is always located at the center of a piece. aespa can move only along the lines drawn on the map. aespa never looks back, so aespa never passes through a point it has already visited. Moving along a road marked by a blue arrow takes one day. aespa must reach KOSMO within 18 days to escape Black Mamba, who is following aespa. Arriving at KOSMO exactly on day 18 is allowed.

The first line contains $N$. The map is a $N \times N$ grid. ($1 \le N \le 4$)

The next $N$ lines give the pieces of the map, one of A, B, C, D per cell, with $N$ pieces per line.

The next $N$ lines give the minimum level requirement of each piece. Each requirement is an integer from 1 to 16. To cross a road in a piece, aespa's level must be at least that piece's requirement. If a road touches two pieces, the higher requirement applies.

The next $N$ lines give the task demon information for each piece. Each piece is described by three strings.

• The first string is 1 if a task demon stands at the center of the piece, and 0 otherwise.
• The second string is the algorithm required by that demon's task. It is 0 if there is no demon or the task requires no algorithm.
• The third string is the algorithm learned after defeating that demon. It is 0 if there is no demon or no algorithm is learned.

The next line contains the number $a$ of algorithms aespa knows at the start. ($0 \le a \le 4$) The following line lists those algorithms.

Every algorithm consists of 1 to 20 lowercase English letters. At most 10 distinct algorithms appear in the problem.

If aespa can reach KOSMO, print Dreams Come True. Otherwise, print -1.