using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
static string InputPattern = "InputX";
static List<string> GetInputList()
{
var WillReturn = new List<string>();
if (InputPattern == "Input1") {
WillReturn.Add("4 5");
WillReturn.Add("1 2 3 4 5");
WillReturn.Add("6 7 8 9 10");
WillReturn.Add("11 12 13 14 15");
WillReturn.Add("16 17 18 19 20");
WillReturn.Add("2 3");
WillReturn.Add("6 8 9");
WillReturn.Add("16 18 19");
//Yes
}
else if (InputPattern == "Input2") {
WillReturn.Add("3 3");
WillReturn.Add("1 1 1");
WillReturn.Add("1 1 1");
WillReturn.Add("1 1 1");
WillReturn.Add("1 1");
WillReturn.Add("2");
//No
}
else {
string wkStr;
while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
}
return WillReturn;
}
static int UB_X;
static int UB_Y;
static int[,] mBanArr1;
static int[,] mBanArr2;
static void Main()
{
List<string> InputList = GetInputList();
int[] wkArr = InputList[0].Split(' ').Select(pX => int.Parse(pX)).ToArray();
int H = wkArr[0];
mBanArr1 = CreateBanArr(InputList.Skip(1).Take(H));
UB_X = mBanArr1.GetUpperBound(0);
UB_Y = mBanArr1.GetUpperBound(1);
mBanArr2 = CreateBanArr(InputList.Skip(1 + H + 1));
if (ExecBFS()) {
Console.WriteLine("Yes");
}
else {
Console.WriteLine("No");
}
}
struct JyoutaiDef
{
internal int[,] BanArr;
internal int CurrX;
internal bool DeleteX;
internal int CurrY;
}
static bool ExecBFS()
{
string GoalHash = GetHash(mBanArr2);
if (GoalHash == GetHash(mBanArr1)) {
return true;
}
var Stk = new Stack<JyoutaiDef>();
JyoutaiDef WillPush;
WillPush.BanArr = mBanArr1;
WillPush.CurrX = UB_X;
WillPush.DeleteX = true;
WillPush.CurrY = UB_Y;
Stk.Push(WillPush);
while (Stk.Count > 0) {
JyoutaiDef Popped = Stk.Pop();
// クリア判定
if (Popped.BanArr.GetUpperBound(0) == mBanArr2.GetUpperBound(0)) {
if (Popped.BanArr.GetUpperBound(1) == mBanArr2.GetUpperBound(1)) {
if (GoalHash == GetHash(Popped.BanArr)) {
return true;
}
}
}
// 枝切り
if (Popped.BanArr.GetUpperBound(0) < mBanArr2.GetUpperBound(0)) {
continue;
}
if (Popped.BanArr.GetUpperBound(1) < mBanArr2.GetUpperBound(1)) {
continue;
}
if (Popped.DeleteX) {
for (int I = Popped.CurrX; 0 <= I; I--) {
WillPush.BanArr = CutColumn(I, Popped.BanArr);
WillPush.CurrX = I - 1;
WillPush.DeleteX = Popped.DeleteX;
WillPush.CurrY = Popped.CurrY;
Stk.Push(WillPush);
}
WillPush.BanArr = Popped.BanArr;
WillPush.CurrX = Popped.CurrX;
WillPush.DeleteX = false;
WillPush.CurrY = Popped.CurrY;
Stk.Push(WillPush);
}
if (Popped.DeleteX == false) {
for (int I = Popped.CurrY; 0 <= I; I--) {
WillPush.BanArr = CutLine(I, Popped.BanArr);
WillPush.CurrX = Popped.CurrX;
WillPush.DeleteX = Popped.DeleteX;
WillPush.CurrY = I - 1;
Stk.Push(WillPush);
}
}
}
return false;
}
////////////////////////////////////////////////////////////////
// 盤面のハッシュ値を求める
////////////////////////////////////////////////////////////////
static string GetHash(int[,] pBanArr)
{
var sb = new System.Text.StringBuilder();
sb.AppendFormat("{0},{1},", pBanArr.GetUpperBound(0), pBanArr.GetUpperBound(1));
for (int Y = 0; Y <= pBanArr.GetUpperBound(1); Y++) {
for (int X = 0; X <= pBanArr.GetUpperBound(0); X++) {
sb.AppendFormat("{0},", pBanArr[X, Y]);
}
}
return sb.ToString();
}
////////////////////////////////////////////////////////////////
// 盤面の指定列を消す
////////////////////////////////////////////////////////////////
static int[,] CutColumn(int pDeleteColumn, int[,] pBanArr)
{
int NewUB_X = pBanArr.GetUpperBound(0) - 1;
int NewUB_Y = pBanArr.GetUpperBound(1);
int[,] ReturnArr = new int[NewUB_X + 1, NewUB_Y + 1];
for (int Y = 0; Y <= pBanArr.GetUpperBound(1); Y++) {
for (int X = 0; X <= pBanArr.GetUpperBound(0); X++) {
if (X < pDeleteColumn) {
ReturnArr[X, Y] = pBanArr[X, Y];
}
else if (X == pDeleteColumn) {
continue;
}
else {
ReturnArr[X - 1, Y] = pBanArr[X, Y];
}
}
}
return ReturnArr;
}
////////////////////////////////////////////////////////////////
// 盤面の指定行を消す
////////////////////////////////////////////////////////////////
static int[,] CutLine(int pDeleteLine, int[,] pBanArr)
{
int NewUB_X = pBanArr.GetUpperBound(0);
int NewUB_Y = pBanArr.GetUpperBound(1) - 1;
int[,] ReturnArr = new int[NewUB_X + 1, NewUB_Y + 1];
for (int Y = 0; Y <= pBanArr.GetUpperBound(1); Y++) {
for (int X = 0; X <= pBanArr.GetUpperBound(0); X++) {
if (Y < pDeleteLine) {
ReturnArr[X, Y] = pBanArr[X, Y];
}
else if (Y == pDeleteLine) {
continue;
}
else {
ReturnArr[X, Y - 1] = pBanArr[X, Y];
}
}
}
return ReturnArr;
}
////////////////////////////////////////////////////////////////
// IEnumerable<string>をintの2次元配列に設定する
////////////////////////////////////////////////////////////////
static int[,] CreateBanArr(IEnumerable<string> pStrEnum)
{
var StrList = pStrEnum.ToList();
if (StrList.Count == 0) {
return new int[0, 0];
}
int[] IntArr = { };
Action<string> SplitAct = pStr =>
IntArr = pStr.Split(' ').Select(pX => int.Parse(pX)).ToArray();
SplitAct(StrList[0]);
int UB_X = IntArr.GetUpperBound(0);
int UB_Y = StrList.Count - 1;
int[,] WillReturn = new int[UB_X + 1, UB_Y + 1];
for (int Y = 0; Y <= UB_Y; Y++) {
SplitAct(StrList[Y]);
for (int X = 0; X <= UB_X; X++) {
WillReturn[X, Y] = IntArr[X];
}
}
return WillReturn;
}
////////////////////////////////////////////////////////////////
// 2次元配列(int型)のデバッグ出力
////////////////////////////////////////////////////////////////
static void PrintBan(int[,] pBanArr)
{
for (int Y = 0; Y <= pBanArr.GetUpperBound(1); Y++) {
for (int X = 0; X <= pBanArr.GetUpperBound(0); X++) {
Console.Write(pBanArr[X, Y]);
}
Console.WriteLine();
}
}
}