GCD Sequence Construction

Construct an integer sequence \(A\) of length \(N\) such that:

• \(1 \le A_i \le 10^9\) for all \(1 \le i \le N\).
• For each of the given \(M\) queries with indices \(X_i\) and \(Y_i\), the greatest common divisor (gcd) of the subsequence \(A[X_i], A[X_i+1], \ldots, A[Y_i]\) equals \(Z_i\); in other words, \(\gcd(A[X_i], A[X_i+1], \ldots, A[Y_i]) = Z_i\).

If a valid sequence exists, output the sequence. Otherwise, report no solution by printing \(-1\).

inputFormat

The input begins with a line containing two integers \(N\) and \(M\), where \(N\) is the length of the sequence and \(M\) is the number of queries.

Each of the following \(M\) lines contains three integers \(X\), \(Y\), and \(Z\) (with \(1 \le X \le Y \le N\)), indicating that
\(\gcd(A[X], A[X+1], \ldots, A[Y]) = Z\).

outputFormat

If a valid sequence exists, output \(N\) space-separated integers representing \(A\) (ensuring \(1 \le A_i \le 10^9\)). Otherwise, output \(-1\).

sample

3 2
1 2 2
2 3 3

2 6 3