Latin Squares

Interview

Time limit1sMemory limit512 MB

Summary

Read an n by n grid of base-n digit characters and report whether it is a Latin square, and if so whether it is in reduced form.

Level: Easy2 of 10
Topics: Implementation, Array, Simulation, Hash map
Solved: No attempts yet

Problem

A Latin square is an $n \times n$ array filled with $n$ different digits, where every digit occurs exactly once in each row and exactly once in each column. (The name comes from Leonhard Euler, who used Latin characters in his papers on the subject.)

A Latin square is in reduced form when its top row and its leftmost column are both in natural order. The natural order of a set of digits is by increasing value.

Read an $n \times n$ array, decide whether it is a Latin square, and if it is, decide whether it is in reduced form.

Input

The first line contains a single integer $n$ ( $2 \le n \le 36$ ). Each of the next $n$ lines contains $n$ digits in base $n$ . Digit values below 10 are written with the characters 0 through 9, and values from 10 to 35 are written with the uppercase letters A through Z. Every character in the input is legal in base $n$ . For example, if $n$ is 3, the only characters in the $n$ lines describing the array are 0, 1, and 2.

Output

If the given array is not a Latin square, print No on a single line. If it is a Latin square but not in reduced form, print Not Reduced. If it is a Latin square in reduced form, print Reduced.

Examples4

Example 1
Input
```
3
012
120
201
```
Expected output
```
Reduced
```
Example 2
Input
```
4
3210
0123
2301
1032
```
Expected output
```
Not Reduced
```

Example 3

Input

11
0123458372A
A9287346283
0285475A834
84738299A02
1947584037A
65848430002
038955873A8
947530200A8
93484721084
95539A92828
04553883568

Expected output

No

Example 4
Input
```
2
01
10
```
Expected output
```
Reduced
```