#include <iostream>
#include <algorithm>
using namespace std;
 

// If this structure is used for two-dimensional surface,
// it assumes that the face id[0] faces the positive direction of the Y axis,
// the face id[1] faces the positive direction of the X axis
// and id[2] is top of the dice.
struct Dice {
  int id[6], cnt;
  const static int f[3][3];

  Dice() { init(); }

  void init() {
    for(int i = 0; i < 6; ++i) {
      id[i] = i;
    }
    cnt = 0;
  }

  // type (0:spin, 1:rollX, 2:rollY)
  // dir 1( ccw     neg      pos   )
  //    -1( cw      pos      neg   )
  void rotate(int type, int dir = 1) {
    const int *v = f[type];
    int a,b,c,t; a=v[0]; b=v[1]; c=v[2]; t=id[type];
    if(dir < 0) swap(a,c);
    id[type]=id[a]; id[a]=id[b]; id[b]=id[c]; id[c]=t;
  }

  bool next() {
    ++cnt;
    if(cnt == 24) {
      rotate(0,-1);
      rotate(1,-1);
      cnt = 0;
      return false;
    }
    if(cnt == 4*3) {
      rotate(2,-1);
      rotate(0,-1);
    } else if(cnt%4 == 0) {
      rotate(2);
    } else {
      rotate(0);
    }
    return true;
  }

  void roll(int dir) {
    //const static int dx[] = {1,0,-1,0};
    //const static int dy[] = {0,1,0,-1};
    switch(dir) {
      case 0: rotate(1,-1); break;
      case 1: rotate(2, 1); break;
      case 2: rotate(1, 1); break;
      case 3: rotate(2,-1); break;
    }
  }

  bool operator < (const Dice &d) const {
    for(int i = 0; i < 3; ++i)
      if(id[i] != d.id[i]) return id[i] < d.id[i];
    return false;
  }

  void show() {
    cout << id[4] << " / \\ " << id[5] << endl;
    cout << " /   \\" << endl;
    cout << "|\\ " << id[2] << " /|" << endl;
    cout << "|" << id[0] << "\\ /" << id[1] << "|" << endl;
    cout << " \\ | /" << endl;
    cout << "  \\|/" << endl;
    cout << "   " << id[3] << endl;
  }
};
const int Dice::f[3][3] = {{4,5,1},{3,4,2},{5,3,0}};

//----------------------------------------------------------

#include <map>
#include <vector>
#include <queue>
#include <set>
#include <string>

struct State {
  int i, j;
  Dice dice;

  State() {}
  State(int i, int j, Dice dice)
    : i(i), j(j), dice(dice) {}

  bool operator < (const State &s) const {
    if(i != s.i) return i < s.i;
    if(j != s.j) return j < s.j;
    return dice < s.dice;
  }
};

struct State2 : public State {
  int p;
  State2() {}
  State2(int i, int j, Dice dice, int p)
    : State(i,j,dice), p(p) {}

  bool operator < (const State2 &s) const {
    if(p != s.p) return p < s.p;
    return (State)(*this) < (State)s;
  }
};

const int di[] = {0,1,0,-1};  
const int dj[] = {1,0,-1,0};
const int MAX_H = 13;
const int MAX_W = 13;
const int STATE_NUM = 5000;

int H, W;
int G[MAX_H][MAX_W];
string F[6];
int si, sj, gi, gj;
map<State, int> id;
map<int, State> rid;
set<State> canGoal;

vector<int> E[STATE_NUM], rE[STATE_NUM];

int getId(const State &s) {
  if(!id.count(s)) id[s] = (int)id.size()-1;
  rid[id[s]] = s;
  return id[s];
}

void init() {
  for(int i = 0; i < MAX_H; ++i) {
    for(int j = 0; j < MAX_W; ++j) {
      Dice dice;
      do {
        getId(State(i,j,dice));
      } while(dice.next());
    }
  }
}

void make() {
  for(int i = 0; i < STATE_NUM; ++i) {
    E[i].clear();
    rE[i].clear();
  }
  for(int i = 0; i < H; ++i) {
    for(int j = 0; j < W; ++j) {
      Dice dice;
      do {
        State s(i,j,dice);
        for(int d = 0; d < 4; ++d) {
          if(G[i][j] & (1<<d)) ; else continue;
          int ni = i + di[d];
          int nj = j + dj[d];
          if(ni < 0 || ni >= H) continue;
          if(nj < 0 || nj >= W) continue;
          Dice ndice = dice;
          ndice.roll(d);
          State t(ni,nj,ndice);
          E[id[s]].push_back(id[t]);
          rE[id[t]].push_back(id[s]);
        }
      } while(dice.next());
    }
  }
}

