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.HashMap;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.io.BufferedInputStream;
import java.io.IOException;
import java.util.Arrays;
import java.io.FilterInputStream;
import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.TreeSet;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 * @author Zyflair Griffane
 */
public class Main {
	public static void main(String[] args) {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		InputUtil in = new InputUtil(inputStream);
		PrintWriter out = new PrintWriter(outputStream);
		TaskD solver = new TaskD();
		solver.solve(1, in, out);
		out.close();
	}
}

class TaskD {
    public void solve(int testNumber, InputUtil in, PrintWriter out) {
        int rows = in.nextInt();
        int cols = in.nextInt();
        if (rows < 3 || cols < 3) {
            out.println("0");
            return;
        }

        int[] to = IntArrayUtil.calloc(rows * cols, -1);
        int[] inDegree = new int[rows * cols];

        char[][] board = in.nextCharRows(rows);
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                int u = r * cols + c;
                if (board[r][c] == '<') {
                    to[u] = u - 1;
                } else if (board[r][c] == '>') {
                    to[u] = u + 1;
                } else if (board[r][c] == 'v') {
                    to[u] = u + cols;
                } else if (board[r][c] == '^') {
                    to[u] = u - cols;
                }
                if (to[u] != -1) {
                    inDegree[to[u]]++;
                }
            }
        }

        int[] res = new int[rows * cols];
        int[] order = IntArrayUtil.calloc(rows * cols, -1);

        int back = 0;
        for (int i = 0; i < rows * cols; i++) {
            if (inDegree[i] == 0) {
                order[back++] = i;
            }
        }
        for (int i = 0; i < rows * cols; i++) {
            int u = order[i];
            if (u == -1) {
                order = null;
                break;
            }
            int v = to[u];
            if (v != -1) {
                inDegree[v]--;
                if (inDegree[v] == 0) {
                    order[back++] = v;
                }
            }
        }

        if (order == null) {
            out.println("-1");
            return;
        }
        for (int i = order.length - 1; i > -1; i--) {
            if (to[order[i]] != -1) {
                res[order[i]] = res[to[order[i]]] + 1;
            }
        }

        int sum = IntArrayUtil.max(res);

        boolean[] visited = new boolean[rows * cols];
        int full = 0;
        Start:
        for (int i = rows * cols - 1; i > -1; i--) {
            if (res[i] == sum) {
                int t = i;
                while (to[t] != -1) {
                    if (visited[t]) {
                        continue Start;
                    }
                    visited[t] = true;
                    t = to[t];
                }
                full++;
            }
        }
        if (sum == 0) full = 2;
        out.println((sum << 1) - (full < 2 ? 1 : 0));
    }
}

class InputUtil {

    JoltyScanner in;

    public InputUtil(InputStream istream) {
        in = new JoltyScanner(istream);
    }

    public String next() {
        return in.nextOrNull();
    }

    public int nextInt() {
        String s = next();
        if (s == null) {
            throw new NoSuchElementException("Attempted to read integer that is not there.");
        }
        return Integer.parseInt(s);
    }

    public char[][] nextCharRows(int rows) {
        char[][] arr = new char[rows][];
        for (int i = 0; i < rows; i++) {
            arr[i] = in.next().toCharArray();
        }
        return arr;
    }

}

class IntArrayUtil {

    public static int[] calloc(int length, int initValue) {
        int[] arr = new int[length];
        for (int i = length - 1; i > -1; i--) {
            arr[i] = initValue;
        }
        return arr;
    }

    public static int max(int[] arr) {
        if (arr.length == 0) {
            throw new RuntimeException("Passed in array has length of 0");
        }
        int max = arr[0];
        for (int a: arr) {
            if (a > max) {
                max = a;
            }
        }
        return max;
    }

}

class JoltyScanner {
    public static final int BUFFER_SIZE = 1 << 16;
	public static final char NULL_CHAR = (char) -1;

    BufferedInputStream in;
	StringBuilder str = new StringBuilder();
	byte[] buffer = new byte[BUFFER_SIZE];
	boolean EOF_FLAG = false;

    char c = NULL_CHAR;
	int bufferIdx = 0;
    int size = 0;

	public JoltyScanner(InputStream in) {
		this.in = new BufferedInputStream(in, BUFFER_SIZE);
	}

    public String next() {
		checkEOF();
		for (c = c == NULL_CHAR ? nextChar() : c; Character.isWhitespace(c); checkEOF()) {
			c = nextChar();
		}
		str.setLength(0);
		for (; !EOF_FLAG && !Character.isWhitespace(c); c = nextChar()) {
			str.append(c);
		}
		return str.toString();
	}

	public String nextOrNull() {
		try {
			return next();
		} catch (EndOfFileException e) {
			return null;
		}
	}

    public char nextChar() {
		if (EOF_FLAG) {
			return NULL_CHAR;
		}
		while (bufferIdx == size) {
			try {
				size = in.read(buffer);
				if (size == -1) {
					throw new Exception();
				}
			} catch (Exception e) {
				EOF_FLAG = true;
				return NULL_CHAR;
			}
			if (size == -1) {
				size = BUFFER_SIZE;
			}
			bufferIdx = 0;
		}
		return (char) buffer[bufferIdx++];
	}

    public void checkEOF() {
		if (EOF_FLAG) {
			throw new EndOfFileException();
		}
	}

	public class EndOfFileException extends RuntimeException {
	}
}