找平方数

Description

While resting on the ship after the "Russian Code Cup" a boy named Misha invented an interesting game. He promised to give his quadrocopter to whoever will be the first one to make a rectangular table of size n × m, consisting of positive integers such that the sum of the squares of numbers for each row and each column was also a square.

Since checking the correctness of the table manually is difficult, Misha asks you to make each number in the table to not exceed 10⁸.

题目网址： http://codeforces.com/problemset/problem/417/E

Input

The first line contains two integers n and m (1 ≤ n, m ≤ 100)  — the size of the table.

Output

Print the table that meets the condition: n lines containing m integers, separated by spaces. If there are multiple possible answers, you are allowed to print anyone. It is guaranteed that there exists at least one correct answer.

Sample Input

Input

1 1

Output

1

Input

1 2

Output

3 4

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;

bool judge(int num)
{
    int k = sqrt(num);
    if(k*k == num)
    return true;
    return false;
}

int main()
{
    int n,m;
    while(scanf("%d %d",&n,&m)!=EOF)
    {
        int a,b,c,d;
        int flag = 0;
        for(a=1;a<=100;a++)
        for(b=1;b<=100;b++)
        for(c=1;c<=100;c++)
        for(d=1;d<=100;d++)
        if(judge(a*a*(m-1)+b*b)&&
           judge(a*a*(n-1)+c*c)&&
           judge(c*c*(m-1)+d*d)&&
           judge(b*b*(n-1)+d*d))
        goto endw;

        endw:;
        for(int i=1;i<=n-1;i++)
        {
            for(int j=1;j<=m-1;j++)
            printf("%d ",a);
            printf("%d
",b);
        }
        for(int i=1;i<=m-1;i++)
        printf("%d ",c);
        printf("%d
",d);
    }
    return 0;
}