During this week, the service of Jutge.org may be disrupted by major platform upgrades.

Consider an n × m matrix of natural numbers. Here, we say that two numbers x and y of the matrix are neighbours if they are horizontally, vertically or diagonally adjacent. You have to add a number chosen among {2, 3, 5, 8} to each number of the matrix. As a result, for every pair of neighbours x and y of the new matrix, x − y cannot be a multiple of four.

Input

Input consists of several cases, each one with n and m, both between 1 and 100,
followed by n lines, each one with m integer numbers between 0 and 10^{9}.

Output

For every given matrix, print your resulting matrix. If there is more than one solution, print any of them. Print a line with 20 dashes after every matrix.

Public test cases

**Input**

1 2 1000000000 999999999 2 3 0 1 2 0 1 2 2 3 0 1 2 0 1 2

**Output**

1000000008 1000000001 -------------------- 5 3 4 8 6 5 -------------------- 2 3 10 8 9 4 --------------------

Information

- Author
- Salvador Roura
- Language
- English
- Official solutions
- C++
- User solutions
- C++ Rust