◀
Training Site
Sideways banner

Not Sudoku

Input: Standard Input (stdin)
Output: Standard Output (stdout)
Memory limit: 100 megabytes
Time limit: 1.0 seconds

Cindy is playing a modified version of Sudoku. She has almost finished, but can’t quite figure out what the last number should be. Your job is the write a program that completes Cindy’s Sudoku game.

Sudoku is a numbers game, using the numbers 1 through 9, played on a 9x9 grid. Each number can only appear once in each column, once in each row, and once in a 3x3 grid.

In Cindy’s modified Sudoku, there are only two rules

  1. Each row can contain any whole number from 1 to R inclusive in any order, where R is the number of rows.
  2. Each column contains exactly one occurrence of all whole numbers 1 to R inclusive. The numbers could be in any order.

The grid of numbers will be R rows down and C columns across where R and C range from 1 to 42 inclusive. This means one of Cindy's grids might not have the same number of rows as columns.

Cindy will give you a valid board where one whole number is missing. There will be a lower-case x character in place of this missing number. There will always be one, and only one, x in a grid. Your program must print the board with the x replaced by the missing number according to Cindy’s rules.

Input

The first line has the whole numbers R and C separated by a space.

The next R lines each contain C numbers separated by spaces. Together these lines make up the R\times C grid.

1 \le R, C \le 42.

Output

Print out the grid with the missing number filled in.

i.e. R lines each with C space separated whole numbers.

Subtasks

  • Subtask 1 (20%): C=1, and the numbers are in ascending order (as in sample input 1). C=1 means there is only a single number (or the x) on each line.
  • Subtask 2 (20%): C=1, but the numbers may be in any order.
  • Subtask 3 (60%): Full solution.

  • Sample Input 1

    5 1
1
2
x
4
5

    Sample Output 1

    1
2
3
4
5

  • Sample Input 2

    5 5
1 2 3 4 5
2 3 4 x 1
3 4 5 1 2
4 5 1 2 3
5 1 2 3 4

    Sample Output 2

    1 2 3 4 5
2 3 4 5 1
3 4 5 1 2
4 5 1 2 3
5 1 2 3 4