The stardate is 1977 and the science and art of detecting Death Stars is in its infancy. Princess Heidi has received information about the stars in the nearby solar system from the Rebel spies and now, to help her identify the exact location of the Death Star, she needs to know whether this information is correct. 

Two rebel spies have provided her with the maps of the solar system. Each map is an N × N grid, where each cell is either occupied by a star or empty. To see whether the information is correct, Heidi needs to know whether the two maps are of the same solar system, or if possibly one of the spies is actually an Empire double agent, feeding her false information.

Unfortunately, spies may have accidentally rotated a map by 90, 180, or 270 degrees, or flipped it along the vertical or the horizontal axis, before delivering it to Heidi. If Heidi can rotate or flip the maps so that two of them become identical, then those maps are of the same solar system. Otherwise, there are traitors in the Rebel ranks! Help Heidi find out.


-----Input-----

The first line of the input contains one number N (1 ≤ N ≤ 10) – the dimension of each map. Next N lines each contain N characters, depicting the first map: 'X' indicates a star, while 'O' indicates an empty quadrant of space. Next N lines each contain N characters, depicting the second map in the same format.


-----Output-----

The only line of output should contain the word Yes if the maps are identical, or No if it is impossible to match them by performing rotations and translations.


-----Examples-----
Input
4
XOOO
XXOO
OOOO
XXXX
XOOO
XOOO
XOXO
XOXX

Output
Yes

Input
2
XX
OO
XO
OX

Output
No



-----Note-----

In the first test, you can match the first map to the second map by first flipping the first map along the vertical axis, and then by rotating it 90 degrees clockwise.

Difficulty: interview

Starter code:

Solutions:
3

import copy


def rotate90(n, f):
    return [[f[n - j - 1][i] for j in range(n)] for i in range(n)]

def fliphor(n, f):
    return [[f[i][n - j - 1] for j in range(n)] for i in range(n)]

def flipver(n, f):
    return [[f[n - i - 1][j] for j in range(n)] for i in range(n)]

def eq(n, f, g):
    for i in range(n):
        for j in range(n):
            if f[i][j] != g[i][j]:
                return False
    return True


n = int(input())
f = [list(input()) for i in range(n)]
g = [list(input()) for i in range(n)]

for doflipv in range(2):
    for dofliph in range(2):
        for nrot in range(4):
            h = copy.deepcopy(f)
            if dofliph == 1:
                h = fliphor(n, h)
            if doflipv == 1:
                h = flipver(n, h)
            for i in range(nrot):
                h = rotate90(n, h)
            if eq(n, h, g):
                print("Yes")
                return

print("No")

N = int(input())
s1 = [list(input()) for i in range(N)]
s2 = [list(input()) for i in range(N)]

def rotate(s):
    ret = [[None for i in range(N)] for j in range(N)]
    for i in range(N):
        for j in range(N):
            ret[i][j] = s[j][N-1-i]
    return ret

def v_mirror(s):
    return list(reversed(s))

def h_mirror(s):
    return [list(reversed(row)) for row in s]

def solve():
    nonlocal s1
    for i in range(4):
        if s1 == s2: return True
        if v_mirror(s1) == s2: return True
        if h_mirror(s1) == s2: return True
        if v_mirror(h_mirror(s1)) == s2: return True
        s1 = rotate(s1)
    return False

print('Yes' if solve() else 'No')


n=int(input())
ns=[]
for i in range(n):
    s=input()
    ns.append(s)
ns2=[]
for i in range(n):
    s=input()
    ns2.append(s)


def rotate(i,j):
    return j,n-1-i
def flip(i,j):
    return j,i

