GCD Subarray Matrix

You are given an array of positive integers of length ( n ). Your task is to construct an ( n \times n ) matrix ( C ) such that for every pair of indices ( i, j ) with ( 1 \leq i \leq j \leq n ), the element ( C_{ij} ) is the greatest common divisor (gcd) of the subarray ( [a_i, a_{i+1}, \dots, a_j] ). For ( i > j ), ( C_{ij} ) should be 0. The gcd is defined as ( \gcd(a, b) ) and can be computed via the Euclidean algorithm. Implement an efficient solution to compute and output the matrix.

inputFormat

The input consists of two lines. The first line contains a single integer ( n ) (the number of elements in the array). The second line contains ( n ) space-separated positive integers representing the array.

outputFormat

Output ( n ) lines, each with ( n ) space-separated integers. The ( j )-th integer in the ( i )-th line should be the gcd of the subarray from the ( i )-th element to the ( j )-th element when ( i \leq j ), and 0 when ( i > j ).## sample

3
12 15 18

12 3 3
0 15 3
0 0 18