Imagine a city with n horizontal streets crossing m vertical streets, forming an (n - 1) × (m - 1) grid. In order to increase the traffic flow, mayor of the city has decided to make each street one way. This means in each horizontal street, the traffic moves only from west to east or only from east to west. Also, traffic moves only from north to south or only from south to north in each vertical street. It is possible to enter a horizontal street from a vertical street, or vice versa, at their intersection.

 [Image] 

The mayor has received some street direction patterns. Your task is to check whether it is possible to reach any junction from any other junction in the proposed street direction pattern.


-----Input-----

The first line of input contains two integers n and m, (2 ≤ n, m ≤ 20), denoting the number of horizontal streets and the number of vertical streets.

The second line contains a string of length n, made of characters '<' and '>', denoting direction of each horizontal street. If the i-th character is equal to '<', the street is directed from east to west otherwise, the street is directed from west to east. Streets are listed in order from north to south.

The third line contains a string of length m, made of characters '^' and 'v', denoting direction of each vertical street. If the i-th character is equal to '^', the street is directed from south to north, otherwise the street is directed from north to south. Streets are listed in order from west to east.


-----Output-----

If the given pattern meets the mayor's criteria, print a single line containing "YES", otherwise print a single line containing "NO".


-----Examples-----
Input
3 3
><>
v^v

Output
NO

Input
4 6
<><>
v^v^v^

Output
YES



-----Note-----

The figure above shows street directions in the second sample test case.

Difficulty: interview

Starter code:

Solutions:
a, b = list(map(int, input().split(' ')))
hor = input()
ver = input()
if (hor[0], ver[0]) == ('>', 'v') or (hor[0], ver[-1]) == ('<', 'v'):
    print("NO")
elif (hor[-1], ver[0]) == ('>', '^') or (hor[-1], ver[-1]) == ('<', '^'):
    print("NO")
else:
    print("YES")


h, w = map(int, input().split())
go = [[[] for x in range(w)] for y in range(h)]
s = input()
for i in range(h):
    if s[i] == '>':
        for j in range(w - 1):
            go[i][j].append((i, j + 1))
    else:
        for j in range(1, w):
            go[i][j].append((i, j - 1))
s = input()
for i in range(w):
    if s[i] == '^':
        for j in range(1, h):
            go[j][i].append((j - 1, i))
    else:
        for j in range(h - 1):
            go[j][i].append((j + 1, i))

good = True
for i in range(h):
    for j in range(w):
        u = [[False for x in range(w)] for y in range(h)]
        u[i][j] = True
        q = [(i, j)]
        hd = 0
        while hd < len(q):
            for g in go[q[hd][0]][q[hd][1]]:
                if not u[g[0]][g[1]]:
                    u[g[0]][g[1]] = True
                    q.append(g)
            hd += 1
        if len(q) != h * w:
            good = False


print("YES" if good else "NO")

3

import sys

"""
4 6
<><>
v^v^v^
"""

def num_of_accessible(g, node):
    q = [node]
    seen = set([node])
    while len(q) > 0:
        v = q.pop()
        for u in g[v]:
            if u in seen:
                continue
            seen.add(u)
            q.append(u)
    return len(seen)

def __starting_point():
    n, m = list(map(int, sys.stdin.readline().split()))
    horiz = sys.stdin.readline().strip()
    vert = sys.stdin.readline().strip()
    
    # Graph
    g = {(i, j): [] for i in range(n) for j in range(m)}
    for i, h in enumerate(horiz):
        if h == '<':
            for j in range(m-1):
                g[(i, j+1)].append((i, j))
        else:
            for j in range(m-1):
                g[(i, j)].append((i, j+1))
    for j, v in enumerate(vert):
        if v == 'v':
            for i in range(n-1):
                g[(i, j)].append((i+1, j))
        else:
            for i in range(n-1):
                g[(i+1, j)].append((i, j))
        
    conn = True
    for node in g:
        if num_of_accessible(g, node) < n*m:
            conn = False
            break
    
    print('YES' if conn else 'NO')

__starting_point()

n,m=map(int,input().split())
s=input()
t=input()
if (s[0]=='>' and t[0]=='v') or (s[0]=='<' and t[0]=='^') or (s[0]=='>' and t[m-1]=='^') or (s[0]=='<' and t[m-1]=='v') or (s[n-1]=='>' and t[0]=='^') or (s[n-1]=='<' and t[0]=='v'):
   print("NO")
else:print("YES")

# CF BAYAN WARMUP
# B

l = input()
h = input()
v = input()

if h[0] == "<" and v[0] == "^":
    print("NO")
elif h[0] == ">" and v[-1] == "^":
    print("NO")
elif h[-1] == "<" and v[0] == "v":
    print("NO")
