В большинстве рецептов некоторые действия необходимо делать до других. Если для каждого задания у нас имеется список других заданий, от выполнения которых оно зависит, то мы можем просто составить расписание заданий, выполнение которых приведет нас к ошеломляющему блюду. Многие из нас знают, что подобная задача может быть решена при помощи топологической сортировки. Но жизнь не всегда проста. Например, рассмотрим рецепт приготовления теста для пиццы: \begin{enumerate} \item Перемешать дрожжи с теплой водой, подождать от \textbf{5} до \textbf{10} минут. \item Мешать остальные инградиенты от \textbf{7} до \textbf{9} минут. \item Мешать дрожжи и остальные инградиенты от \textbf{10} до \textbf{15} минут. \item Подождать от \textbf{90} до \textbf{120} минут пока не подойдет тесто. \item Замесить тесто и дать ему отстояться от \textbf{10} до \textbf{15} минут. \item Раскатать тесто. \end{enumerate} Например, задания \textbf{1} и \textbf{2} могут выполняться сразу же после первой минуты (мы всегда используем первую минуту на чтение рецепта и планирование работы). Задание \textbf{3} можно начать самое раннее в \textbf{8} минут, а задание \textbf{4} можно начать толлько в \textbf{18}-ую минуту после старта и так далее. Это простое расписание. Но если некоторые задания будут иметь много зависимостей, то составление расписания становится достаточно сложной задачей. Иногда даже рецепт невозможно бывает выполнить. Например, рассмотрим следующий абстрактный рецепт: \begin{enumerate} \item задание \textbf{1} \item после задания \textbf{1}, но втечении \textbf{2}-х минут после его начала, сделать задание \textbf{2} \item как минимум через \textbf{3} минуты после начала задания \textbf{2}, но втечении \textbf{2}-х минут после начала задания \textbf{1}, сделать задание \textbf{3} \end{enumerate} У Вас имеется набор заданий. Задачи зависят друг от друга в зависимости от времени их начала. Вам необходимо назначить время начала для каждого задания так, чтобы удовлетворить все заданные условия, или сообщить о невозможности их выполнения. \InputFile Состоит из нескольких тестов. Первая строка каждого теста содержит количество заданий \textbf{n}, (\textbf{1} ≤ \textbf{n} ≤ \textbf{100}). Следующая строка содержит неотрицательное целое число \textbf{m} - количество ограничений. Каждая из следующих \textbf{m} строк описывает ограничение. Они могут быть двух типов: задание \textbf{i} начинается как минимум через \textbf{A} минут после начала задания \textbf{j}задание \textbf{i} начинается втечение \textbf{A} минут после начала задания \textbf{j} где \textbf{i} и \textbf{j} номера двух разных заданий (\textbf{1} ≤ \textbf{i}, \textbf{j} ≤ \textbf{n}), а \textbf{A} неотрицательное целое число (\textbf{A} ≤ \textbf{150}). Первое ограничение утверждает, что задание \textbf{i} может начаться как минимум через \textbf{A} минут после начала задания \textbf{j}. Второе ограничение говорит о том, что задание \textbf{i} должно начаться не раньше начала задания \textbf{j}, и втечении \textbf{A} минут после начала задания \textbf{j}. На одну и ту же пару заданий могут накладываться несколько ограничений. Отметим, что в условиях "как минимум" и "втечении" границы временного интервала включаются (то есть если задание \textbf{1} начинается в \textbf{1} минуту, а задание \textbf{2} стартует в \textbf{4} минуту, то задание \textbf{2} стартует как минимум через \textbf{3} минуты после задания \textbf{1}, и втечении \textbf{3} минут после начала задания \textbf{1}). Входные данные заканчиваются когда \textbf{n = 0}. \OutputFile Для каждого теста в отдельной строке вывести времена начала заданий с \textbf{1} по \textbf{n}, разделяя одним пробелом. Каждое число должно указывать минуту, в которую соответствующее задание начнется. Время начала каждого задания должно быть положительным и меньше \textbf{1000000}. Искомых допустимых расписаний может быть несколько, Вам следует вывести любое из них. Если расписания, удовлетворяющего все ограничения, не существует, вывести \textbf{Impossible.} в отдельной строке.