def main():
    same=True
    for i in range(n): # 0
        for j in range(n):
            if ns[i][j]!=ns2[i][j]:
                same=False
                break
        if same==False:
            break
    if same:
        return True

    same=True
    for i in range(n):  # 1
        for j in range(n):
            a, b = rotate(i, j)
            if ns[i][j] != ns2[a][b]:
                same = False
                break
        if same == False:
            break
    if same:
        return True

    same=True
    for i in range(n):  # 2
        for j in range(n):
            a, b = rotate(i, j)
            a, b = rotate(a, b)
            if ns[i][j] != ns2[a][b]:
                same = False
                break
        if same == False:
            break
    if same:
        return True

    same=True
    for i in range(n):
        for j in range(n):  # 3
            a, b = rotate(i, j)
            a, b = rotate(a, b)
            a, b = rotate(a, b)
            if ns[i][j] != ns2[a][b]:
                same = False
                break
        if same == False:
            break
    if same:
        return True

    same=True
    for i in range(n): # 0
        for j in range(n):
            a,b=flip(i,j)
            if ns[a][b]!=ns2[i][j]:
                same=False
                break
        if same==False:
            break
    if same:
        return True

    same=True
    for i in range(n):  # 1
        for j in range(n):
            a, b = rotate(i, j)
            a, b = flip(a, b)
            if ns[i][j] != ns2[a][b]:
                same = False
                break
        if same == False:
            break
    if same:
        return True

    same=True
    for i in range(n):  # 2
        for j in range(n):
            a, b = rotate(i, j)
            a, b = rotate(a, b)
            a, b = flip(a, b)
            if ns[i][j] != ns2[a][b]:
                same = False
                break
        if same == False:
            break
    if same:
        return True

    same=True
    for i in range(n):
        for j in range(n):  # 3
            a, b = rotate(i, j)
            a, b = rotate(a, b)
            a, b = rotate(a, b)
            a, b = flip(a, b)
            if ns[i][j] != ns2[a][b]:
                same = False
                break
        if same == False:
            break
    if same:
        return True
    else:
        return False

if main():
    print('Yes')
else:
    print('No')





def solve(board):
  n=len(board)
  ans=0
  for i in range(n):
    for j in range(n):
      if board[i][j] is 'X':
        ans+=2**(i*n+j)
  return ans 

def reverse_array(arr):
  for i in range(len(arr)):
    arr[i].reverse()

def rotate(matrix, degree):
    if degree == 0:
        return matrix
    elif degree > 0:
        return rotate(zip(*matrix[::-1]), degree-90)
    else:
        return rotate(zip(*matrix)[::-1], degree+90)

def make_list(board):
    board=list(board)
    arr=[]
    for i in range(len(list(board))):
        arr.append(list(board[i]))
    return arr

def add_rotations(board,st):
  for i in range(4):
    st.add(solve(board))
    reverse_array(board)
    st.add(solve(board))
    reverse_array(board)
    board=make_list(rotate(board, 90))
    

n=int(input())
arr1=[]
arr2=[]
for _ in range(n):
    arr1.append(list(input().strip()))
for _ in range(n):
    arr2.append(list(input().strip()))
s=set()
s.add(solve(arr1))
add_rotations(arr1,s)
l1=len(s)
#print(s,arr1,arr2)
s.add(solve(arr2))
add_rotations(arr2,s)
#print(s)
l2=len(s)
if l1==l2:
    print("Yes")
else:
    print("No")

N = int(input())
first = []
second = []
for i in range(N):
    first.append([s for s in input()])
for i in range(N):
    second.append([s for s in input()])

def rotate_90(matrix):
    return list(zip(*matrix[::-1]))

def flip(matrix):
    return matrix[::-1]

def compare_matrices(first, second):
    for i in range(N):
        for j in range(N):
            if first[i][j] != second[i][j]:
                return False
    return True

def wrap(first, second):
    if compare_matrices(first, second) == True:
        return 'Yes'
    hold_first = first[::]
    for _ in range(3):
        first = rotate_90(first)
        if compare_matrices(first, second) == True:
            return 'Yes'
    first = hold_first
    first = flip(first)
    if compare_matrices(first, second) == True:
        return 'Yes'
    for _ in range(3):
        first = rotate_90(first)
        if compare_matrices(first, second) == True:
            return 'Yes'
    return 'No'

