eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Квест

Квест

Ліміт часу 2 секунди
Ліміт використання пам'яті 64 MiB

Під час квесту у ЛКШ-2017 викладачі дали школярам таке завдання. Кожен з n викладачів задумав число. Школяр може спіймати двох викладачів і запитати про їхні числа. У відповідь вони повідомляють школяру найбільший спільний дільник задуманих ними чисел.

Школярі опитали m пар викладачів. Допоможіть школярам вияснити числа, задумані викладачами.

Вхідні дані

Перший рядок вхідного файлу містить два цілих числа: n та m (2n10, 0m45). Наступні m рядків містять по три цілих числа: i, j та d - така трійка означає, що найбільший спільний ділбник чисел, задуманих i-м та j-м викладачами дорівнює d (1d100). Для кожних двох i та j задано не більше 1-го d. Викладачі нумеруються від 1 до n.

Вихідні дані

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

Приклад

Вхідні дані #1
3 3
1 2 2
1 3 3
2 3 5
Вихідні дані #1
6
10
15
Автор Андрій Станкевич
Джерело Тринадцатая международная командная олимпиада школьников ЛКШ среди параллелей A, A' и B