elif h[-1] == ">" and v[-1] == "v":
    print("NO")
else:
    print("YES")


n, m = list(map(int, input().split()))
a = input()
b = input()
if (a[0] == '>' and b[0] == 'v') or (a[0] == '<' and b[-1] == 'v') or (a[-1] == '>' and b[0] == '^') or (a[-1] == '<' and b[-1] == '^'):
    print('NO')
else:
    print('YES')


3

n, m = input().split()
n = int(n)
m = int(m)

if n == m == 1:
    print("YES")
else:
    x, y = input(), input()
    x = (1 if x[0] == '<' else 0, 1 if x[-1] == '>' else 0)
    y = (1 if y[0] == 'v' else 0, 1 if y[-1] == '^' else 0)
    if (sum(x) + sum(y)) % 4 == 0:
        print("YES")
    else:
        print("NO")


from collections import deque

dic = {'>': (0, 1), '<': (0, -1), 'v': (1, 0), '^': (-1, 0)}
[n, m], hor, vert = list(map(int, input().split())), input().strip(), input().strip()
for _x in range(n):
    for _y in range(m):
        q, d = deque([(_x, _y)]), [[0] * m for x in range(n)]
        d[_x][_y] = 1
        while q:
            x, y = q.popleft()
            for direction in '><v^':
                dx, dy = dic[direction]
                if -1 < x + dx < n and -1 < y + dy < m and (vert[y] == direction if dx else hor[x] == direction) and not d[x + dx][y + dy]:
                    d[x + dx][y + dy] = 1
                    q.append((x + dx, y + dy))
        if sum(sum(d, [])) != n * m:
            print('NO')
            break
    else:
        continue
    break
else:
    print('YES')


from collections import deque

n, m = list(map(int, input().split()))

s1 = input()
s2 = input()

ok = True

for i in range(n):
    for j in range(m):
        c = [[False for _ in range(m)] for __ in range(n)]
        c[i][j] = True

        q = deque()
        q.append((i, j))

        while len(q) > 0:
            x, y = q.popleft()

            if s1[x] == '>' and y + 1 < m and not c[x][y + 1]:
                c[x][y + 1] = True
                q.append((x, y + 1))
            elif s1[x] == '<' and y - 1 >= 0 and not c[x][y - 1]:
                c[x][y - 1] = True
                q.append((x, y - 1))

            if s2[y] == '^' and x - 1 >= 0 and not c[x - 1][y]:
                c[x - 1][y] = True
                q.append((x - 1, y))
            elif s2[y] == 'v' and x + 1 < n and not c[x + 1][y]:
                c[x + 1][y] = True
                q.append((x + 1, y))

        for a in range(n):
            for b in range(m):
                if not c[a][b]:
                    ok = False

if ok:
    print("YES")
else:
    print("NO")


n,m=list(map(int,input().split()))

a=input()
b=input()

if a[0]=='>' and a[n-1]=='<' and b[0]=='^' and b[m-1]=='v':
    print ("YES")
elif  a[n-1]=='>' and a[0]=='<' and b[m-1]=='^' and b[0]=='v':
    print("YES")
else:print("NO")


n, m = map(int, input().split())
a = input()
b = input()
f = True
def dfs(x, y):
    tmp = 1
    used[x + y * 42] = 1
    if a[x] == '>' and y + 1 < m:
        if used[x + (y + 1) * 42] == 0:
            tmp += dfs(x, y + 1)
    if a[x] == '<' and y - 1 >= 0:
        if used[x + (y - 1) * 42] == 0:
            tmp += dfs(x, y - 1)
    if b[y] == 'v' and x + 1 < n:
        if used[x + 1 + (y) * 42] == 0:
            tmp += dfs(x + 1, y)
    if b[y] == '^' and x - 1 >= 0:
        if used[x - 1 + (y) * 42] == 0:
            tmp += dfs(x - 1, y)
    return(tmp)
    
for i in range(n):
    for j in range(m):
        used = [0] * 1000
        if dfs(i, j) != n * m:
            f = False
if f:
    print('YES')
else:
    print('NO')

'''
Created on Oct 5, 2014

@author: Ismael
'''
from _collections import defaultdict

def DFexplo(dictAdj,start):
    explored = {start}
    lifo = [start]
    while(len(lifo)>0):
        node = lifo.pop()
        for child in dictAdj[node]:
            if(child not in explored):
                explored.add(child)
                lifo.append(child)
    return explored

def solve(dictAdj):
    #print(dictAdj)
    for i in range(len(H)):
        for j in range(len(V)):
            nodesReachable = DFexplo(dictAdj,(i,j))
            if(len(nodesReachable) < n*m-1):
                return False
    return True

