Problem 2: A Puzzle, *(K Narayan Kumar, CMI)*

You are given two *N* × *N* square array of integers. Your task is
to find out if the second one can be obtained from the first by a
*legal sequence* of moves.

There are two kinds of moves:

**Column Move:** You may pick any column of the array and
rotate it up or down by one step. For example, consider the following
array:

12 29 40 3 39 25 14 12 14 71 9 61 47 21 53 11

Rotating the fourth column of this array up by one step gives

12 29 40 12 39 25 14 61 14 71 9 11 47 21 53 3

**Row Move:** You may pick any row of the array and rotate it to
the right or left by one step. For example, rotating the third row of
the array above to the left by one results in

12 29 40 12 39 25 14 61 71 9 11 14 47 21 53 3

Continuing, we could now rotate the first row to the right by one and get

12 12 29 40 39 25 14 61 71 9 11 14 47 21 53 3

A *legal sequence* of moves consists of a single column move followed by any
sequence of row moves. Thus, the sequence of moves carried out above
is a legal sequence of moves.

Given, two arrays, you task is to find if the second one can be obtained from the first by any legal sequence of moves.

Input format

The first line of the input contains a single integer *N*
indicating the number of rows (and columns) in the two arrays. The
next *N* lines (lines 2,...,*N*+1) contain *N*
integers each and describe the first array. The next *N*+1
lines (lines *N*+2,..., 2*N* + 1) contain
*N* integers each and describe the second array.

Output format

If the second array cannot be obtained from the first by any legal sequence of moves, simply output the word "NO".

If the second array can be obtained some legal sequence of moves then the first line of the output must contain the word "YES". Further, the second line must describe a legal sequence of moves that will transform the first array into the second.

The column move rotating column *i* up is denoted by
*i* and the column move rotating column *i* down is
denoted by -*i*. The row move rotating row *j* to the
left is denoted by -*j* and the row move rotating row
*j* right is denoted by *j*. (Since the first move is a
column move and everything else is a row move there is no ambiguity in
this notation.)

There may be more than one way to transform the first array to the second and it suffices to output any one legal sequence of moves which does so.

Test data

You may assume that *N* ≤ 8.

Example

We now illustrate the input and output formats using the above example:

Sample input:

4 12 29 40 3 39 25 14 12 14 71 9 61 47 21 53 11 12 12 29 40 39 25 14 61 71 9 11 14 47 21 53 3

Sample output:

YES 4 -3 1

Copyright (c) IARCS 2003-2020; Last Updated: 01 Mar 2005