Problem: J: Horizontal-Vertical Permutation

Problem Statement

You are given a positive integer N. Your task is to determine if there exists a square matrix A whose dimension is N that satisfies the following conditions and provide an example of such matrices if it exists. A_{i, j} denotes the element of matrix A at the i-th row and j-th column.

* For all i, j (1 \leq i, j \leq N), A_{i, j} is an integer that satisfies 1 \leq A_{i, j} \leq 2N - 1.
* For all k = 1, 2, ..., N, a set consists of 2N - 1 elements from the k-th row or k-th column is \\{1, 2, ..., 2N - 1\\}.



If there are more than one possible matrices, output any of them.

Input


N

Input consists of one line, which contains the integer N that is the size of a square matrix to construct.

Constraint

* N is an integer that satisfies 1 \leq N \leq 500.



Output

Output `No` in a single line if such a square matrix does not exist.

If such a square matrix A exists, output `Yes` on the first line and A after that. More specifically, follow the following format.


Yes
A_{1, 1} A_{1, 2} ... A_{1, N}
A_{2, 1} A_{2, 2} ... A_{2, N}
:
A_{N, 1} A_{N, 2} ... A_{N, N}


Sample Input 1


4

Output for Sample Input 1


Yes
2 6 3 7
4 5 2 1
1 7 5 6
5 3 4 2


Sample Input 2


3

Output for Sample Input 2


No





Example

Input

4


Output

Yes
2 6 3 7
4 5 2 1
1 7 5 6
5 3 4 2

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
#define fi first
#define se second
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
const ll mod=65537;
const int mo=65537;
ll powmod(ll a,ll b) {ll res=1;a%=mod;for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
// head


const int N = 510;
int A[N][N],p[N][N];
/* 合并子问题 */
void merge(int n)
{
    /*
     * n 为偶数时，比赛 n - 1 天
     * n 为奇数时，比赛 n 天
     */
    int days = n&1 ? n  : n-1;
    /*
     * 中间值，若n为奇数，则使 m = (n / 2) + 1,
     * 即，前半部分不小于后半部分
     */
    int m = (int)ceil(n / 2.0);
    int passed_days = m& 1? m : m - 1;    /* 已经安排的天数 */

    /*
     *  通过前 n/2 的比赛安排，构造后n/2的比赛安排
     *  如果 n 为奇数，则会产生一个虚拟选手
     */
    for (int i = 1; i <= m; i++)
    {
        for (int j = 1; j <= passed_days; j++)
        {
            if (A[i][j] != 0)   /* 如果 i 号在第 j 天有对手 */
            {
                /*
                 * 那么，(i + m) 号在第 j 天的对手为 i号的
                 * 对手往后数 m 号
                 */
                A[i + m][j] = A[i][j] + m;
            }
            else   /* 如果 i 号在第 j 天没有对手*/
            {
                /*
                 * 那么就让 i 号和 （i + m）号互为对手
                 */
                A[i + m][j] = i;
                A[i][j] = i + m;
            }
        }
    }

    int add_one = 0;        /*标志子问题是否是奇数，如果是的话构造增量加1 */
    if (A[1][passed_days] == m + 1)
        add_one = 1;
    for (int i = 1; i <= m; i++)
    {
        for (int j = passed_days + 1, count = 0; j <= days; j++, count++)
        {
            /*
             * 构造i 号在第 j 天的对手
             */
            int r_value = (count + (i - 1)  + add_one) % m + m + 1;
            A[i][j] = r_value;
            A[r_value][j] = i;
        }
    }
    if ( n & 1 )            /* 如果 n 为奇数，消除虚拟的选手 */
    {
        for (int i = 1; i <= 2 * m; i++)
        {
            for (int j = 1; j <= days; j++)
                if (A[i][j] == n + 1)
                    A[i][j] = 0;        /* A[i][j] = 0 ,表示 i 号选手在第 j 天没有比赛 */
        }
    }
}

/* 分治求解循环赛问题 */
void tournament(int n)
{
    if (n <= 1)
        return;
    else if (n == 2)        /* 2 个选手 */
    {
        A[1][1] = 2;
        A[2][1] = 1;
    }
    else
    {
        tournament((int)ceil(n / 2.0));
        merge(n);
    }
}

int main() {
    int n;
    scanf("%d",&n);
    if (n%2==1) {
        if (n==1) {
            puts("Yes\n1");
        } else {
            puts("No");
        }
        return 0;
    }
    tournament(n);
    for (int i=0;i<n;i++) p[i][i]=1;
    for (int i=1;i<=n-1;i++) {
        for (int j=1;j<=n;j++) if (A[j][i]>j) {
            p[j-1][A[j][i]-1]=i+1;
            p[A[j][i]-1][j-1]=n+i;
        }
    }
    puts("Yes");
    for (int i=0;i<n;i++) for (int j=0;j<n;j++) printf("%d%c",p[i][j]," \n"[j==n-1]);
}