print(wrap(first, second))

from itertools import chain, combinations, permutations

def powerset(iterable):
    """
    powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)
    """
    xs = list(iterable)
    # note we return an iterator rather than a list
    return chain.from_iterable(combinations(xs,n) for n in range(len(xs)+1))

n = int(input())
cl1 = []
cl2 = []
for i in range(n):
  s = input()
  a = []
  for j in range(n):
    a.append(s[j])
  cl1.append(a)

for i in range(n):
  s = input()
  a = []
  for j in range(n):
    a.append(s[j])
  cl2.append(a)

def copy(m):
  res = []
  for i in range(n):
    a = []
    for j in range(n):
      a.append(m[i][j])
    res.append(a)
  return res

def pow(m):
  res = []
  for i in range(n):
    a = []
    for j in range(n):
      a.append(m[n-1-j][i])
    res.append(a)
  return res
  
def vert(m):
  res = []
  for i in range(n):
    res.append(m[i][::-1])
  return res
  
def gor(m):
  res = []
  for i in range(n):
    a = []
    for j in range(n):
      a.append(m[i][n-1-j])
    res.append(a)
  return res

comblist = [[1], []]
cm = [pow, pow, pow, vert, gor]
cm = list(powerset(cm))
res = False
if cl1 == cl2:
  res = True
else:
  for x in cm:
    for y in permutations(x):
      t = copy(cl1)
      for z in y:
        t = z(t)
      if t==cl2:
        res = True
      
if res:
  print('Yes')
else:
  print('No')

#codeforces.com/contest/958/problem/A1
def flipH(A,N):
    B=[[0 for i in range(N)] for j in range(N)]
    for i in range(N):
        for j in range(N):
            B[i][j]=A[i][N-j-1]
    return B

def flipV(A,N):
    B=[[0 for i in range(N)] for j in range(N)]
    for i in range(N):
        for j in range(N):
            B[i][j]=A[N-i-1][j]
    return B

def rotate90(A):
    ans = zip(*A[::-1])
    ans=list(map(list,ans))
    return ans

def check(A,B,N):
    for i in range(N):
        for j in range(N):
            if A[i][j]!=B[i][j]:
                return False
    return True

N=int(input())
A=[]
X=[]
for i in range(N):
    A.append(list(input()))
for i in range(N):
    X.append(list(input()))
B=flipH(A,N)
C=flipV(A,N)
flag=False
for i in range(4):
    if check(A,X,N) or check(B,X,N) or check(C,X,N):
        flag=True
        break
    else:
        A=rotate90(A)
        B=rotate90(B)
        C=rotate90(C)
if flag:
    print("Yes")
else:
    print("No")

import copy
n = int(input())
flg=0
mat1 = []
mat2 = []

mats = []
for i in range(0, n): mat1.append(tuple(input().strip()))
for i in range(0, n): mat2.append(tuple(input().strip()))
mats.append(mat2)
matu = copy.copy(mat2)
matv = copy.copy(mat2)
matv = list(zip(*matv))
mats.append(matv)

mattem = copy.copy(matu)
for i in range(0, 3):
	mattem = list(zip(*list(reversed(mattem))))
	mats.append(mattem)
mattem = copy.copy(matv)
for i in range(0, 3):
	mattem = list(zip(*list(reversed(mattem))))
	mats.append(mattem)

flg = 0
for cmat in mats:
	flg2 = 1
	for ri in range(0, n):
		if cmat[ri]!=mat1[ri]:
			flg2=0
			break
	if flg2==1:
		flg=1
		break
if flg==1: print("Yes")			
else: print("No")



def rotate(L):
    L1 = ['' for i in range(n)]
    for i in range(n):
        for j in range(n):
            L1[n - j - 1] += L[i][j]
    return L1

def flip_v(L):
    L1 = []
    for i in range(n):
        L1.append(L[i][::-1])
    return L1

