Archiwum zadań programistycznych WWSI

Dany jest ciąg n liczb: a₁, a₂, a₃, ..., a_n. Twoim zadaniem jest wyznaczenie macierzy największych wspólnych dzielników (NWD) dla danego ciągu liczbowego. Macierz NWD składa się z n wierszy, każdy z nich zawiera po n liczb. Liczba j-ta w i-tym wierszu równa jest największemu wspólnemu dzielnikowi elementów a_i i a_j.

Wejście

W pierwszej linii znajduje się jedna liczba całkowita n ∈ [1;1000] określająca liczbę elementów ciągu, dla którego mamy wyznaczyć macierz NWD. W drugiej linii znajduje się n liczb całkowitych z przedziału [1;10⁹]. Liczba i-ta w kolejności określa wartość elementu a_i.

Wyjście

Na wyjściu należy wypisać szukaną macierz NWD.

Przykład

Wejście:

3
6 15 7

Wyjście:

6 3 1 
3 15 1 
1 1 7

Wyjaśnienie do przykładu:

NWD(6,6) = 6 NWD(6,15) = 3 NWD(6,7) = 1
NWD(15,6) = 3 NWD(15,15) = 15 NWD(15,7) = 1
NWD(7,6) = 1 NWD(7,15) = 1 NWD(7,7) = 7