B. Neighbor Grid

B. Neighbor Grid

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

You are given a grid with nn rows and mm columns, where each cell has a non-negative integer written on it. We say the grid is good if for each cell the following condition holds: if it has a number k>0k>0 written on it, then exactly kk of its neighboring cells have a number greater than 00 written on them. Note that if the number in the cell is 00, there is no such restriction on neighboring cells.

You are allowed to take any number in the grid and increase it by 11. You may apply this operation as many times as you want, to any numbers you want. Perform some operations (possibly zero) to make the grid good, or say that it is impossible. If there are multiple possible answers, you may find any of them.

Two cells are considered to be neighboring if they have a common edge.

Input

The input consists of multiple test cases. The first line contains an integer tt (1≤t≤50001≤t≤5000)  — the number of test cases. The description of the test cases follows.

The first line of each test case contains two integers nn and mm (2≤n,m≤3002≤n,m≤300)  — the number of rows and columns, respectively.

The following nn lines contain mm integers each, the jj-th element in the ii-th line ai,jai,j is the number written in the jj-th cell of the ii-th row (0≤ai,j≤1090≤ai,j≤109).

It is guaranteed that the sum of n⋅mn⋅m over all test cases does not exceed 105105.

Output

If it is impossible to obtain a good grid, print a single line containing "NO".

Otherwise, print a single line containing "YES", followed by nn lines each containing mm integers, which describe the final state of the grid. This final grid should be obtainable from the initial one by applying some operations (possibly zero).

If there are multiple possible answers, you may print any of them.

Example

input

Copy

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

output

Copy

YES
0 0 0 0
0 1 1 0
0 0 0 0
NO
YES
0 0
0 0
NO
YES
0 1 0 0
1 4 2 1
0 2 0 0
1 3 1 0

Note

In the first test case, we can obtain the resulting grid by increasing the number in row 22, column 33 once. Both of the cells that contain 11 have exactly one neighbor that is greater than zero, so the grid is good. Many other solutions exist, such as the grid

01000100

02100210

00000000

All of them are accepted as valid answers.

In the second test case, it is impossible to make the grid good.

In the third test case, notice that no cell has a number greater than zero on it, so the grid is automatically good.

=========================================================================

他说可以操作任意次的加1，那就全部加到极点

结果类似这种

2333332

3444443

3444443

2333332

先构造答案矩阵，再看看是否有点超过了极限情况即可‘

# include<iostream>
# include<string.h>
# include<vector>

using namespace std;

int a[500][500];
int ans[500][500];

int work(int i,int j,int n,int m)
{

    if(i==1&&j==1)
        return 2;
    if(i==1&&j==m)
        return 2;
    if(i==n&&j==1)
        return 2;
    if(i==n&&j==m)
        return 2;
    if(i==1&&(j>=2&&j<=m-1))
        return 3;
    if(i==n&&(j>=2&&j<=m-1))
        return 3;
    if(j==1&&(i>=2&&i<=n-1))
        return 3;
    if(j==m&&(i>=2&&i<=n-1))
        return 3;

    return 4;
}
int main ()
{
    int t;
    cin>>t;

    while(t--)
    {
        int n,m;
        cin>>n>>m;

        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                cin>>a[i][j];
            }
        }


        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                ans[i][j]=work(i,j,n,m);
            }
        }
        int flag=0;

        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                if(a[i][j]>ans[i][j])
                {
                    flag=1;
                    break;
                }
            }
        }

        if(flag)
        {
            cout<<"NO"<<endl;
        }
        else
        {
            cout<<"YES"<<endl;
            for(int i=1;i<=n;i++)
            {
                for(int j=1;j<=m;j++)
                {
                    cout<<ans[i][j]<<" ";
                }

                cout<<endl;
            }

        }

    }



    return  0;

}