def flip_h(L):
    L1 = []
    for i in range(n):
        L1.append(L[n - i - 1])
    return L1

n = int(input())
L = []
M = []
for i in range(n):
    L.append(input())
for i in range(n):
    M.append(input())
L1 = rotate(L)
L2 = rotate(L1)
L3 = rotate(L2)
L4 = flip_v(L)
L5 = flip_h(L)
L6 = rotate(L4)
L7 = rotate(L6)
L8 = rotate(L7)
L9 = rotate(L5)
L10 = rotate(L9)
L11 = rotate(L10)
if L == M or L1 == M or L2 == M or L3 == M or L4 == M or L5 == M or L6 == M or L7 == M or L8 == M or L9 == M or L10 == M or L11 == M:
    print('Yes')
else:
    print('No')

def check(x, y):
    return ''.join([''.join(s) for s in x]) == ''.join([''.join(s) for s in y])

n = int(input())
a = [list(input()) for i in range(n)]
b = [list(input()) for i in range(n)]
for i in range(4):
    for j in range(2):
        if check(a, b):
            print('Yes')
            return
        b = b[::-1]
    for j in range(2):
        if check(a, b):
            print('Yes')
            return
        b = [s[::-1] for s in b]
    c = [['' for t in range(n)] for u in range(n)]
    for t in range(n):
        for u in range(n):
            c[t][u] = b[u][n - t - 1]
    b = c[:]
    if check(a, b):
        print('Yes')
        return
print('No')


def check(x, y):
    return ''.join([''.join(s) for s in x]) == ''.join([''.join(s) for s in y])

n = int(input())
a = [list(input()) for i in range(n)]
b = [list(input()) for i in range(n)]
for i in range(4):
    for j in range(2):
        if check(a, b):
            print('Yes')
            return
        b = b[::-1]
    for j in range(2):
        if check(a, b):
            print('Yes')
            return
        b = [s[::-1] for s in b]
    c = [['' for t in range(n)] for u in range(n)]
    for t in range(n):
        for u in range(n):
            c[t][u] = b[u][n - t - 1]
    b = c[:]
    if check(a, b):
        print('Yes')
        return
print('No')

N = int(input())
map_1 = [list(input()) for i in range(N)]
map_2 = [list(input()) for i in range(N)]

maps = list()

maps.append([[map_2[i][j] for j in range(N)] for i in range(N)])
maps.append([[map_2[i][N - 1 - j] for j in range(N)] for i in range(N)])
maps.append([[map_2[N - 1 - i][j] for j in range(N)] for i in range(N)])
maps.append([[map_2[N - 1 - i][N - 1 - j] for j in range(N)] for i in range(N)])
maps.append([[map_2[j][i] for j in range(N)] for i in range(N)])
maps.append([[map_2[j][N - 1 - i] for j in range(N)] for i in range(N)])
maps.append([[map_2[N - 1 - j][i] for j in range(N)] for i in range(N)])
maps.append([[map_2[N - 1 - j][N - 1 - i] for j in range(N)] for i in range(N)])

print(('No', 'Yes')[any(map_1 == el for el in maps)])


def check(x, y):
    return ''.join([''.join(s) for s in x]) == ''.join([''.join(s) for s in y])

n = int(input())
a = [list(input()) for i in range(n)]
b = [list(input()) for i in range(n)]
for i in range(4):
    for j in range(2):
        if check(a, b):
            print('Yes')
            return
        b = b[::-1]
    for j in range(2):
        if check(a, b):
            print('Yes')
            return
        b = [s[::-1] for s in b]
    c = [['' for t in range(n)] for u in range(n)]
    for t in range(n):
        for u in range(n):
            c[t][u] = b[u][n - t - 1]
    b = c[:]
    if check(a, b):
        print('Yes')
        return
print('No')

