Problem: Ksenia has a chessboard of size n × m. Each cell of the chessboard contains one of the characters: "<", ">", "^", "v", "#". The cells that contain character "#" are blocked. We know that all chessboard cells that touch the border are blocked.

Ksenia is playing with two pawns on this chessboard. Initially, she puts the pawns on the chessboard. One cell of the chessboard can contain two pawns if and only if the cell is blocked. In other cases two pawns can not stand in one cell. The game begins when Ksenia put pawns on the board. In one move, Ksenia moves each pawn to a side adjacent cell in the direction of arrows painted on the cell on which the corresponding pawn sits (if the pawn sits on "#", it does not move). Assume that Ksenia moves pawns simultaneously (see the second test case). 

Of course, Ksenia plays for points. How can one calculate the points per game? Very simply! Let's count how many movements the first pawn made and how many movements the second pawn made, sum these two numbers — it will be the resulting score of the game. 

Ksenia wonders: what is the maximum number of points she can earn (for that, she should place the pawns optimally well early in the game). Help her and find that number. 

Input

The first line contains two integers, n and m (1 ≤ n, m ≤ 2000) — the sizes of the board. Each of the following n lines contains m characters – the board's description. Each character is one of the characters: "<", ">", "^", "v", "#".

It is guaranteed that the border cells of the table are blocked cells (with character "#").

Output

If Ksenia can get infinitely many points, print -1. Otherwise, print the maximum number of points she can get.

Examples

Input

1 1
#


Output

0


Input

3 4
####
#&gt;^{}#
####


Output

3

Input

3 4
####
#&gt;&lt;#
####


Output

-1

Input

7 5
#####
##v##
##v##
#####
##^{}##
##^{}##
#####


Output

4

Input

7 5
#####
##v##
##v##
##&lt;##
##^{}##
##^{}##
#####

Output

5

Solution (in JAVA):

Solution:

import java.util.*;
import java.io.*;

public class Main implements Runnable {

    int[][] table, maxPath, end;
    int row, col;
    boolean cycle;
    int[] di = new int[]{0, 1, 0, -1};
    int[] dj = new int[]{1, 0, -1, 0};

