Квест
Під час квесту у ЛКШ-2017 викладачі дали школярам таке завдання. Кожен з n викладачів задумав число. Школяр може спіймати двох викладачів і запитати про їхні числа. У відповідь вони повідомляють школяру найбільший спільний дільник задуманих ними чисел.
Школярі опитали m пар викладачів. Допоможіть школярам вияснити числа, задумані викладачами.
Вхідні дані
Перший рядок вхідного файлу містить два цілих числа: n та m (2 ≤ n ≤ 10, 0 ≤ m ≤ 45). Наступні m рядків містять по три цілих числа: i, j та d - така трійка означає, що найбільший спільний ділбник чисел, задуманих i-м та j-м викладачами дорівнює d (1 ≤ d ≤ 100). Для кожних двох i та j задано не більше 1-го d. Викладачі нумеруються від 1 до n.
Вихідні дані
Якщо розв'язку не існуєт, виведіть у вихідний файл слово impossible. Інакше виведіть n цілих чисел - числа, задумані викладачами. Кожне число повинно бути додатнім і не перевищувати 10^18. Якщо розв'язків декілька, виведіть довільний.