Rezolvare PBinfo #2122

Marius este pasionat de pătrate perfecte. Se numeşte pătrat perfect un număr de forma x 2 (unde x este număr natural).

Într-o matrice T cu n linii şi m coloane, Marius a scris numere naturale nenule. Apoi construieşte o altă matrice NR, tot cu n linii şi m coloane. Elementul NR[i][j] = numărul de perechi de pătrate perfecte a căror diferenţă este egală cu T[i][j] (1≤i≤n, 1≤j≤m).

Cerința

Cunoscându-se numerele n, m şi matricea T, să se afişeze matricea NR.

Date de intrare

Fişierul de intrare diferenta.in conţine pe prima linie valorile n şi m, reprezentând numărul de linii, respectiv de coloane ale matricei. Pe următoarele n linii ale fişierului de intrare se găsesc câte m numere naturale nenule, reprezentând elementele matricei T. Valorile scrise pe aceeaşi linie sunt separate prin câte un spaţiu.

Date de ieșire

Fişierul de ieşire diferenta.out conţine n linii pe care sunt scrise câte m numere naturale separate prin câte un spaţiu, reprezentând elementele matricei NR.

Restricții și precizări

• 1 ≤ n ≤ 100
• 1 ≤ m ≤ 100
• Numerele din matricea T sunt numere naturale nenule ≤ 40000.

Exemplu:

diferenta.in

2 3
2 3 4
5 6 7

diferenta.out

0 1 1
1 0 1

Explicație

Pentru 2 şi 6 nu există nicio pereche de pătrate perfecte pentru care diferenţa să fie 2, respectiv 6.
Pentru 3 există perechea de pătrate perfecte 4 1, etc