Квест

Вхідні дані

Перший рядок містить два цілі числа: $n$ та $m$ (2 \le n \le 10, 0 \le m \le 45). У наступних $m$ рядках міститься по три цілі числа: $i$, $j$ та $d$. Ця трійка означає, що найбільший спільний дільник чисел, які загадали $i$-й та $j$-й викладачі, дорівнює $d$ (1 \le d \le 100). Для кожної пари $i$ та $j$ задано не більше одного $d$. Викладачі пронумеровані від $1$ до $n$.

Вихідні дані

Якщо розв'язку не існує, виведіть слово impossible. Інакше виведіть $n$ цілих чисел — числа, які загадали викладачі. Кожне число повинно бути додатним і не перевищувати 10^{18}. Якщо існує декілька розв'язків, дозволяється вивести будь-який.

Приклади