Indian National Olympiad in Informatics

Related:

Online Programming Contest, 5-6 February 2005

IARCS home > OLYMPIAD

Basic Division

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,..., 2N + 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