Problem: You are playing the following game. There are n points on a plane. They are the vertices of a regular n-polygon. Points are labeled with integer numbers from 1 to n. Each pair of distinct points is connected by a diagonal, which is colored in one of 26 colors. Points are denoted by lowercase English letters. There are three stones positioned on three distinct vertices. All stones are the same. With one move you can move the stone to another free vertex along some diagonal. The color of this diagonal must be the same as the color of the diagonal, connecting another two stones. 

Your goal is to move stones in such way that the only vertices occupied by stones are 1, 2 and 3. You must achieve such position using minimal number of moves. Write a program which plays this game in an optimal way.

Input

In the first line there is one integer n (3 ≤ n ≤ 70) — the number of points. In the second line there are three space-separated integer from 1 to n — numbers of vertices, where stones are initially located.

Each of the following n lines contains n symbols — the matrix denoting the colors of the diagonals. Colors are denoted by lowercase English letters. The symbol j of line i denotes the color of diagonal between points i and j. Matrix is symmetric, so j-th symbol of i-th line is equal to i-th symbol of j-th line. Main diagonal is filled with '*' symbols because there is no diagonal, connecting point to itself.

Output

If there is no way to put stones on vertices 1, 2 and 3, print -1 on a single line. Otherwise, on the first line print minimal required number of moves and in the next lines print the description of each move, one move per line. To describe a move print two integers. The point from which to remove the stone, and the point to which move the stone. If there are several optimal solutions, print any of them.

Examples

Input

4
2 3 4
*aba
a*ab
ba*b
abb*


Output

1
4 1


Input

4
2 3 4
*abc
a*ab
ba*b
cbb*


Output

-1

Note

In the first example we can move stone from point 4 to point 1 because this points are connected by the diagonal of color 'a' and the diagonal connection point 2 and 3, where the other stones are located, are connected by the diagonal of the same color. After that stones will be on the points 1, 2 and 3.

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
const double pi = acos(0.0) * 2.0;
const double eps = 1e-12;
const int step[8][2] = {{1, 0}, {-1, 0}, {0, 1},  {0, -1},
                        {1, 1}, {1, -1}, {-1, 1}, {-1, -1}};