void bfs(State s, const vector<int> e[], set<State> &vis) {
  queue<State> que;
  que.push(s);
  vis.insert(s);
  while(!que.empty()) {
    s = que.front();
    que.pop();
    int sid = id[s];
    for(int i = 0; i < e[sid].size(); ++i) {
      State t = rid[e[sid][i]];
      if(vis.count(t)) continue;
      que.push(t);
      vis.insert(t);
    }
  }
}

int main() {
  init();
  while(cin >> H >> W) {
    for(int i = 0; i < H; ++i) {
      for(int j = 0; j < W; ++j) {
        char c;
        cin >> c;
        int &g = G[i][j];
        switch(c) {
          case '+': g = (1<<4)-1; break;
          case '|': g = (1<<1)|(1<<3); break;
          case '-': g = (1<<0)|(1<<2); break;
          case '<': g = (1<<2); break;
          case '>': g = (1<<0); break;
          case '^': g = (1<<3); break;
          case 'v': g = (1<<1); break;
          case '.': g = 0; break;
        }
      }
    }
    cin >> F[2];
    cin >> F[5];
    cin >> F[4];
    cin >> F[0];
    cin >> F[1];
    cin >> F[3];
    cin >> si >> sj;
    cin >> gi >> gj;
    --si; --sj; --gi; --gj;
    make();

    set<State2> vis[2];
    string res;
    set<State> can[2];
    bfs(State(si,sj,Dice()), E, can[0]);
    {
      Dice dice;
      do {
        bfs(State(gi,gj,dice), rE, can[1]);
      } while(dice.next());
    }

    {
      State2 s(si,sj,Dice(),0);
      if(can[0].count(s) && can[1].count(s)) {
        vis[0].insert(s);
      } else {
        cout << "no" << endl;
        continue;
      }
    }
    res = "";

    for(int p = 0; ; p = 1-p) {
      int n = 1-p;
      char mini = 127;
      for(set<State2>::iterator it = vis[p].begin();
          it != vis[p].end(); ++it) {
        if(it->i == gi && it->j == gj &&
           it->p == F[it->dice.id[2]].size()) {
          res += '$';
          break;
        }

        if(it->p == F[it->dice.id[2]].size()) {
          int sid = id[*it];
          for(int i = 0; i < E[sid].size(); ++i) {
            State t = rid[E[sid][i]];
            if(can[0].count(t) && can[1].count(t)) ; else continue;
            if(F[t.dice.id[2]][0] <= mini) {
              if(F[t.dice.id[2]][0] < mini) {
                vis[n].clear();
                mini = F[t.dice.id[2]][0];
              }
              vis[n].insert(State2(t.i, t.j, t.dice, 1));
            }
          }
        } else {
          if(F[it->dice.id[2]][it->p] <= mini) {
            if(F[it->dice.id[2]][it->p] < mini) {
              vis[n].clear();
              mini = F[it->dice.id[2]][it->p];
            }
            State2 tmp = *it;
            ++tmp.p;
            vis[n].insert(tmp); 
          }
        }
      }

      if(*res.rbegin() == '$') {
        res = res.substr(0, (int)res.size()-1);
        break;
      }
      if(mini == 127) {
        res = "no";
        break;
      }
      if(res.size() > STATE_NUM*13) {
        res = "infinite";
        break;
      }
      res += mini;
    }
    cout << res << endl;
  }
  return 0;
}
### Prompt

Create a solution in Cpp for the following problem:

There is a cube on a rectangle map with H-rows and W-columns grid. Two special squares a start and a goal are marked on the map. Initially, the cube is on the start square. Let's repeat to roll it and take it to the goal square. Rolling the cube means to select one of four edges which touch the map, and push the cube down without detaching the edge from the map. That is, there are four directions you can move the cube toward.

Directions where we can roll the cube are limited depending on each square. An instruction is written in each square and represented by a single character as follows:

'+'
all
'|'
only vertical
'-'
only horizontal
'<'
only to left
'>'
only to right
'^'
only to up
'v'
only to down
'.'
none

Regardless of instructions, it is not allowed to roll the cube to outside of the map.

On each face of the cube, a string is written. Let's output the string which concatenates strings written on the top face seen during the rollings from the start square to the goal square. Since there may be multiple paths that take the cube to the goal square, choose the minimal string in ascending lexicographic order.

Please note that there are cases where no path exists from the start to the goal, or the cases you can make the lexicographically minimal string infinitely longer.



Input

A data set has following format:

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

The first line of the input contains two integers H (1 ≤ H ≤ 12) and W (1 ≤ W ≤ 12), which indicate the number of rows and columns of the map respectively. The following W lines describe the map. The j-th character of the i-th line indicates the instruction of the square, which is placed on i-th row (from the top) and j-th column (from the left).

