Superdoku

Time limit2sMemory limit512 MB

Summary

Given the first k rows of an n by n grid, decide whether the remaining rows can be filled so each row and column holds 1 to n, and print one completion.

Level: Medium6 of 10
Topics: Graph, Matrix, Greedy
Solved: No attempts yet

Problem

Alice and Bob are big fans of math. They enjoy games built on numbers, and whenever they see a puzzle like Sudoku, they cannot resist solving it. The goal of Sudoku is to fill a $9 \times 9$ grid so that each row, each column, and each of the nine $3 \times 3$ boxes contains the digits 1 to 9. The setter provides a partially filled grid, and a well-posed puzzle has exactly one solution.

Problem

Superdoku uses an $n \times n$ grid. There are no box constraints. Instead, each row and each column must contain every integer from 1 to $n$ . To simplify the game, Alice and Bob fill in the first $k$ rows completely before play begins. Your task is to determine whether the grid can be completed.

Input

The first line contains two integers $n$ ( $1 \le n \le 100$ ) and $k$ ( $0 \le k \le n$ ), separated by a space. Each of the next $k$ lines contains $n$ integers, giving the first $k$ rows of the grid. Every integer is between 1 and $n$ , inclusive.

Output

If a solution exists, print yes on the first line, followed by $n$ lines with $n$ space-separated integers each, giving one valid grid. If no solution exists, print only no. If several solutions exist, print any one of them.

Examples2

Example 1

Input

4 2
1 2 3 4
2 3 4 1

Expected output

Example 2
Input
```
4 2
1 2 3 4
2 2 2 2
```
Expected output
```
no
```