Math Homework

Ο καθηγητής των μαθηματικών σας έδωσε μια εργασία που περιλαμβάνει την εύρεση μια ακολουθίας ~N~ ακεραίων αριθμών ~A_{1}~, ~. . .~ , ~A_{N}~, τέτοια ώστε ~1 \le A_{i} \le 1\;000\;000\;000~ για κάθε ~i~.

Η ακολουθία ~A~ θα πρέπει επίσης να ικανοποιεί ~M~ προϋποθέσεις, με την ~i~-οστή να ορίζει ότι ο ΜΚΔ (Μέγιστος Κοινός Διαιρέτης) της παρακείμενης υποακολουθίας ~A_{X_{i}}~, ~. . .~ , ~A_{Y_{i}}\;(1 \le X_{i} \le Y_{i} \le N)~ πρέπει να ισούται με ~Z_{i}~. Σημειώστε ότι ο ΜΚΔ μιας ακολουθίας ακεραίων αριθμών είναι ο μεγαλύτερος ακέραιος αριθμός ~d~ τέτοιος ώστε όλοι οι αριθμοί της ακολουθίας να διαιρούνται με τον ~d~.

Βρείτε μια οποιαδήποτε έγκυρη ακολουθία ~A~ που να είναι συνεπής με όλες αυτές τις προϋπουέσεις, ή προσδιορίστε ότι δεν υπάρχει καμία τέτοια ακολουθία.

Είσοδος

Η πρώτη γραμμή θα περιέχει δύο ακέραιους αριθμούς, ~N~ και ~M~, χωρισμένους με κενό διάστημα.
Οι επόμενες ~M~ γραμμές θα περιέχουν η καθεμιά τρεις ακέραιους αριθμούς χωρισμένους με κενά διαστήματα, ~X_{i}~, ~Y_{i}~ και ~Z_{i}\;(1 \le i \le M )~.

Για ~3~ από τους ~15~ διαθέσιμους βαθμούς, ~1 \le N \le 2000~, ~1 \le M \le 2000~ και ~1 \le Z_{i} \le 2~ για κάθε ~i~.

Για επιπλέον ~4~ από τους ~15~ διαθέσιμους βαθμούς, ~1 \le N \le 2000~, ~1 \le M \le 2000~ και ~1 \le Z_{i} \le 16~ για κάθε ~i~.

Για επιπλέον ~8~ από τους ~15~ διαθέσιμους βαθμούς, ~1 \le N \le 150\;000~, ~1 \le M \le 150\;000~ και ~1 \le Z_{i} \le 16~ για κάθε ~i~.

Έξοδος

Αν δεν υπάρχει τέτοια ακολουθία, εξάγετε τη συμβολοσειρά ~Impossible~ σε μία γραμμή. Διαφορετικά, σε μία γραμμή, εξάγετε ~N~ ακέραιους αριθμούς χωρισμένους με κενά διαστήματα, που θα σχηματίζουν την ακολουθία ~A_{1}~, ~. . .~ , ~A_{N}~. Εάν υπάρχουν πολλαπλές πιθανές έγκυρες ακολουθίες, οποιαδήποτε έγκυρη ακολουθία θα είναι αποδεκτή.

Παραδείγματα

input

2 2
1 2 2
2 2 6

output

4 6

Επεξήγηση του πρώτου παραδείγματος:

Αν ~A_{1} = 4~ και ~A_{2} = 6~, ο ΜΚΔ της ~\left[A_{1}, A_{2}\right]~ είναι ~2~ και ο ΜΚΔ της ~\left[A_{2}\right]~ είναι ~6~, όπως είναι απαιτούμενο. Σημειώστε ότι και άλλες έξοδοι θα γίνονταν δεκτές.

input

2 2
1 2 2
2 2 5

output

Impossible

Επεξήγηση του δεύτερου παραδείγματος:

Δεν υπάρχει ακολουθία ~\left[A_{1}, A_{2}\right]~ τέτοια ώστε ο ΜΚΔ της ~\left[A_{1}, A_{2}\right]~ να είναι ~2~ και ο ΜΚΔ της ~\left[A_{2}\right]~ να είναι ~5~.