def isNode(i,j):
    return 0 <= i < n and 0 <= j < m

def buildGraph(H,V):
    dictAdj = defaultdict(list)
    for i in range(len(H)):
        for j in range(len(V)):
            if(isNode(i,j-1) and H[i]=='<'):
                dictAdj[(i,j)].append((i,j-1))
            if(isNode(i,j+1) and H[i]=='>'):
                dictAdj[(i,j)].append((i,j+1))
            if(isNode(i-1,j) and V[j]=='^'):
                dictAdj[(i,j)].append((i-1,j))
            if(isNode(i+1,j) and V[j]=='v'):
                dictAdj[(i,j)].append((i+1,j))
    return dictAdj

n,m = map(int,input().split())
H = input()
V = input()
dictAdj = buildGraph(H,V)
if(solve(dictAdj)):
    print("YES")
else:
    print("NO")

data = input().split()
n = int(data[0])
m = int(data[1])
h = input().rstrip()
v = input().rstrip()
f = (h[0] == '<' and v[0] == 'v' and v[-1] == '^' and h[-1] == '>') or (h[0] == '>' and v[0] == '^' and v[-1] == 'v' and h[-1] == '<')
print('YES' if f else 'NO')

def dfs(x, y):
    if not graph[2][x + graph[0][x][y]][y]:
        graph[2][x + graph[0][x][y]][y] = True
        dfs(x + graph[0][x][y], y)
    if not graph[2][x][y + graph[1][x][y]]:
        graph[2][x][y + graph[1][x][y]] = True
        dfs(x, y + graph[1][x][y])
            
n, m = list(map(int, input().split()))
c = chr(0)
flag1 = True
graph = [[[0] * (n + 1) for i in range(m + 1)], [[0] * (n + 1) for i in range(m + 1)], [[False] * (n + 1) for i in range(m + 1)]]

s = input()
for i in range(n):
    c = s[i]
    if c == '<':
        for j in range(1, m):
            graph[0][j][i] = -1
    else:
        for j in range(m - 1):
            graph[0][j][i] = 1
                    
s = input()
for i in range(m):
    c = s[i]
    if c == '^':
        for j in range(1, n):
            graph[1][i][j] = -1
    else:
        for j in range(n - 1):
            graph[1][i][j] = 1
                    
for i in range(n):
    for j in range(m):
        flag = False
        if flag1:
            for k in range(n):
                for l in range(m):
                    graph[2][l][k] = False
            graph[2][j][i] = True
            dfs(j, i)
            for k in range(n):
                for l in range(m):
                    if graph[2][l][k] == False:
                        flag = True
             #           print(i, j, k, l)
            if flag:
                print('NO')
                flag1 = not flag

if flag1:
    print('YES')
    
#print()
#for i in range(n):
    #for j in range(m):
        #print(graph[0][j][i], end = ' ')
    #print()
#print()
#for i in range(n):
    #for j in range(m):
        #print(graph[1][j][i], end = ' ')
    #print()


#input
n,m=map(int,input().split())
nstr=str(input())
mstr=str(input())

#variables

#main
if nstr[0]=='>' and mstr[0]=='v':
	print('NO')
	quit()
if nstr[0]=='<' and mstr[-1]=='v':
	print('NO')
	quit()
if nstr[-1]=='>' and mstr[0]=='^':
	print('NO')
	quit()
if nstr[-1]=='<' and mstr[-1]=='^':
	print('NO')
	quit()
print('YES')

h, w = map(int, input().split())
go = [[[] for x in range(w)] for y in range(h)]
s = input()
for i in range(h):
    if s[i] == '>':
        for j in range(w - 1):
            go[i][j].append((i, j + 1))
    else:
        for j in range(1, w):
            go[i][j].append((i, j - 1))
s = input()
for i in range(w):
    if s[i] == '^':
        for j in range(1, h):
            go[j][i].append((j - 1, i))
    else:
        for j in range(h - 1):
            go[j][i].append((j + 1, i))

good = True
for i in range(h):
    for j in range(w):
        u = [[False for x in range(w)] for y in range(h)]
        u[i][j] = True
        q = [(i, j)]
        hd = 0
        while hd < len(q):
            for g in go[q[hd][0]][q[hd][1]]:
                if not u[g[0]][g[1]]:
                    u[g[0]][g[1]] = True
                    q.append(g)
            hd += 1
        if len(q) != h * w:
            good = False


print("YES" if good else "NO")

h, w = map(int, input().split())
go = [[[] for x in range(w)] for y in range(h)]
s = input()
t = input()
c1 = s[0] == '<' and s[h - 1] == '>' and t[0] == 'v' and t[w - 1] == '^'
c2 = s[0] == '>' and s[h - 1] == '<' and t[0] == '^' and t[w - 1] == 'v'
print("YES" if c1 or c2 else "NO")