#def pr():
#	print()
#	for i in range(n):
#		for j in range(n):
#			print(map1[i][j], end = "")
#		print()
#	print()
#-----------------------------------------------
def check():
	f = True
	for i in range(n):
		for j in range(n):
			if map1[i][j] != map2[i][j]:
				f = False
				break
	if f:
		return True
	
	f = True
	for i in range(n):
		for j in range(n):
			if map1[i][j] != map2[n - 1 - i][j]:
				f = False
				break
	if f:
		return True
	
	f = True
	for i in range(n):
		for j in range(n):
			if map1[i][j] != map2[i][n - 1 - j]:
				f = False
				break
	if f:
		return True
	

def rotate():
	wk1=[]
	for i in range(n):
		wk1.append([])
		for j in range(n):
			wk1[i].append(map1[i][j])
	
	for i in range(n):
		for j in range(n):
			map1[i][j] = wk1[j][n - 1 - i]


n = int(input())
map1 = []
for i in range(n):
	st = input()
	map1.append([])
	for j in st:
		map1[i].append(j)

map2 = []
for i in range(n):
	st = input()
	map2.append([])
	for j in st:
		map2[i].append(j)


f = False
for k in range(4):
	if check():
		f = True
		break
	rotate()

if f:
	print("Yes")
else:
	print("No")


def check(x, y):
    return ''.join([''.join(s) for s in x]) == ''.join([''.join(s) for s in y])

re = int(input())
a = [list(input()) for i in range(re)]
b = [list(input()) for i in range(re)]
for i in range(4):
    for j in range(2):
        if check(a, b):
            print('Yes')
            return
        b = b[::-1]
    for j in range(2):
        if check(a, b):
            print('Yes')
            return
        b = [s[::-1] for s in b]
    c = [['' for t in range(re)] for u in range(re)]
    for t in range(re):
        for u in range(re):
            c[t][u] = b[u][re - t - 1]
    b = c[:]
    if check(a, b):
        print('Yes')
        return
print('No')

n = int(input())
f = lambda: ''.join(input() for i in range(n))
a, b = f(), f()
g = lambda k: k // n + n * (n - 1 - k % n)
e = lambda k: k
h = lambda k: n * (n - 1 - k // n) + k % n
v = lambda k: n * (k // n) + n - 1 - k % n
for i in (e, v, h):
    for j in [e, g, lambda k: g(g(k)), lambda k: g(g(g(k)))]:
        if all(a[k] == b[i(j(k))] for k in range(n * n)): (print('Yes'));return
print('No')

# Function to rotate the matrix 
# 90 degree clockwise 
def rotate90Clockwise(A): 
    N = len(A[0]) 
    for i in range(N // 2): 
        for j in range(i, N - i - 1): 
            temp = A[i][j] 
            A[i][j] = A[N - 1 - j][i] 
            A[N - 1 - j][i] = A[N - 1 - i][N - 1 - j] 
            A[N - 1 - i][N - 1 - j] = A[j][N - 1 - i] 
            A[j][N - 1 - i] = temp 
def check(A,B):
    c1=0
    c2=0
    for i in range(N):
        for j in range(N):
            if(A[i][j]==B[N-1-i][j]):
                c1+=1
            if(A[i][j]==B[i][N-1-j]):
                c2+=1
    if(c1==N**2 or c2==N**2):return True
    else:return False
N=int(input())
A=[]
for i in range(N):
    a=input()
    aa=[]
    for j in range(N):
        aa.append(a[j])
    A.append(aa)
B=[]    
for j in range(N):
    b=input()
    bb=[]
    for j in range(N):
        bb.append(b[j])
    B.append(bb)
flag=False    
if(A==B):flag=True
if(check(A,B)):flag=True
rotate90Clockwise(A)
if(A==B):flag=True
if(check(A,B)):flag=True
rotate90Clockwise(A)
if(A==B):flag=True
if(check(A,B)):flag=True
rotate90Clockwise(A)
if(A==B):flag=True
if(check(A,B)):flag=True
if(flag):print("Yes")
else:print("No")