    public void solve() throws IOException {
        row = nextInt();
        col = nextInt();
        cycle = false;
        table = new int[row][col];
        maxPath = new int[row][col];
        end = new int[row][col];
        for (int i = 0; i < row; i++) {
            String tok = nextToken();
            for (int j = 0; j < col; j++) {
                maxPath[i][j] = -1;
                switch (tok.charAt(j)) {
                    case '>':
                        table[i][j] = 0;
                        break;
                    case '<':
                        table[i][j] = 2;
                        break;
                    case '^':
                        table[i][j] = 3;
                        break;
                    case 'v':
                        table[i][j] = 1;
                        break;
                    case '#':
                        table[i][j] = -1;
                        break;
                }
            }
        }
        int maximum = -1;
        for (int i = row - 1; i >= 0; i--) {
            for (int j = col - 1; j >= 0; j--) {
                if (maxPath[i][j] == -1) {
                    maximum = Math.max(maximum, dfs(i, j));
                }
                if (cycle) {
                    System.out.println(-1);
                    return;
                }
            }
        }
        //print(end);
        //print(maxPath);
        ArrayList<Integer> can = new ArrayList<Integer>();
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (maximum == maxPath[i][j]) {
                    can.add(hash(i, j));
                }
            }
        }
        //print(can);
        int ans = 2 * maximum - 1;
        for (int i = 1; i < can.size(); i++) {
            int[] cell1 = decode(can.get(i));
            int[] cell2 = decode(can.get(i - 1));
            if (end[cell1[0]][cell1[1]] != end[cell2[0]][cell2[1]]) {
                ans = 2 * maximum;
            }
        }
        System.out.println(Math.max(0, ans));
    }

    int dfs(int x, int y) {
        if (maxPath[x][y] == -2) {
            cycle = true;
            return Integer.MIN_VALUE;
        }
        if (maxPath[x][y] != -1) {
            return maxPath[x][y];
        }
        maxPath[x][y] = -2;
        if (table[x][y] == -1) {
            end[x][y] = hash(x, y);
            return maxPath[x][y] = 0;
        }
        int length = dfs(x + di[table[x][y]], y + dj[table[x][y]]);
        end[x][y] = end[x + di[table[x][y]]][y + dj[table[x][y]]];
        if (length == 0) {
            end[x][y] = hash(x, y);
        }
        return maxPath[x][y] = 1 + length;
    }

    int hash(int i, int j) {
        return i * col + j;
    }

    int[] decode(int x) {
        return new int[]{x / col, x % col};
    }

    String[] check(String in) {
        String[] ret = new String[2];
        Arrays.fill(ret, "");
        int i = 0;
        for (i = 0; i < in.length(); i++) {
            if (in.charAt(i) == '|') {
                break;
            }
            ret[0] += in.charAt(i);
        }
        i++;
        for (; i < in.length(); i++) {
            //if(in.charAt(i)=='|')break;
            ret[1] += in.charAt(i);
        }
        return ret;
    }

    int answer(int[] a, int[] b) {
        int n = a.length;
        b = b.clone();
        a = a.clone();
        for (int i = 0; i < n; i++) {
            if (b[i] >= 0) {
                merge(a, i, b[i]);
            }
        }
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            if (a[i] < 0) {
                cnt++;
            }
        }
        return cnt;
    }

    void merge(int[] arr, int a, int b) {
        a = get(arr, a);
        b = get(arr, b);
        if (a != b) {
            if (arr[a] > arr[b]) {
                int t = a;
                a = b;
                b = t;
            }
            arr[a] += arr[b];
            arr[b] = a;
        }
    }

    int get(int[] arr, int a) {
        if (arr[a] < 0) {
            return a;
        }
        return arr[a] = get(arr, arr[a]);
    }

    void shuffle(int[] a) {
        int N = a.length;
        for (int i = 0; i < N / 2; i++) {
            int j = (int) (Math.random() * N);
            int t = a[i];
            a[i] = a[j];
            a[j] = t;
        }
    }

    void print(Object... obj) {
        for (Object o : obj) {
            System.out.println(o);
        }
    }

    void print(int[] a) {
        System.out.println();
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i] + " ");
        }
    }

    void print(int[][] arr) {
        System.out.println();
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr[i].length; j++) {
                System.out.print(arr[i][j] + " ");
            }
            System.out.println();
        }
    }

    void print(boolean[][] arr) {
        System.out.println();
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr[i].length; j++) {
                System.out.print(arr[i][j] + " ");
            }
            System.out.println();
        }
    }

    boolean nextPermutation(int[] arr) {
        int f = -1;
        for (int i = arr.length - 2; i >= 0; i--) {
            if (arr[i + 1] > arr[i]) {
                f = i;
                break;
            }
        }
        if (f == -1) {
            return false;
        }
        int s = -1;
        for (int i = arr.length - 1; i >= 0; i--) {
            if (arr[i] > arr[f]) {
                s = i;
                break;
            }
        }
        int d = arr[f];
        arr[f] = arr[s];
        arr[s] = d;

        f++;
        int l = arr.length - 1;
        while (f < l) {
            d = arr[f];
            arr[f] = arr[l];
            arr[l] = d;
            f++;
            l--;
        }
        return true;
    }

    //-----------------------------------------------------------
    public static void main(String[] args) {
        new Main().run();
    }

    public void run() {
        try {
            in = new BufferedReader(new InputStreamReader(System.in));
            tok = null;
            solve();
            in.close();
        } catch (IOException e) {
            System.exit(0);
        }
    }

    public String nextToken() throws IOException {
        while (tok == null || !tok.hasMoreTokens()) {
            tok = new StringTokenizer(in.readLine());
        }
        return tok.nextToken();
    }

    public int nextInt() throws IOException {
        return Integer.parseInt(nextToken());
    }

    public long nextLong() throws IOException {
        return Long.parseLong(nextToken());
    }

    public double nextDouble() throws IOException {
        return Double.parseDouble(nextToken());
    }
    BufferedReader in;
    StringTokenizer tok;
}

class Student {

    int idx;
    int level;
    int cost;

    public Student(int i, int l) {
        idx = i;
        level = l;
    }

    public String toString() {
        return idx + " " + level + " " + cost;
    }
    public static final Comparator<Student> byLevel = new Comparator<Student>() {
        public int compare(Student a, Student b) {
            if (a.level != b.level) {
                return b.level - a.level;
            }
            if (a.cost != b.cost) {
                return a.cost - b.cost;
            }
            return a.idx - b.idx;
        }
    };
    public static final Comparator<Student> byCost = new Comparator<Student>() {
        public int compare(Student a, Student b) {
            if (a.cost != b.cost) {
                return a.cost - b.cost;
            }
            if (a.level != b.level) {
                return b.level - a.level;
            }
            return a.idx - b.idx;
        }
    };
}

class Bug implements Comparable<Bug> {

    int idx;
    int level;

    public Bug(int idx, int level) {
        this.idx = idx;
        this.level = level;
    }

    public int compareTo(Bug other) {
        if (level != other.level) {
            return other.level - level;
        }
        return idx - other.idx;
    }

    public String toString() {
        return idx + " " + level;
    }
}