n , m = map(int,input().split())
h = input()
v = input()
if (h[0] == '>' and v[0] == 'v') or (h[-1] == '<' and v[-1] == '^') or (h[0] == '<' and v[-1] == 'v') or (h[-1] == '>' and v[0] == '^'):
    print('NO')
else:
    print('YES')

'''
Created on Oct 6, 2014

@author: nod
'''
n, m = map(int, input().split())
horizontal = str(input())
visited = []
h = []
vertical = str(input())
v = []
for char in horizontal:
    if char == ">":
        h.append(int(1))
    else:
        h.append(int(-1))
for char in vertical:
    if char == "v":
        v.append(int(1))
    else:
        v.append(int(-1))
def travel(ni, mi):
    leftright = h[ni]
    updown = v[mi]
    visited.append([ni,mi])
    newn = ni + updown
    newm = mi + leftright
    if newn >= 0 and newn < n and [newn,mi] not in visited:
#        print(newn,mi)
        travel(newn,mi)
    if newm >= 0 and newm < m and [ni,newm] not in visited:
#        print(ni,newm)
        travel(ni,newm)
    return visited

def solve():
    lst = [[0,0],[0,m-1],[n-1,0],[n-1,m-1]]
    visited = []
    for l in lst:
        visited.clear()
        vis = travel(l[0],l[1])
        if len(vis) != m*n:
            print("NO")
            return
        visited.clear()
        vis.clear()
    print("YES")
solve()

input()
horiz = input()
vert = input()

m = horiz[0]+horiz[-1]+vert[0]+vert[-1]

print("YES" if m in ("><^v", "<>v^") else "NO")

n, m = map(int, input().split())
h, v = input(), input()
if h[0] == '<' and v[0] == '^':
    print('NO')
elif h[0] == '>' and v[0] == 'v':
    print('NO')
elif h[0] == h[-1] or v[0] == v[-1]:
    print('NO')
else:
    print('YES')

# 475B

from sys import stdin

__author__ = 'artyom'

stdin.readline()
p = stdin.readline().strip()
q = stdin.readline().strip()
print('YES' if (p[0] == '>' and p[-1] == '<' and q[0] == '^' and q[-1] == 'v') or
               (p[0] == '<' and p[-1] == '>' and q[0] == 'v' and q[-1] == '^') else 'NO')

n, m = [int(x) for x in input().split()]
a = input()
b = input()
if a[0] == '<' and b[0] == 'v' and a[-1] == '>' and b[-1] == '^':
	print('YES')
elif a[0] == '>' and b[-1] == 'v' and a[-1] == '<' and b[0] == '^':
	print('YES')
else:
	print('NO')


def main():
    n, m = map(int, input().split())
    nm = n * m
    neigh = [[] for _ in range(nm)]
    for y, c in enumerate(input()):
        for x in range(y * m + 1, y * m + m):
            if c == '<':
                neigh[x].append(x - 1)
            else:
                neigh[x - 1].append(x)
    for x, c in enumerate(input()):
        for y in range(m + x, nm, m):
            if c == '^':
                neigh[y].append(y - m)
            else:
                neigh[y - m].append(y)

    def getdsu(t):
        if dsu[t] != t:
            dsu[t] = getdsu(dsu[t])
        return dsu[t]

    def setdsu(u, v):
        dsu[u] = getdsu(dsu[v])

    def dfs(yx):
        l[yx] = False
        for yx1 in neigh[yx]:
            if l[yx1]:
                setdsu(yx1, yx)
                dfs(yx1)

    for i in range(nm):
        l = [True] * nm
        dsu = list(range(nm))
        for j in range(i, i + nm):
            j %= nm
            if l[j]:
                dfs(j)
        if any(getdsu(_) != i for _ in range(nm)):
            print('NO')
            return
    print('YES')


def __starting_point():
    main()
__starting_point()

def main():
    n, m = map(int, input().split())
    nm = n * m
    neigh = [[] for _ in range(nm)]
    for y, c in enumerate(input()):
        for x in range(y * m + 1, y * m + m):
            if c == '<':
                neigh[x].append(x - 1)
            else:
                neigh[x - 1].append(x)
    for x, c in enumerate(input()):
        for y in range(m + x, nm, m):
            if c == '^':
                neigh[y].append(y - m)
            else:
                neigh[y - m].append(y)

    def dfs(yx):
        l[yx] = False
        for yx1 in neigh[yx]:
            if l[yx1]:
                dfs(yx1)

    for i in range(nm):
        l = [True] * nm
        dfs(i)
        if any(l):
            print('NO')
            return
    print('YES')


def __starting_point():
    main()
__starting_point()