Во время квеста в ЛКШ-2017 преподаватели дали школьникам такое задание. Каждый из \textbf{n} преподавателей задумал число. Школьник может поймать двух преподавателей и спросить об их числах. В ответ они сообщают школьнику наибольший общий делитель задуманных ими чисел. Школьники опросили \textbf{m} пар преподавателей. Помогите школьникам выяснить числа, задуманные преподавателями. \InputFile Первая строка входного файла содержит два целых числа: \textbf{n} и \textbf{m} (\textbf{2} ≤ \textbf{n} ≤ \textbf{10}, \textbf{0} ≤ \textbf{m} ≤ \textbf{45}). Следующие \textbf{m} строк содержат по три целых числа: \textbf{i}, \textbf{j} и \textbf{d} - такая тройка означает, что наибольший общий делитель чисел, загаданных \textbf{i}-м и \textbf{j}-м преподавателями равен \textbf{d} (\textbf{1} ≤ \textbf{d} ≤ \textbf{100}). Для каждых двух \textbf{i} и \textbf{j} дано не более \textbf{1}-го \textbf{d}. Преподаватели нумеруются от \textbf{1} до \textbf{n}. \OutputFile Если решения не существует, выведите в выходной файл слово \textbf{impossible}. Иначе выведите \textbf{n} целых чисел - числа, задуманные преподавателями. Каждое число должно быть положительным и не превышать \textbf{10^18}. Если решений несколько, выведите любое.