template <class T>
inline T abs1(T a) {
  return a < 0 ? -a : a;
}
template <class T>
inline T max1(T a, T b) {
  return a > b ? a : b;
}
template <class T>
inline T max1(T a, T b, T c) {
  return max1(max1(a, b), c);
}
template <class T>
inline T max1(T a, T b, T c, T d) {
  return max1(max1(a, b, c), d);
}
template <class T>
inline T max1(T a, T b, T c, T d, T e) {
  return max1(max1(a, b, c, d), e);
}
template <class T>
inline T min1(T a, T b) {
  return a > b ? a : b;
}
template <class T>
inline T min1(T a, T b, T c) {
  return min1(min1(a, b), c);
}
template <class T>
inline T min1(T a, T b, T c, T d) {
  return min1(min1(a, b, c), d);
}
template <class T>
inline T min1(T a, T b, T c, T d, T e) {
  return min1(min1(a, b, c, d), e);
}
template <class T>
inline T lowb(T num) {
  return num & (-num);
}
inline int jud(double a, double b) {
  if (abs(a) < eps && abs(b) < eps)
    return 0;
  else if (abs1(a - b) / abs1(a) < eps)
    return 0;
  if (a < b) return -1;
  return 1;
}
template <typename t>
inline int jud(t a, t b) {
  if (a < b) return -1;
  if (a == b) return 0;
  return 1;
}
template <typename it, typename t1>
inline int find(t1 val, it a, int na, bool f_small = 1, bool f_lb = 1) {
  int be = 0, en = na - 1;
  if (*a <= *(a + na - 1)) {
    if (f_lb == 0)
      while (be < en) {
        int mid = (be + en + 1) / 2;
        if (jud(*(a + mid), val) != 1)
          be = mid;
        else
          en = mid - 1;
      }
    else
      while (be < en) {
        int mid = (be + en) / 2;
        if (jud(*(a + mid), val) != -1)
          en = mid;
        else
          be = mid + 1;
      }
    if (f_small && jud(*(a + be), val) == 1) be--;
    if (!f_small && jud(*(a + be), val) == -1) be++;
  } else {
    if (f_lb)
      while (be < en) {
        int mid = (be + en + 1) / 2;
        if (jud(*(a + mid), val) != -1)
          be = mid;
        else
          en = mid - 1;
      }
    else
      while (be < en) {
        int mid = (be + en) / 2;
        if (jud(*(a + mid), val) != 1)
          en = mid;
        else
          be = mid + 1;
      }
    if (!f_small && jud(*(a + be), val) == -1) be--;
    if (f_small && jud(*(a + be), val) == 1) be++;
  }
  return be;
}
inline int bitnum(unsigned int nValue) { return __builtin_popcount(nValue); }
inline int bitnum(int nValue) { return __builtin_popcount(nValue); }
inline int bitnum(unsigned long long nValue) {
  return __builtin_popcount(nValue) + __builtin_popcount(nValue >> 32);
}
inline int bitnum(long long nValue) {
  return __builtin_popcount(nValue) + __builtin_popcount(nValue >> 32);
}
inline int bitmaxl(unsigned int a) {
  if (a) return 0;
  return 32 - __builtin_clz(a);
}
inline int bitmaxl(int a) {
  if (a) return 0;
  return 32 - __builtin_clz(a);
}
inline int bitmaxl(unsigned long long a) {
  int temp = a >> 32;
  if (temp) return 32 - __builtin_clz(temp) + 32;
  return bitmaxl(int(a));
}
inline int bitmaxl(long long a) {
  int temp = a >> 32;
  if (temp) return 32 - __builtin_clz(temp) + 32;
  return bitmaxl(int(a));
}
long long pow(long long n, long long m, long long mod = 0) {
  if (m < 0) return 0;
  long long ans = 1;
  long long k = n;
  while (m) {
    if (m & 1) {
      ans *= k;
      if (mod) ans %= mod;
    }
    k *= k;
    if (mod) k %= mod;
    m >>= 1;
  }
  return ans;
}
const int maxn = 75;
int dp[maxn][maxn][maxn][4];
int mp[maxn][maxn];
int a, b, c;
int q[maxn * maxn * maxn][3], lq, rq;
int n;
int ans[maxn * maxn * maxn][3];
inline void relax(int &a, int &b, int &c) {
  if (a > b) swap(a, b);
  if (a > c) swap(a, c);
  if (b > c) swap(b, c);
}
inline bool canfind(int x, int a, int b, int c) {
  return x == a || x == b || x == c;
}
inline void justdoit(int a, int b, int c) {
  int ta = a, tb = b, tc = c;
  relax(ta, tb, tc);
  for (int i = 0; i < n; i++)
    if (i != b && i != c && mp[a][i] == mp[b][c]) {
      int ra = i, rb = b, rc = c;
      relax(ra, rb, rc);
      if (dp[ra][rb][rc][0] == -1) {
        dp[ra][rb][rc][0] = dp[ta][tb][tc][0] + 1;
        dp[ra][rb][rc][1] = a;
        dp[ra][rb][rc][2] = b;
        dp[ra][rb][rc][3] = c;
        q[rq][0] = ra;
        q[rq][1] = rb;
        q[rq][2] = rc;
        rq++;
      }
    }
}
int main() {
  ios_base::sync_with_stdio(0);
  scanf("%d", &n);
  scanf("%d%d%d", &a, &b, &c);
  a--;
  b--;
  c--;
  memset(mp, -1, sizeof(mp));
  for (int i = 0; i < n; i++) {
    char str[maxn];
    scanf("%s", str);
    for (int j = 0; j < n; j++)
      if (j != i) mp[i][j] = str[j] - 'a';
  }
  memset(dp, -1, sizeof(dp));
  relax(a, b, c);
  dp[a][b][c][0] = 0;
  for (int i = 0; i < 3; i++) dp[a][b][c][i + 1] = -1;
  q[rq][0] = a;
  q[rq][1] = b;
  q[rq][2] = c;
  rq++;
  for (; lq != rq; lq++) {
    int ra = q[lq][0], rb = q[lq][1], rc = q[lq][2];
    justdoit(ra, rb, rc);
    justdoit(rb, ra, rc);
    justdoit(rc, rb, ra);
  }
  if (dp[0][1][2][0] > 100000000)
    printf("-1\n");
  else {
    printf("%d\n", dp[0][1][2][0]);
    int a = 0, b = 1, c = 2;
    int nxt, bef;
    for (int i = dp[0][1][2][0] - 1; i >= 0; --i) {
      int ra = dp[a][b][c][1], rb = dp[a][b][c][2], rc = dp[a][b][c][3];
      if (canfind(a, ra, rb, rc)) {
        if (canfind(b, ra, rb, rc))
          nxt = c;
        else
          nxt = b;
      } else
        nxt = a;
      if (canfind(ra, a, b, c)) {
        if (canfind(rb, a, b, c))
          bef = rc;
        else
          bef = rb;
      } else
        bef = ra;
      ans[i][0] = bef + 1;
      ans[i][1] = nxt + 1;
      a = ra;
      b = rb;
      c = rc;
      relax(a, b, c);
    }
    for (int i = 0; i < dp[0][1][2][0]; i++)
      printf("%d %d\n", ans[i][0], ans[i][1]);
  }
  return 0;
}