Then the following 6 lines describe the strings on each face of the cube. All of these strings are not empty and shorter than 12 characters (inclusive). In addition, they only consist of uppercase alphabets or digits. The faces where the strings are written are given as figure 1. Initially, the cube is placed on the start square in a direction as the face No. 1 is facing top and the upper direction of face No. 1 faces toward the top row of the map.

<image>

Figure 1. a net of a cube

The last two lines contain two integers each that indicate the row number and column number of the start square and the goal square in this order. You can assume that the start square and the goal square are always different.

Output

Print the lexicographically minimal string in a line. If there is no path, print "no" in a line. If you can make the lexicographically minimal string infinitely longer, print "infinite" in a line.

Examples

Input

1 3
+++
6
5
4
3
2
1
1 3
1 1


Output

621


Input

1 3
+++
1
2
3
4
5
6
1 3
1 1


Output

infinite


Input

1 3
...
1
2
3
4
5
6
1 3
1 1


Output

no


Input

3 3
->|
..v
.^<
JAG
2012
SUMMER
HOGE
HOGE
CAMP
1 1
2 2


Output

JAGSUMMERCAMP2012JAGSUMMER2012

### Response

```cpp
#include <iostream>
#include <algorithm>
using namespace std;
 

// If this structure is used for two-dimensional surface,
// it assumes that the face id[0] faces the positive direction of the Y axis,
// the face id[1] faces the positive direction of the X axis
// and id[2] is top of the dice.
struct Dice {
  int id[6], cnt;
  const static int f[3][3];

  Dice() { init(); }

  void init() {
    for(int i = 0; i < 6; ++i) {
      id[i] = i;
    }
    cnt = 0;
  }

  // type (0:spin, 1:rollX, 2:rollY)
  // dir 1( ccw     neg      pos   )
  //    -1( cw      pos      neg   )
  void rotate(int type, int dir = 1) {
    const int *v = f[type];
    int a,b,c,t; a=v[0]; b=v[1]; c=v[2]; t=id[type];
    if(dir < 0) swap(a,c);
    id[type]=id[a]; id[a]=id[b]; id[b]=id[c]; id[c]=t;
  }

  bool next() {
    ++cnt;
    if(cnt == 24) {
      rotate(0,-1);
      rotate(1,-1);
      cnt = 0;
      return false;
    }
    if(cnt == 4*3) {
      rotate(2,-1);
      rotate(0,-1);
    } else if(cnt%4 == 0) {
      rotate(2);
    } else {
      rotate(0);
    }
    return true;
  }

  void roll(int dir) {
    //const static int dx[] = {1,0,-1,0};
    //const static int dy[] = {0,1,0,-1};
    switch(dir) {
      case 0: rotate(1,-1); break;
      case 1: rotate(2, 1); break;
      case 2: rotate(1, 1); break;
      case 3: rotate(2,-1); break;
    }
  }

  bool operator < (const Dice &d) const {
    for(int i = 0; i < 3; ++i)
      if(id[i] != d.id[i]) return id[i] < d.id[i];
    return false;
  }

  void show() {
    cout << id[4] << " / \\ " << id[5] << endl;
    cout << " /   \\" << endl;
    cout << "|\\ " << id[2] << " /|" << endl;
    cout << "|" << id[0] << "\\ /" << id[1] << "|" << endl;
    cout << " \\ | /" << endl;
    cout << "  \\|/" << endl;
    cout << "   " << id[3] << endl;
  }
};
const int Dice::f[3][3] = {{4,5,1},{3,4,2},{5,3,0}};

//----------------------------------------------------------

#include <map>
#include <vector>
#include <queue>
#include <set>
#include <string>

struct State {
  int i, j;
  Dice dice;

  State() {}
  State(int i, int j, Dice dice)
    : i(i), j(j), dice(dice) {}

  bool operator < (const State &s) const {
    if(i != s.i) return i < s.i;
    if(j != s.j) return j < s.j;
    return dice < s.dice;
  }
};

struct State2 : public State {
  int p;
  State2() {}
  State2(int i, int j, Dice dice, int p)
    : State(i,j,dice), p(p) {}

  bool operator < (const State2 &s) const {
    if(p != s.p) return p < s.p;
    return (State)(*this) < (State)s;
  }
};

const int di[] = {0,1,0,-1};  
const int dj[] = {1,0,-1,0};
const int MAX_H = 13;
const int MAX_W = 13;
const int STATE_NUM = 5000;

int H, W;
int G[MAX_H][MAX_W];
string F[6];
int si, sj, gi, gj;
map<State, int> id;
map<int, State> rid;
set<State> canGoal;

vector<int> E[STATE_NUM], rE[STATE_NUM];

int getId(const State &s) {
  if(!id.count(s)) id[s] = (int)id.size()-1;
  rid[id[s]] = s;
  return id[s];
}

void init() {
  for(int i = 0; i < MAX_H; ++i) {
    for(int j = 0; j < MAX_W; ++j) {
      Dice dice;
      do {
        getId(State(i,j,dice));
      } while(dice.next());
    }
  }
}

void make() {
  for(int i = 0; i < STATE_NUM; ++i) {
    E[i].clear();
    rE[i].clear();
  }
  for(int i = 0; i < H; ++i) {
    for(int j = 0; j < W; ++j) {
      Dice dice;
      do {
        State s(i,j,dice);
        for(int d = 0; d < 4; ++d) {
          if(G[i][j] & (1<<d)) ; else continue;
          int ni = i + di[d];
          int nj = j + dj[d];
          if(ni < 0 || ni >= H) continue;
          if(nj < 0 || nj >= W) continue;
          Dice ndice = dice;
          ndice.roll(d);
          State t(ni,nj,ndice);
          E[id[s]].push_back(id[t]);
          rE[id[t]].push_back(id[s]);
        }
      } while(dice.next());
    }
  }
}

void bfs(State s, const vector<int> e[], set<State> &vis) {
  queue<State> que;
  que.push(s);
  vis.insert(s);
  while(!que.empty()) {
    s = que.front();
    que.pop();
    int sid = id[s];
    for(int i = 0; i < e[sid].size(); ++i) {
      State t = rid[e[sid][i]];
      if(vis.count(t)) continue;
      que.push(t);
      vis.insert(t);
    }
  }
}

int main() {
  init();
  while(cin >> H >> W) {
    for(int i = 0; i < H; ++i) {
      for(int j = 0; j < W; ++j) {
        char c;
        cin >> c;
        int &g = G[i][j];
        switch(c) {
          case '+': g = (1<<4)-1; break;
          case '|': g = (1<<1)|(1<<3); break;
          case '-': g = (1<<0)|(1<<2); break;
          case '<': g = (1<<2); break;
          case '>': g = (1<<0); break;
          case '^': g = (1<<3); break;
          case 'v': g = (1<<1); break;
          case '.': g = 0; break;
        }
      }
    }
    cin >> F[2];
    cin >> F[5];
    cin >> F[4];
    cin >> F[0];
    cin >> F[1];
    cin >> F[3];
    cin >> si >> sj;
    cin >> gi >> gj;
    --si; --sj; --gi; --gj;
    make();

    set<State2> vis[2];
    string res;
    set<State> can[2];
    bfs(State(si,sj,Dice()), E, can[0]);
    {
      Dice dice;
      do {
        bfs(State(gi,gj,dice), rE, can[1]);
      } while(dice.next());
    }

    {
      State2 s(si,sj,Dice(),0);
      if(can[0].count(s) && can[1].count(s)) {
        vis[0].insert(s);
      } else {
        cout << "no" << endl;
        continue;
      }
    }
    res = "";

    for(int p = 0; ; p = 1-p) {
      int n = 1-p;
      char mini = 127;
      for(set<State2>::iterator it = vis[p].begin();
          it != vis[p].end(); ++it) {
        if(it->i == gi && it->j == gj &&
           it->p == F[it->dice.id[2]].size()) {
          res += '$';
          break;
        }

        if(it->p == F[it->dice.id[2]].size()) {
          int sid = id[*it];
          for(int i = 0; i < E[sid].size(); ++i) {
            State t = rid[E[sid][i]];
            if(can[0].count(t) && can[1].count(t)) ; else continue;
            if(F[t.dice.id[2]][0] <= mini) {
              if(F[t.dice.id[2]][0] < mini) {
                vis[n].clear();
                mini = F[t.dice.id[2]][0];
              }
              vis[n].insert(State2(t.i, t.j, t.dice, 1));
            }
          }
        } else {
          if(F[it->dice.id[2]][it->p] <= mini) {
            if(F[it->dice.id[2]][it->p] < mini) {
              vis[n].clear();
              mini = F[it->dice.id[2]][it->p];
            }
            State2 tmp = *it;
            ++tmp.p;
            vis[n].insert(tmp); 
          }
        }
      }

      if(*res.rbegin() == '$') {
        res = res.substr(0, (int)res.size()-1);
        break;
      }
      if(mini == 127) {
        res = "no";
        break;
      }
      if(res.size() > STATE_NUM*13) {
        res = "infinite";
        break;
      }
      res += mini;
    }
    cout << res << endl;
  }
  return 0;
}
```