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 never contain the same number more than once, but it may contain any whole number from 1 to R inclusive in any order. 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 eks character x 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