Move on Dice

A cube sits on a rectangular map with H rows and W columns. The map has one start square and one goal square. The cube starts on the start square, and you roll it until it reaches the goal square.

To roll the cube, pick one of the four bottom edges that touch the map and tip the cube over that edge without lifting the edge off the map. So the cube can move in four directions. The instruction character on each square limits which of those directions are allowed:

• '+': all directions
• '|': only up and down
• '-': only left and right
• '<': only left
• '>': only right
• '^': only up
• 'v': only down
• '.': no direction

The cube can never roll outside the map, whatever the instruction character says.

Each face of the cube has a string written on it. While the cube rolls from the start square to the goal square, record the string on the top face at each square it occupies, and concatenate them in order. There may be several paths to the goal, so output the lexicographically smallest concatenated string. Some inputs have no path to the goal. Others allow the lexicographically smallest string to keep getting longer without limit.

The cube starts with face 1 on top, and the upper edge of face 1 points toward the top row of the map. Figure 1 shows the net of the cube.

Figure 1. A net of the cube

The first line contains two integers H and W (1 ≤ H ≤ 12, 1 ≤ W ≤ 12). The next H lines describe the map. The j-th character of the i-th line is the instruction for the square in row i and column j.

The next 6 lines give the strings T1 through T6 written on the faces of the cube. Each string is non-empty, has at most 12 characters, and contains only uppercase letters and digits. The faces are numbered as in Figure 1.

The last two lines each contain two integers. The first gives the row and column of the start square, RS CS. The second gives the row and column of the goal square, RD CD. The start and goal squares are always different.

H W
C11 ... C1W
...
CH1 ... CHW
T1
...
T6
RS CS
RD CD

Print the lexicographically smallest string on one line. If no path reaches the goal, print no. If the lexicographically smallest string can be made arbitrarily long, print infinite.